分類	排序算法	改進思路	最好情況	平均時間複雜度	最壞情況	空間複雜度	穩定性
插入排序	直接插入排序	基本排序方法	O(n)	O(\(n^2\))	O(\(n^2\))	O(1)	穩定
折半插入排序	确定有序序列的插入位置	O(\(nlog_2n\))	O(\(n^2\))	O(\(n^2\))	O(1)	穩定
希爾排序	利用直接插入的最好情況	O(\(n^{1.3}\))	NA	O(\(n^2\))	O(1)	不穩定
交換排序	冒泡排序	基本排序方法	O(n)	O(\(n^2\))	O(\(n^2\))	O(1)	穩定
快速排序	交換不相鄰元素	O(\(nlog_2n\))	O(\(nlog_2n\))	O(\(n^2\))	O(\(nlog_2n\))	不穩定
選擇排序	簡單選擇排序	基本排序方法	O(\(n^2\))	O(\(n^2\))	O(\(n^2\))	O(1)	不穩定
堆排序	将待排序列轉化為完全二叉樹	O(\(nlog_2n\))	O(\(nlog_2n\))	O(\(nlog_2n\))	O(1)	不穩定
歸并排序	2路歸并排序	合并每個有序序列	O(\(nlog_2n\))	O(\(nlog_2n\))	O(\(nlog_2n\))	O(n)	穩定
基數排序	基數排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	穩定

插入排序

直接插入排序

基本思想：

可以将L(2)~L(n)依次插入到前面已排好序的子序列中，初始假定L[1]是一個已經排好序的子序列。
1. 查找出L(i)在L[1...i-1]中的插入位置k。
2. 将L[k...i-1]中的所有元素全部後移一個位置。
3. 将L(i)複制到L(k)。
具體實作：

void InsertSort(ElemType A[], int n) {
    int i, j;
    for(i = 2; i <= n; i++) {       //依次将A[2]~A[n]插入到前面已排序序列
        if(A[i].data < A[i-1].data) {   //若A[i]的關鍵碼小于有序序列的最後一個元素（有序序列中的最大值）（即其前驅），需将A[i]插入有序表；大于有序序列的最後一個元素，則不用從頭插入，并入有序序列（本來就排在有序序列之後），成為有序序列新的最大值（最後一個）
            A[0] = A[i];        //複制為哨兵，A[0]不存放元素
            for(j = i - 1; A[0].data < A[j].data; --j) {    //從後往前查找待插入位置
                A[j+1] = A[j];      //向後挪位
            }
            A[j+1] = A[0];      //複制到插入位置
        }
    }
}

性能分析：
- 空間效率：O(1)
  
  僅使用了常數個輔助單元。
- 時間效率：O(\(n^2\))
  
  在排序過程中，向有序子表中逐個插入元素的操作進行了n-1趟，每趟操作都分比較關鍵字和移動元素，而比較次數和移動元素取決于待排序表的初始狀态。
  - 最好情況：O(n) (順序)
  - 最壞情況：O(\(n^2\)) (逆序)
  - 平均情況：O(\(n^2\))
- 穩定性：穩定
  
  由于每次插入元素時，總是從後向前先比較在移動，是以不會出現相同元素相對位置發生變化的情況。
- 适用性：
  
  适用于順序存儲和鍊式存儲的線性表。
  
  适用于基本有序的排序表和資料量不大的排序表。
  
  為鍊式存儲時，可以從前往後查找指定元素的位置。
  
  大部分排序算法都僅适用于順序存儲的線性表。

折半插入排序

基本思想：

将比較和移動操作分離，即先折半查找出元素的待插入位置，然後統一地移動待插入位置之後的所有元素。
具體實作：

void InsertSort(ElemType A[], int n) {
    int i, j, low, high, mid;
    for(i = 2; i <= n; i++) {       //依次将A[2]~A[n]插入前面的已知排序序列
        A[0] = A[i];        //将A[i]暫存到A[0]
        low = 1;            //設定折半查找的範圍
        high = i-1;         
        while(low <= high) {    //折半查找（預設遞增有序）
            mid = (low + high) / 2;     //取中間點
            if(A[mid].data > A[0].data) {   //查找左半邊
                high = mid - 1;
            }else {         //查找右半邊
                low = mid + 1;
            }
            //查找結束後，high<low，k在high和high+1之間，是以頂替high+1位置，把high+1後面的元素後移
            for(j=i-1; j>=high+1; --j) {
                A[j+1] = A[j];      //統一後移元素，空出插入位置
            }
            A[high+1] = A[0];       //插入
        }
    }
}

性能分析：
- 空間效率：O(1)
  
  僅使用了常數個輔助單元。
- 時間效率：O(\(n^2\))
  
  僅減少了比較元素的次數，約為O(\(nlog_2n\))，該比較次數與待排序表的初始狀态無關，僅取決于表中元素的個數n；而元素移動次數并未改變，他依賴于待排序表的初始狀态。
  - 最好情況：O(\(nlog_2n\)) (順序)
  - 最壞情況：O(\(n^2\)) (逆序)
  - 平均情況：O(\(n^2\))
- 穩定性：穩定
- 适用性：
  
  适用于順序存儲的線性表
  
  适用于基本有序的排序表和資料量不大的排序表。

希爾排序

基本思想：

先将待排序表分割成若幹形如L[i, i+d, i+2d, ..., i+kd]的“特殊”子表，分别進行直接插入排序，當整個表中的元素已呈“基本有序”時，再對全體記錄進行一次直接插入排序
具體實作：

//對順序表做希爾插入排序，本算法和直接插入排序相比，做了以下修改：
//1. 前後記錄的位置增量是dk，不是1
//2. A[0]隻是暫存單元，不是哨兵，當j<=0時，插入位置已到
void ShellSort(ElemType A[], int n) {
    for(dk=n/2; dk>=1; dk=dk/2) {       //步長變化
        for(i=dk+1; i<=n; ++i) {
            if(A[i].data < A[i-dk].data) {      //需将A[i]插入有序增量子表
                A[0] = A[i];        //暫存在A[0]
                for(j=i-dk; j>0 && A[0].data<A[j].data; j-=dk) {
                    A[j+dk] = A[j];     //記錄後移，尋找插入的位置
                }
                A[j+dk] = A[0];     //插入
            }
        }
    }
}

性能分析：
- 空間效率：O(1)
  
  僅使用了常數個輔助單元
- 時間效率：
  
  由于希爾排序的時間複雜度依賴于增量序列的函數，這設計數學上尚未解決的難題，是以其時間複雜度分析比較困難。
  - 最好情況：O(\(n^{1.3}\)) (當n在某個特定範圍時)
  - 最壞情況：O(\(n^2\))
  - 平均情況：NA
- 穩定性：不穩定
  
  但相同關鍵字的記錄被劃分到不同的子表時，可能會改變它們之間的相對次序。
- 适用性：僅适用于線性表為順序存儲的情況。

交換排序

冒泡排序

基本思想：

假設待排序表長為n，從後往前（或從前往後）兩兩比較相鄰元素的值，若為逆序（即A[i-1] > A[i]），則交換它們，知道序列比較完。稱之為一趟冒泡，即将最小的元素交換到待排序列的第一個位置（關鍵字最小的元素如氣泡一般逐漸往上“漂浮”直至“水面”）。下一趟冒泡時，前一趟确定的最小元素不在參與比較，待排序列減少一個元素。這樣最多做n-1趟冒泡就能把所有元素排好序。
具體實作：

//用冒泡排序法将序列A中的元素按從小到大排列
void BubbleSort(ElemType A[], int n) {
    for(i=0; i<n-1; i++) {  //趟數
        flag = false;       //表示本趟冒泡是否發生交換的标志
        for(j=n-1; j>i; j--) {      //一趟冒泡過程
            if(A[j-1].data > A[j].data) {   //若為逆序
                swap(A[j-1], A[j]);     //交換
                flag = true;
            }
        }
        if(flag == false) {     //本趟周遊後沒有發生交換（前面一個元素均小于後面一個），說明表已經有序
            return;
        }
    }
}

性能分析：
- 空間效率：O(1)
  
  僅使用了常數個輔助單元
- 時間效率：O(\(n^2\))
  
  當初始序列有序時，顯然第一趟冒泡後沒有元素交換（前均小于後），進而直接跳出循環，比較次數為n-1，移動次數為0。
  - 最好情況：O(n) (順序)
  - 最壞情況：O(\(n^2\)) (逆序)
  - 平均情況：O(\(n^2\))
- 穩定性：穩定
  
  i>j且A[i].data==A[j].data時，不會交換兩個元素
- 适用性：
  
  适用于線性表
  
  适用于基本有序的排序表。

快速排序

基本思想：

基于分治法，在待排序表L[1...n]中任取一個元素pivot(樞軸)作為基準，通過一趟排序将待排表劃分為兩個獨立的兩部分L[1...k-1]和L[k+1...n]，使得L[1...k-1]中所有元素小于pivot，L[k+1...n]中的所有元素大于等于pivot，則pivot放在了其排序後的最終位置L(k)上，這個稱為一趟快速排序。而後分别遞歸地對兩個子表重複上述過程，直至每個部分内隻有一個元素或空為止，即所有元素放在了其最終位置上。
具體實作：

//劃分算法（一趟排序過程）
int Partition(ElemType A[], int low, int high) {
    ElemType pivot = A[low];    //将目前表中第一個元素設為樞軸值，對表進行劃分
    while(low < high) {     
        while(low<high && A[high]>=pivot) {     //當high中的值已經比pivot大，則不移動
            --high;
        }
        //循環結束時，high中的元素比pivot小
        A[low] = A[high];       //将小值移動到左端
        while(low<high && A[low]<=pivot) {      //當low中的值已經比pivot小，則不移動
            ++low;
        }
        //循環結束時，low中的元素比pivot大
        A[high] = A[low];       //将大值移動到右端
    }
    //循環結束時，low==high，已經是pivot的最終位置
    A[low] = pivot;     //放入最終位置
    return low;     //傳回存放樞軸的最終位置
}

void QuickSort(ElemType A[], int low, int high) {
    if(low >= high) {   //不能劃分了，遞歸出口
        return;
    }
    int pivotpos = Partition(A, low, high);     //劃分
    QuickSort(A, low, pivotpos-1);      //依次對兩個子表進行遞歸排序劃分
    QuickSort(A, pivotpos+1, high);
}

性能分析：
- 空間效率：O(\(log_2n\))
  
  遞歸需要借助一個遞歸工作棧來儲存每層遞歸調用的必要資訊，其容量應與遞歸調用的最大深度一緻。
  - 最好情況：⌈\(log_2(n+1)\)⌉
  - 最壞情況：O(n)
  - 平均情況：O(\(log_2n\))
- 時間效率：O(\(nlog_2n\))
  
  快速排序的運作時間與劃分是否對稱有關，而後者又與具體使用的劃分算法有關。
  - 最好情況：O(\(nlog_2n\)) (對稱，即大于、小于樞軸的個數相等)
  - 最壞情況：O(\(n^2\)) (基本有序或基本逆序)
  - 平均情況：O(\(nlog_2n\))
- 穩定性：不穩定
  
  在劃分算法中，若右端區間有兩個關鍵字相同，且均小于基準值的記錄，則在交換到左區間後，它們的相對位置會發生變化。
- 适用性：
  
  适用于順序存儲的線性表。
  
  适用于資料量較大的排序表。

選擇排序

簡單選擇排序

基本思想：

假設排序表為L[1...n]，第i趟排序即從L[i...n]中選擇關鍵字最小的元素與L(i)交換，每一趟排序可以确定一個元素的最終位置，這樣經過n-1趟排序就可使得整個排序表有序。
具體實作：

//對表A做簡單選擇排序，A[]從0開始存放元素
void SelectSort(ElemType A[], int n) {
    for(i=0; i<n-1; i++) {      //一共進行n-1趟
        min = i;                //記錄最小元素的位置
        for(j=i+1; j<n; j++) {  //在A[i...n-1]中選擇最小的元素
            if(A[j] < A[min]) { //更新最小元素位置
                min = j;
            }
            if(min != i) {      //與第i個位置交換
                swap(A[i], A[min]);
            }
        }
    }
}

性能分析：
- 空間效率：O(1)
  
  僅使用常數個輔助單元
- 時間效率：O(\(n^2\))
  
  元素間比較次數與序列的初始狀态無關，始終是n(n-1)/2次。
  - 最好情況：O(\(n^2\))
  - 最壞情況：O(\(n^2\))
  - 平均情況：O(\(n^2\))
- 穩定性：不穩定
  
  在第i趟找到最小元素後，和第i個元素交換，可能會導緻第i個元素與其含有相同關鍵字元素的相對位置發生改變。
- 适用性：
  
  适用于順序存儲的線性表。
  
  适用于資料量較小的排序表和記錄本身資訊量較大的排序表。
  
  PS：當記錄本身資訊量較大時，為避免耗費大量時間移動記錄，可用連結清單作為存儲結構。

堆排序

堆排序是一種樹形選擇排序方法，其特點是：在排序過程中，将L[1...n]視為一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點的内在關系，在目前無序區中選擇關鍵字最大（或最小）的元素。經常被用來實作**優先級隊列**。

基本思想：

堆排序的關鍵是構造初始堆，對初始序列建堆，是一個反複篩選的過程。

n個結點的完全二叉樹，最後一個結點是第⌊n/2⌋個結點的孩子（即⌊n/2⌋是最後一個分支結點）。
1. 建堆
  
  對第⌊n/2⌋個結點為根的子樹篩選（對于大根堆，若根節點的關鍵字小于左右孩子中的較大者，則交換，即讓最大的當根節點），使該子樹稱為堆。之後向前依次對各節點（⌊n/2⌋-1 ~ 1）為根的子樹進行篩選，取自己與左右孩子之間的較大值為根，交換後可能會破壞下一級的堆，于是繼續采用上述方法構造下一級的堆，直到以該節點為根的子樹構成堆為止。反複利用上述調整堆的方法建堆，直到根節點。
2. 堆排序
  
  首先将存放在L[1...n]中的n個元素建成初始堆，由于堆本身的特點（以大頂堆為例），堆頂元素就是最大值。輸出堆頂元素後，通常将堆底元素送入堆頂，此時根節點已不滿足大頂堆的性質，堆被破壞，将堆頂元素向下調整使其繼續保持大頂堆的性質，再輸出堆頂元素。如此反複，知道堆中僅剩下一個元素為止。

具體實作：

向下調整堆（建堆或删除堆頂元素時可用）

//函數AdjustDown将元素k向下進行調整
void AdjustDown(ElemType A[], int k, int len) {
  A[0] = A[k];        //A[0]暫存        此時k為根節點
  for(i=2*k; i<=len; i*=2) {      //沿key較大的子結點向下篩選
  //i為2k，即i為k的左子節點
      if(i<len && A[i]<A[i+1]) {      //A[i] < A[i+1]，即左子結點小于右子結點
          i++;        //取key較大的子結點的下标
      }
      if(A[0] >= A[i]) {      //根節點大于左右孩子中的較大值，篩選結束
          break;
      }else {     //根節點小于左右孩子中的較大值
          A[k] = A[i];        //将A[i]（較大值）調整到雙親結點上
          //（交換後可能會破壞下一級的堆）
          k = i;              //修改k值，取之前較大的孩子結點的位置，以便繼續向下篩選出較大值并調整
      }
  }//循環結束後，k指向了被篩選結點的最終位置
  A[k] = A[0];        //被篩選的結點值放入最終位置
}

向上調整堆（對堆進行插入操作時可用）

//函數AdjustUp将元素k向上進行調整
void AdjustUp(ElemType A[], int k) {
//參數k為向上調整的結點，也為堆的元素個數（因為插入時新結點先放在堆的末端）
  A[0] = A[k];    //A[0]暫存 把k當指針用
  int i = k/2;    //i為k的雙親結點
  while(i>0 && A[i]<A[0]) {   //若結點值大于雙親結點，則将雙親結點下調，并繼續向上比較
      A[k] = A[i];        //雙親結點i下調到子結點k
      //（上調後可能會破壞上一級的堆）
      k = i;              //k指向雙親結點i
      i = k/2;            //i取此時的k的雙親結點，繼續向上比較
  }//循環結束後，k指向了被篩選結點的最終位置
  A[k] = A[0];            //複制到最終位置
}

建堆

//建立大根堆
void BuildMaxHeap(ElemType A[], int len) {
  for(int i=len/2; i>0; i--) {    //從i=[n/2] ~ 1，反複調整堆
      AdjustDown(A, i, len);
  }
}

堆排序

//堆排序
void HeapSort(ElemType A[], int len) {
  BuildMaxHeap(A, len);       //建立初始大頂堆堆
  for(i=len; i>1; i--) {      //n-1趟的交換和調整過程
      Swap(A[i], A[1]);       //輸出堆頂元素（并和堆底元素交換）
      AdjustDown(A, 1, i-1);  //調整，把剩餘的i-1個元素調整成大頂堆
  }
}

性能分析：
- 空間效率：O(1)
  
  僅使用了常數個輔助單元。
- 時間效率：O(\(nlog_2n\))
  
  建堆時間為O(n)，之後又n-1次向下調整操作，每次調整的時間複雜度為O(h)
  - 最好情況：O(\(nlog_2n\))
  - 最壞情況：O(\(nlog_2n\))
  - 平均情況：O(\(nlog_2n\))
- 穩定性：不穩定
  
  進行篩選時，有可能把後面相同關鍵字的元素調整到前面。
- 适用性：
  
  适用于線性表
  
  适用于資料量較大的排序表。

歸并排序

基本思想：

“歸并”的含義是将兩個或兩個以上的有序表組合成一個新的有序表。

假定待排序表含有n個記錄，則可将其視為n個有序的子表，每個子表的長度為1，然後兩兩歸并，得到\(⌈n/2⌉\)個長度為2或1的有序表；再兩兩歸并……如此重複，知道合并成一個長度為n的有序表位置，這種排序方法稱為2路歸并排序

遞歸形式的2路歸并排序算法是基于分治的。

分解：将含有n個元素的待排序表分成各含\(n/2\)個元素的子表，采用2路歸并排序算法對兩個子表遞歸地進行排序。

合并：合并兩個已排序的子表得到排序結果。
具體實作：

//表A的兩段A[low...mid]和A[mid+1...high]各自有序，将它們合并成一個有序表（合并過程中排序）
ElemType *B = (ElemType *)malloc((n+1)*sizeof(ElemType));   //輔助數組B
void Merge(ElemType A[], int low, int mid, int high) {
    for(int k=low; k<=high; k++) {
        B[k] = A[k];        //将A中所有元素複制到B中
    }
    for(i=low, j=mid+1, k=i; i<=mid && j<=high; k++) {
        if(B[i]<=B[j]) {    //比較B的左右兩段中的元素
            A[k] = B[i++];  //将較小值複制到A中
        }else {
            A[k] = B[j++];
        }
    }
    while(i <= mid) {       //若有的表中還有元素尚未檢測完，全部放入A中
        A[k++] = B[i++];
    }
    while(j <= high) {
        A[k++] = B[j++];
    }
}
//将A歸并排序
void MergeSort(ElemType A[], int low, int high) {
    if(low >= high) {       //不能再繼續分解了
        return;
    }
    int mid = (low+high)/2;     //分解：從中間劃分兩個子序列
    MergeSort(A, low, mid);     //對左側子序列進行遞歸排序
    MergeSort(A, mid+1, high);  //對右側子序列進行遞歸排序
    
    Merge(A, low, mid, high);   //歸并（并排序）
}

性能分析：
- 空間效率：O(n)
  
  Merge()操作中，輔助空間剛好占用n個單元
- 時間效率：O(\(nlog_2n\))
  
  每趟歸并的時間複雜度為O(n)，共需進行⌈log_2n⌉趟歸并
  - 最好情況：O(\(nlog_2n\))
  - 最壞情況：O(\(nlog_2n\))
  - 平均情況：O(\(nlog_2n\))
- 穩定性：穩定
  
  由于Merge()操作不會改變相同關鍵字記錄的相對次序
- 适用性：
  
  适用于順序存儲的線性表。
  
  适用于資料量較大且要求排序穩定的排序表。
  
  PS:以上排序都是基于比較的排序方法，每次比較兩個關鍵字大小之後，僅出現兩種可能的轉移，是以可以用一棵二叉樹來描述比較判定過程，由此可以證明：當檔案的n個關鍵字随機分布時，任何借助于“比較”的排序算法，至少需要O(\(nlog_2n\))的時間。

基數排序

基本思想：

将每個位數排好序，由低到高(由高到低)
具體實作：
性能分析：
- 空間效率：O(r)
  
  一趟排序需要的輔助空間為r(r個隊列)，但以後的排序中會重複使用這些隊列
- 時間效率：O(d(n+r))
  
  基數排序需要進行d趟配置設定和收集，一趟配置設定需要O(n)，一趟收集需要O(r)
  - 最好情況：O(d(n+r))
  - 最壞情況：O(d(n+r))
  - 平均情況：O(d(n+r))
- 穩定性：穩定
  
  對于基數排序算法而言，按位排序是必須是穩定的，是以保證了基數排序的穩定性
- 适用性：
  
  适用于順序存儲的線性表
  
  适用于資料量很大但記錄的關鍵字位數較少且可以分解的排序表

轉載于:https://www.cnblogs.com/blknemo/p/11234908.html

資料結構之内部排序插入排序交換排序選擇排序歸并排序基數排序

插入排序

直接插入排序

折半插入排序

希爾排序

交換排序

冒泡排序

快速排序

選擇排序

簡單選擇排序

堆排序

歸并排序

基數排序

繼續閱讀

goalng nil interface淺析持續學習

模組化：數學模組化

開源軟體：NoSql資料庫 - 圖資料庫 Neo4j轉載自原文位址：http://www.cnblogs.com/loveis715/p/5277051.html

資料在網絡7層中的傳輸過程

當今世界十大經典算法

字元串功能實作

【算法提高班】貪婪政策

《貪婪的動态規劃》

分治法實作求解最大子數組

UVA 10154:Weights and Measures Weights and Measures

Linux Kernel Development　學習

動态規劃、最小費用流例題 — nyoj_712 探尋寶藏

計算機開路人阿蘭·圖靈

基礎算法之二分查找

poj3249

PAT 1089 Insert or Merge[難]