我們這里說說八大排序就是內部排序。

排序算法：一種能將一串數(shù)據依照特定的排序方式進行排列的一種算法。
排序算法性能：取決于時間和空間復雜度，其次還得考慮穩(wěn)定性，及其適應的場景。
穩(wěn)定性：讓原本有相等鍵值的記錄維持相對次序。也就是若一個排序算法是穩(wěn)定的，當有倆個相等鍵值的記錄R和S，且原本的序列中R在S前，那么排序后的列表中R應該也在S之前。

以下來總結常用的排序算法，加深對排序的理解。

排序算法目錄

• 冒泡排序
• 插入排序
• 希爾排序
• 選擇排序
• 快速排序
• 歸并排序
• 堆排序
• 計數(shù)排序
• 桶排序
• 基數(shù)排序
• 總結

冒泡排序

原理

倆倆比較相鄰記錄的排序碼，若發(fā)生逆序，則交換；有倆種方式進行冒泡，一種是先把小的冒泡到前邊去，另一種是把大的元素冒泡到后邊。

性能

時間復雜度為O(N^2)，空間復雜度為O(1)。排序是穩(wěn)定的，排序比較次數(shù)與初始序列無關，但交換次數(shù)與初始序列有關。

優(yōu)化

若初始序列就是排序好的，對于冒泡排序仍然還要比較O(N^2)次，但無交換次數(shù)?？筛鶕@個進行優(yōu)化，設置一個flag，當在一趟序列中沒有發(fā)生交換，則該序列已排序好，但優(yōu)化后排序的時間復雜度沒有發(fā)生量級的改變。

代碼

void bubble_sort(int arr[], int len){
//每次從后往前冒一個最小值，且每次能確定一個數(shù)在序列中的最終位置
    for (int i = 0; i < len-1; i++){         //比較n-1次
        bool exchange = true;               //冒泡的改進，若在一趟中沒有發(fā)生逆序，則該序列已有序
        for (int j = len-1; j >i; j--){    // 每次從后邊冒出一個最小值
            if (arr[j] < arr[j - 1]){       //發(fā)生逆序，則交換
                swap(arr[j], arr[j - 1]);
                exchange = false;
            }
        }
        if (exchange){
            return;
        }
    }
}

冒泡排序的示例：

算法的實現(xiàn)：

冒泡排序算法的改進

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

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

改進后算法如下:

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

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

原理

依次選擇一個待排序的數(shù)據，插入到前邊已排好序的序列中。
基本思想:將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數(shù)增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。
要點：設立哨兵，作為臨時存儲和判斷數(shù)組邊界之用。

性能

時間復雜度為O(N^2)，空間復雜度為O(1)。算法是穩(wěn)定的，比較次數(shù)和交換次數(shù)都與初始序列有關。

優(yōu)化

直接插入排序每次往前插入時，是按順序依次往前找，可在這里進行優(yōu)化，往前找合適的插入位置時采用二分查找的方式，即折半插入。
折半插入排序相對直接插入排序而言：平均性能更快，時間復雜度降至O(NlogN)，排序是穩(wěn)定的，但排序的比較次數(shù)與初始序列無關，總是需要foor(log(i))+1次排序比較。

使用場景

當數(shù)據基本有序時，采用插入排序可以明顯減少數(shù)據交換和數(shù)據移動次數(shù)，進而提升排序效率。
 

直接插入排序示例：

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

代碼

void insert_sort(int arr[], int len){
//每次把當前的數(shù)往前插入，可以順序插入，改進的可以進行二分插入
    for (int i = 1; i < len; i++){
        if (arr[i] < arr[i - 1]){      //發(fā)生逆序，往前插入
            int temp = arr[i];
            int j;
            for (j = i - 1;j>=0 && arr[j]>temp; j--){
                arr[j+1] = arr[j];
            }
            arr[j+1] = temp;
        }
    }
}

void insert_binary_sort(int arr[], int len){
    //改進的插入排序，往前插入比較時，進行二分查找
    for (int i = 1; i < len; i++){
        if (arr[i] < arr[i - 1]){
            int temp = arr[i];
            int low = 0, high = i - 1, mid;
            while (low <= high){
                mid = (low + high) / 2;
                if (temp < arr[mid]){
                    high = mid - 1;
                }
                else{
                    low = mid + 1;
                }
            }
            for (int j = i; j >low; j--){
                arr[j] = arr[j - 1];
            }
            arr[low] = temp;
        }
    }
}

希爾排序

原理

插入排序的改進版，是基于插入排序的以下倆點性質而提出的改進方法：

• 插入排序對幾乎已排好序的數(shù)據操作時，效率很高，可以達到線性排序的效率。
• 但插入排序在每次往前插入時只能將數(shù)據移動一位，效率比較低。

所以希爾排序的思想是：

• 先是取一個合適的gap<n作為間隔，將全部元素分為gap個子序列，所有距離為gap的元素放入同一個子序列，再對每個子序列進行直接插入排序；
• 縮小間隔gap，例如去gap=ceil(gap/2)，重復上述子序列劃分和排序
• 直到，最后gap=1時，將所有元素放在同一個序列中進行插入排序為止。

性能

開始時，gap取值較大，子序列中的元素較少，排序速度快，克服了直接插入排序的缺點；其次，gap值逐漸變小后，雖然子序列的元素逐漸變多，但大多元素已基本有序，所以繼承了直接插入排序的優(yōu)點，能以近線性的速度排好序。
 

希爾排序的示例：

代碼

void shell_sort(int arr[], int len){
    //每次選擇一個gap，對相隔gap的數(shù)進行插入排序
    for (int gap = len / 2; gap > 0; gap /= 2){
        for (int i = 0; i < len; i = i + gap){
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && temp < arr[j-gap]; j -= gap){
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

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

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

原理

每次從未排序的序列中找到最小值，記錄并最后存放到已排序序列的末尾

性能

時間復雜度為O(N^2)，空間復雜度為O(1)，排序是不穩(wěn)定的（把最小值交換到已排序的末尾導致的），每次都能確定一個元素所在的最終位置，比較次數(shù)與初始序列無關。
 

簡單選擇排序的示例：

操作方法：

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

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

以此類推.....

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

直到整個序列按關鍵碼有序。

代碼

void select_sort(int arr[], int len){
    //每次從后邊選擇一個最小值
    for (int i = 0; i < len-1; i++){     //只需選擇n-1次
        int min = i;
        for (int j = i+1; j < len; j++){
            if (arr[min]>arr[j]){
                min = j;
            }
        }
        if (min != i){
            swap(arr[i], arr[min]);
        }
    }
}

快速排序

原理

分而治之思想：

• Divide：找到基準元素pivot，將數(shù)組A[p..r]劃分為A[p..pivotpos-1]和A[pivotpos+1...q]，左邊的元素都比基準小，右邊的元素都比基準大;
• Conquer：對倆個劃分的數(shù)組進行遞歸排序；
• Combine：因為基準的作用，使得倆個子數(shù)組就地有序，無需合并操作。

性能

快排的平均時間復雜度為O(NlogN），空間復雜度為O(logN)，但最壞情況下，時間復雜度為O(N^2)，空間復雜度為O(N)；且排序是不穩(wěn)定的，但每次都能確定一個元素所在序列中的最終位置，復雜度與初始序列有關。

優(yōu)化

當初始序列是非遞減序列時，快排性能下降到最壞情況，主要因為基準每次都是從最左邊取得，這時每次只能排好一個元素。
所以快排的優(yōu)化思路如下：

• 優(yōu)化基準，不每次都從左邊取，可以進行三路劃分，分別取最左邊，中間和最右邊的中間值，再交換到最左邊進行排序；或者進行隨機取得待排序數(shù)組中的某一個元素，再交換到最左邊，進行排序。
• 在規(guī)模較小情況下，采用直接插入排序

快速排序的示例：

（a）一趟排序的過程：

（b）排序的全過程

//快速排序
int partition(int arr[], const int left, const int right){
    //對序列進行劃分，以第一個為基準
    int pivot = arr[left];
    int pivotpos = left;
    for (int i = left+1; i <= right; i++){
        if (arr[i] < pivot){
            pivotpos++;
            if (pivotpos != i){     //如果交換元素就位于基準后第一個，則不需要交換
                swap(arr[i], arr[pivotpos]);
            }
        }
    }
    arr[left] = arr[pivotpos];
    arr[pivotpos] = pivot;
    return pivotpos;
}
void quick_sort(int arr[],const int left,const int right){
    if (left < right){
        int pivotpos = partition(arr, left, right);
        quick_sort(arr, left, pivotpos - 1);
        quick_sort(arr, pivotpos + 1, right);
    }
}
void quick_sort(int arr[], int len){
    quick_sort(arr, 0, len - 1);
}

int improve_partition(int arr[], int left, int right){
    //基準進行隨機化處理
    int n = right - left + 1;
    srand(time((unsigned)0));
    int gap = rand() % n;
    swap(arr[left], arr[left + gap]);  //把隨機化的基準與左邊進行交換
    //再從左邊開始進行
    return partition(arr,left,right);
}
void quick_improve_sort(int arr[], const int left, const int right){
    //改進的快速排序
    //改進的地方：1、在規(guī)模較小時采用插入排序
    //2、基準進行隨機選擇
    int M = 5;
    if (right - left < M){
        insert_sort(arr, right-left+2);
    }
    if (left>=right){
        return;
    }
    int pivotpos = improve_partition(arr, left, right);
    quick_improve_sort(arr, left, pivotpos - 1);
    quick_improve_sort(arr, pivotpos + 1, right);
}
void quick_improve_sort(int arr[], int len){
    quick_improve_sort(arr, 0, len - 1);
}

歸并排序

原理

分而治之思想：

• Divide：將n個元素平均劃分為各含n/2個元素的子序列；
• Conquer：遞歸的解決倆個規(guī)模為n/2的子問題；
• Combine：合并倆個已排序的子序列。

性能

時間復雜度總是為O(NlogN)，空間復雜度也總為為O(N)，算法與初始序列無關，排序是穩(wěn)定的。

優(yōu)化

優(yōu)化思路：

• 在規(guī)模較小時，合并排序可采用直接插入；
• 在寫法上，可以在生成輔助數(shù)組時，倆頭小，中間大，這時不需要再在后邊加倆個while循環(huán)進行判斷，只需一次比完。

代碼

//歸并排序
void merge(int arr[],int temp_arr[],int left,int mid, int right){
    //簡單歸并：先復制到temp_arr，再進行歸并
    for (int i = left; i <= right; i++){
        temp_arr[i] = arr[i];
    }
    int pa = left, pb = mid + 1;
    int index = left;
    while (pa <= mid && pb <= right){
        if (temp_arr[pa] <= temp_arr[pb]){
            arr[index++] = temp_arr[pa++];
        }
        else{
            arr[index++] = temp_arr[pb++];
        }
    }
    while(pa <= mid){
        arr[index++] = temp_arr[pa++];
    }
    while (pb <= right){
        arr[index++] = temp_arr[pb++];
    }
}
void merge_improve(int arr[], int temp_arr[], int left, int mid, int right){
    //優(yōu)化歸并：復制時，倆頭小，中間大，一次比較完
    for (int i = left; i <= mid; i++){
        temp_arr[i] = arr[i];
    }
    for (int i = mid + 1; i <= right; i++){
        temp_arr[i] = arr[right + mid + 1 - i];
    }
    int pa = left, pb = right, p = left;
    while (p <= right){
        if (temp_arr[pa] <= temp_arr[pb]){
            arr[p++] = temp_arr[pa++];
        }else{
            arr[p++] = temp_arr[pb--];
        }
    }
}
void merge_sort(int arr[],int temp_arr[], int left, int right){
    if (left < right){
        int mid = (left + right) / 2;
        merge_sort(arr,temp_arr,0, mid);
        merge_sort(arr, temp_arr,mid + 1, right);
        merge(arr,temp_arr,left,mid,right);
    }
}

void merge_sort(int arr[], int len){
    int *temp_arr = (int*)malloc(sizeof(int)*len);
    merge_sort(arr,temp_arr, 0, len - 1);
}

堆排序

原理

堆的性質：

• 是一棵完全二叉樹
• 每個節(jié)點的值都大于或等于其子節(jié)點的值，為最大堆；反之為最小堆。

堆排序思想：

• 將待排序的序列構造成一個最大堆，此時序列的最大值為根節(jié)點
• 依次將根節(jié)點與待排序序列的最后一個元素交換
• 再維護從根節(jié)點到該元素的前一個節(jié)點為最大堆，如此往復，最終得到一個遞增序列

性能

時間復雜度為O(NlogN)，空間復雜度為O(1)，因為利用的排序空間仍然是初始的序列，并未開辟新空間。算法是不穩(wěn)定的，與初始序列無關。

使用場景

想知道最大值或最小值時，比如優(yōu)先級隊列，作業(yè)調度等場景。

代碼

void shiftDown(int arr[], int start, int end){  
    //從start出發(fā)到end，調整為最大堆
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end){
        //先選取子節(jié)點中較大的
        if (son + 1 <= end && arr[son] < arr[son + 1]){
            son++;
        }
        //若子節(jié)點比父節(jié)點大，則交換，繼續(xù)往子節(jié)點尋找；否則退出
        if (arr[dad] < arr[son]){
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
        else{
            break;
        }
    }
}
void heap_sort(int arr[], int len){
    //先調整為最大堆，再依次與第一個交換，進行調整，最后構成最小堆
    for (int i = (len - 2) / 2; i >= 0; i--){   //len為總長度，最后一個為len-1,所以父節(jié)點為    (len-1-1)/2
        shiftDown(arr,i,len-1);
    }
    for (int i = len - 1; i >= 0; i--){
        swap(arr[i], arr[0]);
        shiftDown(arr, 0,i-1);
    }
}

計數(shù)排序

原理

先把每個元素的出現(xiàn)次數(shù)算出來，然后算出該元素所在最終排好序列中的絕對位置(最終位置)，再依次把初始序列中的元素，根據該元素所在最終的絕對位置移到排序數(shù)組中。

性能

時間復雜度為O(N+K)，空間復雜度為O(N+K)，算法是穩(wěn)定的，與初始序列無關，不需要進行比較就能排好序的算法。

使用場景

算法只能使用在已知序列中的元素在0-k之間，且要求排序的復雜度在線性效率上。

代碼

//計數(shù)排序
void count_sort(int arr[],int sorted_arr[],int len,int k){
    //數(shù)組中的元素大小為0-k，
    //先統(tǒng)計每個數(shù)的相對位置，再算出該數(shù)所在序列中排序后的絕對位置
    int *count_arr = (int*)malloc(sizeof(int)*(k+1));
    for (int i = 0; i <= k; i++){
        count_arr[i] = 0;
    }
    for (int i = 0; i < len; i++){       //每個元素的相對位置
        count_arr[arr[i]]++;
    }
    for (int i = 1; i <= k; i++){       //每個元素的絕對位置，位置為第1個到n個
        count_arr[i] += count_arr[i - 1];
    }
    for (int i = len-1; i >=0; i--){     //從后往前，可使排序穩(wěn)定，相等的倆個數(shù)的位置不會發(fā)    生逆序
        count_arr[arr[i]]--;             //把在排序后序列中絕對位置為1-n的數(shù)依次放入到0-    (n-1)中
        sorted_arr[count_arr[arr[i]]] = arr[i];
    }
    free(count_arr);
}

桶排序

原理

• 根據待排序列元素的大小范圍，均勻獨立的劃分M個桶
• 將N個輸入元素分布到各個桶中去
• 再對各個桶中的元素進行排序
• 此時再按次序把各桶中的元素列出來即是已排序好的。
  

性能

時間復雜度為O(N+C)，O(C)=O(M(N/M)log(N/M))=O(NlogN-NlogM)，空間復雜度為O(N+M)，算法是穩(wěn)定的，且與初始序列無關。

使用場景

算法思想和散列中的開散列法差不多，當沖突時放入同一個桶中；可應用于數(shù)據量分布比較均勻，或比較側重于區(qū)間數(shù)量時。

基數(shù)排序

原理

對于有d個關鍵字時，可以分別按關鍵字進行排序。有倆種方法：

• MSD：先從高位開始進行排序，在每個關鍵字上，可采用計數(shù)排序
• LSD：先從低位開始進行排序，在每個關鍵字上，可采用桶排序
   

性能

時間復雜度為O(d*(N+K))，空間復雜度為O(N+K)。

總結

以上排序算法的時間、空間與穩(wěn)定性的總結如下：

• 算法