排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。

我們這里說說八大排序就是內(nèi)部排序。

當(dāng)n較大，則應(yīng)采用時間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。

快速排序：是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機分布時，快速排序的平均時間最短；

1.插入排序—直接插入排序(Straight Insertion Sort)

基本思想:

將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數(shù)增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。

要點：設(shè)立哨兵，作為臨時存儲和判斷數(shù)組邊界之用。

直接插入排序示例：

如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。

算法的實現(xiàn)：

void print(int a[], int n ,int i){
    cout<<i <<":";
    for(int j= 0; j<8; j++){
        cout<<a[j] <<" ";
    }
    cout<<endl;
}
 
 
void InsertSort(int a[], int n)
{
    for(int i= 1; i<n; i++){
        if(a[i] < a[i-1]){               //若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入
            int j= i-1; 
            int x = a[i];        //復(fù)制為哨兵，即存儲待排序元素
            a[i] = a[i-1];           //先后移一個元素
            while(x < a[j]){     //查找在有序表的插入位置
                a[j+1] = a[j];
                j--;         //元素后移
            }
            a[j+1] = x;      //插入到正確位置
        }
        print(a,n,i);           //打印每趟排序的結(jié)果
    }
    
}
 
int main(){
    int a[8] = {3,1,5,7,2,4,9,6};
    InsertSort(a,8);
    print(a,8,8);
}

效率：

時間復(fù)雜度：O（n^2）.

其他的插入排序有二分插入排序，2-路插入排序。

2. 插入排序—希爾排序（Shell`s Sort）

希爾排序是1959 年由D.L.Shell 提出來的，相對直接排序有較大的改進。希爾排序又叫縮小增量排序

基本思想：

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

操作方法：

1. 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列個數(shù)k，對序列進行k 趟排序；
3. 每趟排序，根據(jù)對應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

希爾排序的示例：

算法實現(xiàn)：

我們簡單處理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n為要排序數(shù)的個數(shù)

即：先將要排序的一組記錄按某個增量d（n/2,n為要排序數(shù)的個數(shù)）分成若干組子序列，每組中記錄的下標(biāo)相差d.對每組中全部元素進行直接插入排序，然后再用一個較小的增量（d/2）對它進行分組，在每組中再進行直接插入排序。繼續(xù)不斷縮小增量直至為1，最后使用直接插入排序完成排序。

void print(int a[], int n ,int i){
    cout<<i <<":";
    for(int j= 0; j<8; j++){
        cout<<a[j] <<" ";
    }
    cout<<endl;
}
/**
 * 直接插入排序的一般形式
 *
 * @param int dk 縮小增量，如果是直接插入排序，dk=1
 *
 */
 
void ShellInsertSort(int a[], int n, int dk)
{
    for(int i= dk; i<n; ++i){
        if(a[i] < a[i-dk]){         //若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入
            int j = i-dk;   
            int x = a[i];           //復(fù)制為哨兵，即存儲待排序元素
            a[i] = a[i-dk];         //首先后移一個元素
            while(x < a[j]){        //查找在有序表的插入位置
                a[j+dk] = a[j];
                j -= dk;             //元素后移
            }
            a[j+dk] = x;            //插入到正確位置
        }
        print(a, n,i );
    }
    
}
 
/**
 * 先按增量d（n/2,n為要排序數(shù)的個數(shù)進行希爾排序
 *
 */
void shellSort(int a[], int n){
 
    int dk = n/2;
    while( dk >= 1  ){
        ShellInsertSort(a, n, dk);
        dk = dk/2;
    }
}
int main(){
    int a[8] = {3,1,5,7,2,4,9,6};
    //ShellInsertSort(a,8,1); //直接插入排序
    shellSort(a,8);           //希爾插入排序
    print(a,8,8);
}

希爾排序時效分析很難，關(guān)鍵碼的比較次數(shù)與記錄移動次數(shù)依賴于增量因子序列d的選取，特定情況下可以準(zhǔn)確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動次數(shù)。目前還沒有人給出選取最好的增量因子序列的方法。增量因子序列可以有各種取法，有取奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：增量因子中除1 外沒有公因子，且最后一個增量因子必須為1。希爾排序方法是一個不穩(wěn)定的排序方法。

3. 選擇排序—簡單選擇排序（Simple Selection Sort）

基本思想：

在要排序的一組數(shù)中，選出最?。ɑ蛘咦畲螅┑囊粋€數(shù)與第1個位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小（或者最大）的與第2個位置的數(shù)交換，依次類推，直到第n-1個元素（倒數(shù)第二個數(shù)）和第n個元素（最后一個數(shù)）比較為止。

簡單選擇排序的示例：

操作方法：

第一趟，從n 個記錄中找出關(guān)鍵碼最小的記錄與第一個記錄交換；

第二趟，從第二個記錄開始的n-1 個記錄中再選出關(guān)鍵碼最小的記錄與第二個記錄交換；

以此類推.....

第i 趟，則從第i 個記錄開始的n-i+1 個記錄中選出關(guān)鍵碼最小的記錄與第i 個記錄交換，

直到整個序列按關(guān)鍵碼有序。

算法實現(xiàn)：

void print(int a[], int n ,int i){
    cout<<"第"<<i+1 <<"趟 : ";
    for(int j= 0; j<8; j++){
        cout<<a[j] <<"  ";
    }
    cout<<endl;
}
/**
 * 數(shù)組的最小值
 *
 * @return int 數(shù)組的鍵值
 */
int SelectMinKey(int a[], int n, int i)
{
    int k = i;
    for(int j=i+1 ;j< n; ++j) {
        if(a[k] > a[j]) k = j;
    }
    return k;
}
 
/**
 * 選擇排序
 *
 */
void selectSort(int a[], int n){
    int key, tmp;
    for(int i = 0; i< n; ++i) {
        key = SelectMinKey(a, n,i);           //選擇最小的元素
        if(key != i){
            tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素與第i位置元素互換
        }
        print(a,  n , i);
    }
}
int main(){
    int a[8] = {3,1,5,7,2,4,9,6};
    cout<<"初始值：";
    for(int j= 0; j<8; j++){
        cout<<a[j] <<"  ";
    }
    cout<<endl<<endl;
    selectSort(a, 8);
    print(a,8,8);
}

簡單選擇排序的改進——二元選擇排序

簡單選擇排序，每趟循環(huán)只能確定一個元素排序后的定位。我們可以考慮改進為每趟循環(huán)確定兩個元素（當(dāng)前趟最大和最小記錄）的位置,從而減少排序所需的循環(huán)次數(shù)。改進后對n個數(shù)據(jù)進行排序，最多只需進行[n/2]趟循環(huán)即可。具體實現(xiàn)如下：

/** 這是偽函數(shù), 邏輯判斷不嚴(yán)謹(jǐn)
void selectSort(int r[],int n) {
    int i ,j , min ,max, tmp;
    for (i=1 ;i <= n/2;i++) {  
        // 做不超過n/2趟選擇排序 
        min = i; max = i ; //分別記錄最大和最小關(guān)鍵字記錄位置
        for (j= i+1; j<= n-i; j++) {
            if (r[j] > r[max]) { 
                max = j ; continue ; 
            }  
            if (r[j]< r[min]) { 
                min = j ; 
            }   
      }  
      //該交換操作還可分情況討論以提高效率
      tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;
      tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp; 
 
    } 
}
 */
void selectSort(int a[],int len) {
        int i,j,min,max,tmp;  
        for(i=0; i<len/2; i++){  // 做不超過n/2趟選擇排序 
            min = max = i;  
            for(j=i+1; j<=len-1-i; j++){  
                //分別記錄最大和最小關(guān)鍵字記錄位置
                if(a[j] > a[max]){  
                    max = j;  
                    continue;  
                }  
                if(a[j] < a[min]){  
                    min = j;  
                }  
            }  
            //該交換操作還可分情況討論以提高效率
            if(min != i){//當(dāng)?shù)谝粋€為min值，不用交換  
                tmp=a[min];  a[min]=a[i];  a[i]=tmp;  
            }  
            if(min == len-1-i && max == i)//當(dāng)?shù)谝粋€為max值，同時最后一個為min值，不再需要下面操作  
                continue;  
            if(max == i)//當(dāng)?shù)谝粋€為max值，則交換后min的位置為max值  
                max = min;  
            if(max != len-1-i){//當(dāng)最后一個為max值，不用交換  
                tmp=a[max];  a[max]=a[len-1-i];  a[len-1-i]=tmp;  
            }
            print(a,len, i);            
        }  
 }

4. 選擇排序—堆排序（Heap Sort）

堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。

基本思想：

堆的定義如下：具有n個元素的序列（k1,k2,...,kn),當(dāng)且僅當(dāng)滿足

時稱之為堆。由堆的定義可以看出，堆頂元素（即第一個元素）必為最小項（小頂堆）。
若以一維數(shù)組存儲一個堆，則堆對應(yīng)一棵完全二叉樹，且所有非葉結(jié)點的值均不大于(或不小于)其子女的值，根結(jié)點（堆頂元素）的值是最小(或最大)的。如：

（a）大頂堆序列：（96, 83,27,38,11,09)

(b) 小頂堆序列：（12，36，24，85，47，30，53，91）

初始時把要排序的n個數(shù)的序列看作是一棵順序存儲的二叉樹（一維數(shù)組存儲二叉樹），調(diào)整它們的存儲序，使之成為一個堆，將堆頂元素輸出，得到n 個元素中最小(或最大)的元素，這時堆的根節(jié)點的數(shù)最小（或者最大）。然后對前面(n-1)個元素重新調(diào)整使之成為堆，輸出堆頂元素，得到n 個元素中次小(或次大)的元素。依此類推，直到只有兩個節(jié)點的堆，并對它們作交換，最后得到有n個節(jié)點的有序序列。稱這個過程為堆排序。

因此，實現(xiàn)堆排序需解決兩個問題：
1. 如何將n 個待排序的數(shù)建成堆；
2. 輸出堆頂元素后，怎樣調(diào)整剩余n-1 個元素，使其成為一個新堆。

首先討論第二個問題：輸出堆頂元素后，對剩余n-1元素重新建成堆的調(diào)整過程。
調(diào)整小頂堆的方法：

1）設(shè)有m 個元素的堆，輸出堆頂元素后，剩下m-1 個元素。將堆底元素送入堆頂（（最后一個元素與堆頂進行交換），堆被破壞，其原因僅是根結(jié)點不滿足堆的性質(zhì)。

2）將根結(jié)點與左、右子樹中較小元素的進行交換。

3）若與左子樹交換：如果左子樹堆被破壞，即左子樹的根結(jié)點不滿足堆的性質(zhì)，則重復(fù)方法 （2）.

4）若與右子樹交換，如果右子樹堆被破壞，即右子樹的根結(jié)點不滿足堆的性質(zhì)。則重復(fù)方法 （2）.

5）繼續(xù)對不滿足堆性質(zhì)的子樹進行上述交換操作，直到葉子結(jié)點，堆被建成。

稱這個自根結(jié)點到葉子結(jié)點的調(diào)整過程為篩選。如圖：

再討論對n 個元素初始建堆的過程。
建堆方法：對初始序列建堆的過程，就是一個反復(fù)進行篩選的過程。

個結(jié)點的子樹。

個結(jié)點為根的子樹開始，該子樹成為堆。

3）之后向前依次對各結(jié)點為根的子樹進行篩選，使之成為堆，直到根結(jié)點。

如圖建堆初始過程：無序序列：（49，38，65，97，76，13，27，49）

算法的實現(xiàn)：

從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最后一個元素交換位置。所以堆排序有兩個函數(shù)組成。一是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實現(xiàn)排序的函數(shù)。

void print(int a[], int n){
    for(int j= 0; j<n; j++){
        cout<<a[j] <<"  ";
    }
    cout<<endl;
}
 
 
 
/**
 * 已知H[s…m]除了H[s] 外均滿足堆的定義
 * 調(diào)整H[s],使其成為大頂堆.即將對第s個結(jié)點為根的子樹篩選, 
 *
 * @param H是待調(diào)整的堆數(shù)組
 * @param s是待調(diào)整的數(shù)組元素的位置
 * @param length是數(shù)組的長度
 *
 */
void HeapAdjust(int H[],int s, int length)
{
    int tmp  = H[s];
    int child = 2*s+1; //左孩子結(jié)點的位置。(i+1 為當(dāng)前調(diào)整結(jié)點的右孩子結(jié)點的位置)
    while (child < length) {
        if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比當(dāng)前待調(diào)整結(jié)點大的孩子結(jié)點)
            ++child ;
        }
        if(H[s]<H[child]) {  // 如果較大的子結(jié)點大于父結(jié)點
            H[s] = H[child]; // 那么把較大的子結(jié)點往上移動，替換它的父結(jié)點
            s = child;       // 重新設(shè)置s ,即待調(diào)整的下一個結(jié)點的位置
            child = 2*s+1;
        }  else {            // 如果當(dāng)前待調(diào)整結(jié)點大于它的左右孩子，則不需要調(diào)整，直接退出
             break;
        }
        H[s] = tmp;         // 當(dāng)前待調(diào)整的結(jié)點放到比其大的孩子結(jié)點位置上
    }
    print(H,length);
}
 
 
/**
 * 初始堆進行調(diào)整
 * 將H[0..length-1]建成堆
 * 調(diào)整完之后第一個元素是序列的最小的元素
 */
void BuildingHeap(int H[], int length)
{ 
    //最后一個有孩子的節(jié)點的位置 i=  (length -1) / 2
    for (int i = (length -1) / 2 ; i >= 0; --i)
        HeapAdjust(H,i,length);
}
/**
 * 堆排序算法
 */
void HeapSort(int H[],int length)
{
    //初始堆
    BuildingHeap(H, length);
    //從最后一個元素開始對序列進行調(diào)整
    for (int i = length - 1; i > 0; --i)
    {
        //交換堆頂元素H[0]和堆中最后一個元素
        int temp = H[i]; H[i] = H[0]; H[0] = temp;
        //每次交換堆頂元素和堆中最后一個元素之后，都要對堆進行調(diào)整
        HeapAdjust(H,0,i);
  }
} 
 
int main(){
    int H[10] = {3,1,5,7,2,4,9,6,10,8};
    cout<<"初始值：";
    print(H,10);
    HeapSort(H,10);
    //selectSort(a, 8);
    cout<<"結(jié)果：";
    print(H,10);
 
}

分析:

從根到葉的篩選，元素比較次數(shù)至多2(k-1)次，交換記錄至多k 次。所以，在建好堆后，排序過程中的篩選次數(shù)不超過下式：

5. 交換排序—冒泡排序（Bubble Sort）

基本思想：

在要排序的一組數(shù)中，對當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對相鄰的兩個數(shù)依次進行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換。

冒泡排序的示例：

算法的實現(xiàn)：

void bubbleSort(int a[], int n){
    for(int i =0 ; i< n-1; ++i) {
        for(int j = 0; j < n-i-1; ++j) {
            if(a[j] > a[j+1])
            {
                int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;
            }
        }
    }
}

冒泡排序算法的改進

對冒泡排序常見的改進方法是加入一標(biāo)志性變量exchange，用于標(biāo)志某一趟排序過程中是否有數(shù)據(jù)交換，如果進行某一趟排序時并沒有進行數(shù)據(jù)交換，則說明數(shù)據(jù)已經(jīng)按要求排列好，可立即結(jié)束排序，避免不必要的比較過程。本文再提供以下兩種改進算法：

1．設(shè)置一標(biāo)志性變量pos,用于記錄每趟排序中最后一次進行交換的位置。由于pos位置之后的記錄均已交換到位,故在進行下一趟排序時只要掃描到pos位置即可。

改進后算法如下:

void Bubble_1 ( int r[], int n) {
    int i= n -1;  //初始時,最后位置保持不變
    while ( i> 0) { 
        int pos= 0; //每趟開始時,無記錄交換
        for (int j= 0; j< i; j++)
            if (r[j]> r[j+1]) {
                pos= j; //記錄交換的位置 
                int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
            } 
        i= pos; //為下一趟排序作準(zhǔn)備
     } 
}  

2．傳統(tǒng)冒泡排序中每一趟排序操作只能找到一個最大值或最小值,我們考慮利用在每趟排序中進行正向和反向兩遍冒泡的方法一次可以得到兩個最終值(最大者和最小者) , 從而使排序趟數(shù)幾乎減少了一半。

改進后的算法實現(xiàn)為:

void Bubble_2 ( int r[], int n){
    int low = 0; 
    int high= n -1; //設(shè)置變量的初始值
    int tmp,j;
    while (low < high) {
        for (j= low; j< high; ++j) //正向冒泡,找到最大者
            if (r[j]> r[j+1]) {
                tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
            } 
        --high;                 //修改high值, 前移一位
        for ( j=high; j>low; --j) //反向冒泡,找到最小者
            if (r[j]<r[j-1]) {
                tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;
            }
        ++low;                  //修改low值,后移一位
    } 
} 

6. 交換排序—快速排序（Quick Sort）

基本思想：

1）選擇一個基準(zhǔn)元素,通常選擇第一個元素或者最后一個元素,

2）通過一趟排序講待排序的記錄分割成獨立的兩部分，其中一部分記錄的元素值均比基準(zhǔn)元素值小。另一部分記錄的 元素值比基準(zhǔn)值大。

3）此時基準(zhǔn)元素在其排好序后的正確位置

4）然后分別對這兩部分記錄用同樣的方法繼續(xù)進行排序，直到整個序列有序。

快速排序的示例：

（a）一趟排序的過程：

（b）排序的全過程

算法的實現(xiàn)：

遞歸實現(xiàn)：

void print(int a[], int n){
    for(int j= 0; j<n; j++){
        cout<<a[j] <<"  ";
    }
    cout<<endl;
}
 
void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
 
int partition(int a[], int low, int high)
{
    int privotKey = a[low];                             //基準(zhǔn)元素
    while(low < high){                                  //從表的兩端交替地向中間掃描
        while(low < high  && a[high] >= privotKey) --high;  //從high 所指位置向前搜索，至多到low+1 位置。將比基準(zhǔn)元素小的交換到低端
        swap(&a[low], &a[high]);
        while(low < high  && a[low] <= privotKey ) ++low;
        swap(&a[low], &a[high]);
    }
    print(a,10);
    return low;
}
 
 
void quickSort(int a[], int low, int high){
    if(low < high){
        int privotLoc = partition(a,  low,  high);  //將表一分為二
        quickSort(a,  low,  privotLoc -1);          //遞歸對低子表遞歸排序
        quickSort(a,   privotLoc + 1, high);        //遞歸對高子表遞歸排序
    }
}
 
int main(){
    int a[10] = {3,1,5,7,2,4,9,6,10,8};
    cout<<"初始值：";
    print(a,10);
    quickSort(a,0,9);
    cout<<"結(jié)果：";
    print(a,10);
 
}

分析：

快速排序是通常被認(rèn)為在同數(shù)量級（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按關(guān)鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進之，通常以“三者取中法”來選取基準(zhǔn)記錄，即將排序區(qū)間的兩個端點與中點三個記錄關(guān)鍵碼居中的調(diào)整為支點記錄?？焖倥判蚴且粋€不穩(wěn)定的排序方法。

快速排序的改進

在本改進算法中,只對長度大于k的子序列遞歸調(diào)用快速排序,讓原序列基本有序，然后再對整個基本有序序列用插入排序算法排序。實踐證明，改進后的算法時間復(fù)雜度有所降低，且當(dāng)k取值為 8 左右時,改進算法的性能最佳。算法思想如下：

void print(int a[], int n){
    for(int j= 0; j<n; j++){
        cout<<a[j] <<"  ";
    }
    cout<<endl;
}
 
void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
 
int partition(int a[], int low, int high)
{
    int privotKey = a[low];                 //基準(zhǔn)元素
    while(low < high){                  //從表的兩端交替地向中間掃描
        while(low < high  && a[high] >= privotKey) --high; //從high 所指位置向前搜索，至多到low+1 位置。將比基準(zhǔn)元素小的交換到低端
        swap(&a[low], &a[high]);
        while(low < high  && a[low] <= privotKey ) ++low;
        swap(&a[low], &a[high]);
    }
    print(a,10);
    return low;
}
 
 
void qsort_improve(int r[ ],int low,int high, int k){
    if( high -low > k ) { //長度大于k時遞歸, k為指定的數(shù)
        int pivot = partition(r, low, high); // 調(diào)用的Partition算法保持不變
        qsort_improve(r, low, pivot - 1,k);
        qsort_improve(r, pivot + 1, high,k);
    } 
} 
void quickSort(int r[], int n, int k){
    qsort_improve(r,0,n,k);//先調(diào)用改進算法Qsort使之基本有序
 
    //再用插入排序?qū)居行蛐蛄信判?    for(int i=1; i<=n;i ++){
        int tmp = r[i]; 
        int j=i-1;
        while(tmp < r[j]){
            r[j+1]=r[j]; j=j-1; 
        }
        r[j+1] = tmp;
    } 
 
} 
 
 
 
int main(){
    int a[10] = {3,1,5,7,2,4,9,6,10,8};
    cout<<"初始值：";
    print(a,10);
    quickSort(a,9,4);
    cout<<"結(jié)果：";
    print(a,10);
 
}

7. 歸并排序（Merge Sort）

基本思想：

歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。

歸并排序示例：

合并方法：

設(shè)r[i…n]由兩個有序子表r[i…m]和r[m+1…n]組成，兩個子表長度分別為n-i +1、n-m。

1. j=m+1；k=i；i=i; //置兩個子表的起始下標(biāo)及輔助數(shù)組的起始下標(biāo)
2. 若i>m 或j>n，轉(zhuǎn)⑷ //其中一個子表已合并完，比較選取結(jié)束
3. //選取r[i]和r[j]較小的存入輔助數(shù)組rf
   如果r[i]<r[j]，rf[k]=r[i]； i++； k++； 轉(zhuǎn)⑵
   否則，rf[k]=r[j]； j++； k++； 轉(zhuǎn)⑵
4. //將尚未處理完的子表中元素存入rf
   如果i<=m，將r[i…m]存入rf[k…n] //前一子表非空
   如果j<=n , 將r[j…n] 存入rf[k…n] //后一子表非空
5. 合并結(jié)束。

//將r[i…m]和r[m +1 …n]歸并到輔助數(shù)組rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
    int j,k;
    for(j=m+1,k=i; i<=m && j <=n ; ++k){
        if(r[j] < r[i]) rf[k] = r[j++];
        else rf[k] = r[i++];
    }
    while(i <= m)  rf[k++] = r[i++];
    while(j <= n)  rf[k++] = r[j++];
}

歸并的迭代算法

1 個元素的表總是有序的。所以對n 個元素的待排序列，每個元素可看成1 個有序子表。對子表兩兩合并生成n/2個子表，所得子表除最后一個子表長度可能為1 外，其余子表長度均為2。再進行兩兩合并，直到生成n 個元素按關(guān)鍵碼有序的表。

void print(int a[], int n){
    for(int j= 0; j<n; j++){
        cout<<a[j] <<"  ";
    }
    cout<<endl;
}
 
//將r[i…m]和r[m +1 …n]歸并到輔助數(shù)組rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
    int j,k;
    for(j=m+1,k=i; i<=m && j <=n ; ++k){
        if(r[j] < r[i]) rf[k] = r[j++];
        else rf[k] = r[i++];
    }
    while(i <= m)  rf[k++] = r[i++];
    while(j <= n)  rf[k++] = r[j++];
    print(rf,n+1);
}
 
void MergeSort(ElemType *r, ElemType *rf, int lenght)
{ 
    int len = 1;
    ElemType *q = r ;
    ElemType *tmp ;
    while(len < lenght) {
        int s = len;
        len = 2 * s ;
        int i = 0;
        while(i+ len <lenght){
            Merge(q, rf,  i, i+ s-1, i+ len-1 ); //對等長的兩個子表合并
            i = i+ len;
        }
        if(i + s < lenght){
            Merge(q, rf,  i, i+ s -1, lenght -1); //對不等長的兩個子表合并
        }
        tmp = q; q = rf; rf = tmp; //交換q,rf，以保證下一趟歸并時，仍從q 歸并到rf
    }
}
 
 
int main(){
    int a[10] = {3,1,5,7,2,4,9,6,10,8};
    int b[10];
    MergeSort(a, b, 10);
    print(b,10);
    cout<<"結(jié)果：";
    print(a,10);
 
}

兩路歸并的遞歸算法

void MSort(ElemType *r, ElemType *rf,int s, int t)
{ 
    ElemType *rf2;
    if(s==t) r[s] = rf[s];
    else
    { 
        int m=(s+t)/2;          /*平分*p 表*/
        MSort(r, rf2, s, m);        /*遞歸地將p[s…m]歸并為有序的p2[s…m]*/
        MSort(r, rf2, m+1, t);      /*遞歸地將p[m+1…t]歸并為有序的p2[m+1…t]*/
        Merge(rf2, rf, s, m+1,t);   /*將p2[s…m]和p2[m+1…t]歸并到p1[s…t]*/
    }
}
void MergeSort_recursive(ElemType *r, ElemType *rf, int n)
{   /*對順序表*p 作歸并排序*/
    MSort(r, rf,0, n-1);
}

8. 桶排序/基數(shù)排序(Radix Sort)

說基數(shù)排序之前，我們先說桶排序：

基本思想：是將陣列分到有限數(shù)量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞回方式繼續(xù)使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序的陣列內(nèi)的數(shù)值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。
簡單來說，就是把數(shù)據(jù)分組，放在一個個的桶中，然后對每個桶里面的在進行排序。

例如要對大小為[1..1000]范圍內(nèi)的n個整數(shù)A[1..n]排序

首先，可以把桶設(shè)為大小為10的范圍，具體而言，設(shè)集合B[1]存儲[1..10]的整數(shù)，集合B[2]存儲 (10..20]的整數(shù)，……集合B[i]存儲( (i-1)10, i10]的整數(shù)，i = 1,2,..100。總共有 100個桶。

然后，對A[1..n]從頭到尾掃描一遍，把每個A[i]放入對應(yīng)的桶B[j]中。 再對這100個桶中每個桶里的數(shù)字排序，這時可用冒泡，選擇，乃至快排，一般來說任 何排序法都可以。

最后，依次輸出每個桶里面的數(shù)字，且每個桶中的數(shù)字從小到大輸出，這 樣就得到所有數(shù)字排好序的一個序列了。

假設(shè)有n個數(shù)字，有m個桶，如果數(shù)字是平均分布的，則每個桶里面平均有n/m個數(shù)字。如果

對每個桶中的數(shù)字采用快速排序，那么整個算法的復(fù)雜度是

O(n + m * n/m*log(n/m)) = O(n + nlogn - nlogm)

從上式看出，當(dāng)m接近n的時候，桶排序復(fù)雜度接近O(n)

當(dāng)然，以上復(fù)雜度的計算是基于輸入的n個數(shù)字是平均分布這個假設(shè)的。這個假設(shè)是很強的 ，實際應(yīng)用中效果并沒有這么好。如果所有的數(shù)字都落在同一個桶中，那就退化成一般的排序了。

前面說的幾大排序算法 ，大部分時間復(fù)雜度都是O（n2），也有部分排序算法時間復(fù)雜度是O(nlogn)。而桶式排序卻能實現(xiàn)O（n）的時間復(fù)雜度。但桶排序的缺點是：

1）首先是空間復(fù)雜度比較高，需要的額外開銷大。排序有兩個數(shù)組的空間開銷，一個存放待排序數(shù)組，一個就是所謂的桶，比如待排序值是從0到m-1，那就需要m個桶，這個桶數(shù)組就要至少m個空間。
2）其次待排序的元素都要在一定的范圍內(nèi)等等。

桶式排序是一種分配排序。分配排序的特定是不需要進行關(guān)鍵碼的比較，但前提是要知道待排序列的一些具體情況。

分配排序的基本思想：說白了就是進行多次的桶式排序。****

基數(shù)排序過程無須比較關(guān)鍵字，而是通過“分配”和“收集”過程來實現(xiàn)排序。它們的時間復(fù)雜度可達(dá)到線性階：O(n)。

實例:

撲克牌中52 張牌，可按花色和面值分成兩個字段，其大小關(guān)系為：
花色： 梅花< 方塊< 紅心< 黑心
面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

若對撲克牌按花色、面值進行升序排序，得到如下序列：

即兩張牌，若花色不同，不論面值怎樣，花色低的那張牌小于花色高的，只有在同花色情況下，大小關(guān)系才由面值的大小確定。這就是多關(guān)鍵碼排序。

為得到排序結(jié)果，我們討論兩種排序方法。
方法1：先對花色排序，將其分為4 個組，即梅花組、方塊組、紅心組、黑心組。再對每個組分別按面值進行排序，最后，將4 個組連接起來即可。
方法2：先按13 個面值給出13 個編號組(2 號，3 號，...，A 號)，將牌按面值依次放入對應(yīng)的編號組，分成13 堆。再按花色給出4 個編號組(梅花、方塊、紅心、黑心)，將2號組中牌取出分別放入對應(yīng)花色組，再將3 號組中牌取出分別放入對應(yīng)花色組，……，這樣，4 個花色組中均按面值有序，然后，將4 個花色組依次連接起來即可。

設(shè)n 個元素的待排序列包含d 個關(guān)鍵碼{k1，k2，…，kd}，則稱序列對關(guān)鍵碼{k1，k2，…，kd}有序是指：對于序列中任兩個記錄r[i]和rj都滿足下列有序關(guān)系：

其中k1 稱為最主位關(guān)鍵碼，kd 稱為最次位關(guān)鍵碼 。

兩種多關(guān)鍵碼排序方法：

多關(guān)鍵碼排序按照從最主位關(guān)鍵碼到最次位關(guān)鍵碼或從最次位到最主位關(guān)鍵碼的順序逐次排序，分兩種方法：

最高位優(yōu)先(Most Significant Digit first)法，簡稱MSD 法：

1）先按k1 排序分組，將序列分成若干子序列，同一組序列的記錄中，關(guān)鍵碼k1 相等。

2）再對各組按k2 排序分成子組，之后，對后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd 對各子組排序后。

3）再將各組連接起來，便得到一個有序序列。撲克牌按花色、面值排序中介紹的方法一即是MSD 法。

最低位優(yōu)先(Least Significant Digit first)法，簡稱LSD 法：

1. 先從kd 開始排序，再對kd-1進行排序，依次重復(fù)，直到按k1排序分組分成最小的子序列后。

2. 最后將各個子序列連接起來，便可得到一個有序的序列, 撲克牌按花色、面值排序中介紹的方法二即是LSD 法。

基于LSD方法的鏈?zhǔn)交鶖?shù)排序的基本思想

“多關(guān)鍵字排序”的思想實現(xiàn)“單關(guān)鍵字排序”。對數(shù)字型或字符型的單關(guān)鍵字，可以看作由多個數(shù)位或多個字符構(gòu)成的多關(guān)鍵字，此時可以采用“分配-收集”的方法進行排序，這一過程稱作基數(shù)排序法，其中每個數(shù)字或字符可能的取值個數(shù)稱為基數(shù)。比如，撲克牌的花色基數(shù)為4，面值基數(shù)為13。在整理撲克牌時，既可以先按花色整理，也可以先按面值整理。按花色整理時，先按紅、黑、方、花的順序分成4摞（分配），再按此順序再疊放在一起（收集），然后按面值的順序分成13摞（分配），再按此順序疊放在一起（收集），如此進行二次分配和收集即可將撲克牌排列有序。

基數(shù)排序:

是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序，再按高優(yōu)先級排序。最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu)先級高的在前?；鶖?shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。

算法實現(xiàn)：

Void RadixSort(Node L[],length,maxradix)
{
   int m,n,k,lsp;
   k=1;m=1;
   int temp[10][length-1];
   Empty(temp); //清空臨時空間
   while(k<maxradix) //遍歷所有關(guān)鍵字
   {
     for(int i=0;i<length;i++) //分配過程
    {
       if(L[i]<m)
          Temp[0][n]=L[i];
       else
          Lsp=(L[i]/m)%10; //確定關(guān)鍵字
       Temp[lsp][n]=L[i];
       n++;
   }
   CollectElement(L,Temp); //收集
   n=0;
   m=m*10;
  k++;
 }
}

總結(jié)

各種排序的穩(wěn)定性，時間復(fù)雜度和空間復(fù)雜度總結(jié)：

我們比較時間復(fù)雜度函數(shù)的情況：

時間復(fù)雜度函數(shù)O(n)的增長情況

所以對n較大的排序記錄。一般的選擇都是時間復(fù)雜度為O(nlog2n)的排序方法。

時間復(fù)雜度來說：

(1)平方階(O(n²))排序
各類簡單排序:直接插入、直接選擇和冒泡排序；
(2)線性對數(shù)階(O(nlog2n))排序 　　
快速排序、堆排序和歸并排序；
(3)O(n^1+§))排序,§是介于0和1之間的常數(shù)。
希爾排序
(4)線性階(O(n))排序
基數(shù)排序，此外還有桶、箱排序。

說明：

當(dāng)原表有序或基本有序時，直接插入排序和冒泡排序?qū)⒋蟠鬁p少比較次數(shù)和移動記錄的次數(shù)，時間復(fù)雜度可降至O（n）；

而快速排序則相反，當(dāng)原表基本有序時，將蛻化為冒泡排序，時間復(fù)雜度提高為O（n2）；

原表是否有序，對簡單選擇排序、堆排序、歸并排序和基數(shù)排序的時間復(fù)雜度影響不大。

穩(wěn)定性：

排序算法的穩(wěn)定性:若待排序的序列中，存在多個具有相同關(guān)鍵字的記錄，經(jīng)過排序， 這些記錄的相對次序保持不變，則稱該算法是穩(wěn)定的；若經(jīng)排序后，記錄的相對 次序發(fā)生了改變，則稱該算法是不穩(wěn)定的。
穩(wěn)定性的好處：排序算法如果是穩(wěn)定的，那么從一個鍵上排序，然后再從另一個鍵上排序，第一個鍵排序的結(jié)果可以為第二個鍵排序所用。基數(shù)排序就是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的。另外，如果排序算法穩(wěn)定，可以避免多余的比較；

穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序

不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序

選擇排序算法準(zhǔn)則：

每種排序算法都各有優(yōu)缺點。因此，在實用時需根據(jù)不同情況適當(dāng)選用，甚至可以將多種方法結(jié)合起來使用。

選擇排序算法的依據(jù)

影響排序的因素有很多，平均時間復(fù)雜度低的算法并不一定就是最優(yōu)的。相反，有時平均時間復(fù)雜度高的算法可能更適合某些特殊情況。同時，選擇算法時還得考慮它的可讀性，以利于軟件的維護。一般而言，需要考慮的因素有以下四點：

1．待排序的記錄數(shù)目n的大??；

2．記錄本身數(shù)據(jù)量的大小，也就是記錄中除關(guān)鍵字外的其他信息量的大??；

3．關(guān)鍵字的結(jié)構(gòu)及其分布情況；

4．對排序穩(wěn)定性的要求。

設(shè)待排序元素的個數(shù)為n.

1）當(dāng)n較大，則應(yīng)采用時間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。

快速排序：是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機分布時，快速排序的平均時間最短；
堆排序 ： 如果內(nèi)存空間允許且要求穩(wěn)定性的，
歸并排序：它有一定數(shù)量的數(shù)據(jù)移動，所以我們可能過與插入排序組合，先獲得一定長度的序列，然后再合并，在效率上將有所提高。

2） 當(dāng)n較大，內(nèi)存空間允許，且要求穩(wěn)定性 =》歸并排序

3）當(dāng)n較小，可采用直接插入或直接選擇排序。

直接插入排序：當(dāng)元素分布有序，直接插入排序?qū)⒋蟠鬁p少比較次數(shù)和移動記錄的次數(shù)。
直接選擇排序 ：元素分布有序，如果不要求穩(wěn)定性，選擇直接選擇排序

5）一般不使用或不直接使用傳統(tǒng)的冒泡排序。

6）基數(shù)排序 它是一種穩(wěn)定的排序算法，但有一定的局限性：
1、關(guān)鍵字可分解。
2、記錄的關(guān)鍵字位數(shù)較少，如果密集更好 　　
3、如果是數(shù)字時，最好是無符號的，否則將增加相應(yīng)的映射復(fù)雜度，可先將其正負(fù)分開排序。