面試官愛問的10大經典排序算法，20+張圖來搞定

冒泡排序

簡介

冒泡排序是因為越小的元素會經由交換以升序或降序的方式慢慢浮到數列的頂端，就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名冒泡排序。

復雜度與穩(wěn)定性

思路原理

以順序為例

1. 從第一個元素開始一個一個的比較相鄰的元素，如果第一個比第二個大即a[1]>a[2]，就彼此交換。

2. 從第一對到最后一對，對每一對相鄰元素做一樣的操作。此時在最后的元素應該會是最大的數，我們也稱呼一遍這樣的操作為一趟冒泡排序。

3. 針對所有的元素重復以上的步驟，每一趟得到的最大值已放在最后，下一次操作則不需要將此最大值納入計算。

4. 持續(xù)對每次對越來越少的元素，重復上面的步驟。

5. 直到所有的數字都比較完成符合a[i]<a[i+1]，即完成冒泡排序。

圖示過程

以數組數據{ 70,50,30,20,10,70,40,60}為例：

如圖，每一次排序把一個最大的數被放在了最后，然后按照這個趨勢逐漸往前，直到按從小到大的順序依次排序。

到了第4輪的時候，整個數據已經排序結束了，但此時程序仍然在進行。

直到第5，6，7輪程序才算真正的結束，這其實是一種浪費算力的表現。

主要代碼實現

void bubble_sort(int a[],int n) {
    for(int i=0; i<n; i++) {
        for(int j=0; j<n-i; j++) {
            if(a[j]>a[j+1]) {
                swap(a[j],a[j+1]);  //交換數據
            }
        }
    }
}

注意，由于C++的namespace std命名空間的使用，std自帶了交換函數swap(a,b)，可以直接使用，其功能是交換a與b的兩個值，當然你可以自定義swap函數，其模板代碼為：

template<class T>        //模板類，可以讓參數為任意類型
void swap(T &a,T &b) {
    T c(a);
    a=b;
    b=c;
}

或者指定類型修改為整形，如：

void swap(int &a, int &b) { //指定類型
    int temp = a;
    a = b;
    b = temp;
}

選擇排序

簡介

選擇排序是一種簡單直觀的排序算法，它從待排序的數據元素中選出最小或最大的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小或最大元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數據元素的個數為零。

復雜度與穩(wěn)定性

過程介紹（以順序為例）

1. 首先設置兩個記錄i和j，i從數組第一個元素開始，j從(i+1)個元素開始。

2. 接著j遍歷整個數組，選出整個數組最小的值，并讓這個最小的值和i的位置交換。

3. i選中下一個元素(i++)，重復進行每一趟選擇排序。

4. 持續(xù)上述步驟，使得i到達(n-1)處，即完成排序 。

圖示過程：

以數據{2,10,9,4,8,1,6,5}為例

如圖所示，每次交換的數據使用紅顏色標記出，已經排好序的數據使用藍底標注，

每一趟從待排序的數據元素中選出最小的一個元素，順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。

我們只需要進行n-1趟排序即可，因為最后剩下的一個數據一定是整體數據中最大的數據。

代碼實現

void select_sort(int a[],int n){
    int temp;
    for(int i=0;i<n-1;i++){
        temp=i;      //利用一個中間變量temp來記錄需要交換元素的位置
        for(int j=i+1;j<n;j++){
            if(a[temp]>a[j]){   //選出待排數據中的最小值
                temp=j;  
            }
        }
        swap(a[i],a[temp]); //交換函數
    }
} 

相比冒泡排序的不斷交換，簡單選擇排序是等到合適的關鍵字出現后再進行交換，并且交換一次就可以達到一次冒泡的效果。

插入排序

簡介

插入排序是一種最簡單的排序方法，對于少量元素的排序，它是一個有效的算法。

復雜度與穩(wěn)定性

過程介紹

首先將一個記錄插入到已經排好序的有序表中，從而一個新的、記錄數增1的有序表。

每一步將一個待排序的元素，按其排序碼的大小，插入到前面已經排好序的一組元素的適當位置上去，直到元素全部插入為止。

可以選擇不同的方法在已經排好序數據表中尋找插入位置。根據查找方法不同，有多種插入排序方法，下面要介紹的是直接插入排序。

1. 每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序。

2. 第一趟比較前兩個數，然后把第二個數按大小插入到有序表中；

3. 第二趟把第三個數據與前兩個數從后向前掃描，把第三個數按大小插入到有序表中；

4. 依次進行下去，進行了(n-1)趟掃描以后就完成了整個排序過程。

圖示過程

以數組數據{ 70,50,30,20,10,70,40,60}為例：

將紅色的數據依次插入組成一個逐漸有序的數組

代碼實現

void insert_sort(int a[],int n) {
    int i,j;
    //外層循環(huán)標識并決定待比較的數值
    for(i=1; i<n; i++) { //循環(huán)從第2個元素開始
        if(a[i]<a[i-1]) {
            int temp=a[i];
            //待比較數值確定其最終位置
            for(j=i-1; j>=0 && a[j]>temp; j--) {
                a[j+1]=a[j];
            }
            a[j+1]=temp;//此處就是a[j+1]=temp;
        }
    }
}

希爾排序

簡介

希爾排序又稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。

希爾排序是非穩(wěn)定排序算法，在對幾乎已經排好序的數據操作時，效率極高，即可以達到線性排序的效率。

復雜度與穩(wěn)定性

過程介紹

先將整個待排序的記錄序列分組，對若干子序列分別進行直接插入排序，隨著增量逐漸減少即整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

過程如下：

1. 選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

2. 按增量序列個數 k，對序列進行 k 趟排序；

3. 每趟排序，根據對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。

4. 僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

圖示過程

可以看見，相比直接插入排序由于可以每趟進行分段操作，故整體效率體現較高。

主要代碼實現

void shellSort(int arr[], int n) {
    int i, j, gap;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = 0; i < gap; i++) {
            for (j = i + gap; j < n; j += gap) {
                for (int k = j; k > i && arr[k] < arr[k-gap]; k -= gap) {
                    swap(arr[k-gap], arr[k]);
                }
            }
        }
    }
}

堆排序

簡介

堆排序是指利用堆這種數據結構所設計的一種排序算法，它是一個近似完全二叉樹的結構。

同時堆滿足堆積的性質：即子結點的鍵值或索引總是小于或大于它的父節(jié)點。

復雜度與穩(wěn)定性

什么是堆？

由于堆排序比較特殊，我們先了解一下堆是什么。

堆是一種非線性的數據結構，其實就是利用完全二叉樹的結構來維護的一維數組，利用這種結構可以快速訪問到需要的值，堆可以分為大頂堆和小頂堆。

• 大頂堆：每個結點的值都大于或等于其左右孩子結點的值

• 小頂堆：每個結點的值都小于或等于其左右孩子結點的值

過程介紹

首先把待排序的元素按照大小在二叉樹位置上排列，且要滿足堆的特性，如果根節(jié)點存放的是最大的數，則叫做大根堆，反之就叫做小根堆了。

根據這個特性就可以把根節(jié)點拿出來，然后再堆化下，即用父節(jié)點和他的孩子節(jié)點進行比較，取最大的孩子節(jié)點和其進行交換，再把根節(jié)點拿出來，一直循環(huán)到最后一個節(jié)點，就排序好了。

由于堆的實現圖解需要很長篇幅，故這里不畫圖，肖遙會單獨出一篇堆的圖解，感謝關注。其代碼實現如下。

主要代碼實現

/* Function: 交換交換根節(jié)點和數組末尾元素的值*/
void Swap(int *heap, int len) {
    int temp;
  
    temp = heap[0];
    heap[0] = heap[len-1];
    heap[len-1] = temp;
}
  
/* Function: 構建大頂堆 */
void BuildMaxHeap(int *heap, int len) {
    int i,temp;
    for (i = len/2-1; i >= 0; i--) {
        if ((2*i+1) < len && heap[i] < heap[2*i+1]) {  /* 根節(jié)點大于左子樹 */
            temp = heap[i];
            heap[i] = heap[2*i+1];
            heap[2*i+1] = temp;
            /* 檢查交換后的左子樹是否滿足大頂堆性質 如果不滿足 則重新調整子樹結構 */
            if ((2*(2*i+1)+1 < len && heap[2*i+1] < heap[2*(2*i+1)+1]) || (2*(2*i+1)+2 < len && heap[2*i+1] < heap[2*(2*i+1)+2])) {
                BuildMaxHeap(heap, len);
            }
        }
        if ((2*i+2) < len && heap[i] < heap[2*i+2]) {  /* 根節(jié)點大于右子樹 */
            temp = heap[i];
            heap[i] = heap[2*i+2];
            heap[2*i+2] = temp;
            /* 檢查交換后的右子樹是否滿足大頂堆性質 如果不滿足 則重新調整子樹結構 */
            if ((2*(2*i+2)+1 < len && heap[2*i+2] < heap[2*(2*i+2)+1]) || (2*(2*i+2)+2 < len && heap[2*i+2] < heap[2*(2*i+2)+2])) {
                BuildMaxHeap(heap, len);
            }
        }
    }
}

歸并排序

簡介

歸并排序是建立在歸并操作上的一種有效，穩(wěn)定的排序算法，該算法是采用分治法的一個非常典型的應用，其核心思想是將兩個有序的數列合并成一個大的有序的序列。

復雜度與穩(wěn)定性

注：歸并排序需要創(chuàng)建一個與原數組相同長度的數組來輔助排序

過程介紹

首先將已有序的子序列合并，得到完全有序的序列，即先使每個子序列有序，再使子序列段間有序。

過程如下：

1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列

2. 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置

3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置

4. 重復步驟c直到某一指針超出序列尾

5. 將另一序列剩下的所有元素直接復制到合并序列尾

圖示過程

第一次排序將數據分為“兩個”一組，組內順序，其次再逐個的將各組進行整合，最終完成歸并排序

主要代碼實現

void merge(int arr[],int l,int mid,int r) {
    int aux[r-l+1];//開辟一個新的數組，將原數組映射進去
    for(int m=l; m<=r; m++) {
        aux[m-l]=arr[m];
    }
  
    int i=l,j=mid+1;//i和j分別指向兩個子數組開頭部分
  
    for(int k=l; k<=r; k++) {
        if(i>mid) {
            arr[k]=aux[j-l];
            j++;
        } else if(j>r) {
            arr[k]=aux[i-l];
            i++;
        } else if(aux[i-l]<aux[j-l]) {
            arr[k]=aux[i-l];
            i++;
        } else {
            arr[k]=aux[j-l];
            j++;
        }
    }
}
  
void merge_sort(int arr[],int n) {
    for(int sz=1; sz<=n; sz+=sz) {
        for(int i=0; i+sz<n; i+=sz+sz) { //i+sz防止越界
            //對局部：arr[i...sz-1]和arr[i+sz.....i+2*sz-1]進行排序
            merge(arr,i,i+sz-1,min(i+sz+sz-1,n-1));    //min函數防止越界
        }
    }
  
}
  

快速排序

簡介

快速排序在1960年提出，是考察次數最多的排序，無論是在大學專業(yè)課的期末考試，還是在公司的面試測試題目中，快速排序都極大的被使用，在實際中快速排序也極大的被使用。

復雜度與穩(wěn)定性

過程介紹

通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

1. 在數組中選擇一個基準點

2. 分別從數組的兩端掃描數組，設兩個指示標志

3. 從后半部分開始，如果發(fā)現有元素比該基準點的值小，就交換位置

4. 然后從前半部分開始掃描，發(fā)現有元素大于基準點的值，繼續(xù)交換位置

5. 如此往復循環(huán)，然后把基準點的值放到high這個位置,排序完成

以后采用遞歸的方式分別對前半部分和后半部分排序，當前半部分和后半部分均有序時該數組就自然有序了。

圖示過程

可以看出，在第四趟時已經達到順序，但是仍然還是會繼續(xù)計算幾趟直到完成全部運算

主要代碼實現

void qucik_sort(int a[],int low,int high) {
  int i,j,temp;
  i=low;
  j=high;
  if(low<high) {
    temp=a[low];    //設置樞軸
    while(i!=j) {
      while(j>i&&a[j]>=temp) {
        --j;
      }
      if(i<j) {
        a[i]=a[j];
        ++i;
      }

      while(i<j&&a[i]<temp) {
        ++i;
      }
      if(i<j) {
        a[j]=a[i];
        --j;
      }
    }
    a[i]=temp;
    qucik_sort(a,low,i-1);
    qucik_sort(a,i+1,high);
  }
}

計數排序

簡介

計數排序的核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

計數排序算法不是基于元素比較，而是利用數組下標來確定元素的正確位置。

它的優(yōu)勢在于在對一定范圍內的整數排序時，它的復雜度為Ο(n+k)，快于任何比較排序算法。

當然這是一種犧牲空間換取時間的做法，而且當O(k)>O(n*log(n))的時候其效率反而不如基于比較的排序。

復雜度與穩(wěn)定性

過程介紹

1. 找出待排序的數組中最大和最小的元素

2. 統(tǒng)計數組中每個值為i的元素出現的次數，存入數組C的第i項

3. 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）

4. 反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1

圖示過程

如下圖，A為待排序的數組，C記錄A中各個值的數目。

將C[i]轉換為值小于等于i的元素個數。

為數組A從后向前的每個元素找到對應的B中的位置，每次從A中復制一個元素到B中，C中相應的計數減一。

當A中的元素都復制到B中后，B就是排序好的結果，如圖所示。

代碼實現

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void CountSort(int *arr, int len){
    if(arr == NULL) return;
    int max = arr[0], min = arr[0];
    for(int i = 1; i < len; i++){
        if(arr[i] > max)    max = arr[i];
        if(arr[i] < min)    min = arr[i];
    }
    int size = max - min + 1;
    int *count =(int*)malloc(sizeof(int)*size);
    memset(count, 0, sizeof(int)*size);

    for(int i = 0; i < len; i++)
        count[arr[i] - min]++;//包含了自己！
    for(int i = 1; i < size; i++)
        count[i] += count[i - 1];

    int* psort =(int*)malloc(sizeof(int)*len);
    memset(psort, 0, sizeof(int)*len);

    for(int i = len - 1; i >= 0; i--){
        count[arr[i] - min]--;//要先把自己減去
        psort[count[arr[i] - min]] = arr[i];
    }

    for(int i = 0; i < len; i++){
        arr[i] = psort[i];
    }

    free(count);
    free(psort);
    count = NULL;
    psort = NULL;
}


void print_array(int *arr, int len)
{
    for(int i=0; i<len; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main()
{
    int arr[8] = {2, 5, 3, 0, 2, 3, 0, 3};
    CountSort(arr, 8);
    print_array(arr, 8);

    return 0;
}

桶式排序

簡介

桶排序也稱箱排序，原理是將數組分到有限數量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序）。

桶排序是鴿巢排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。

復雜度與穩(wěn)定性

過程介紹

1. 根據待排序集合中最大元素和最小元素的差值范圍和映射規(guī)則，確定申請的桶個數；

2. 遍歷待排序集合，將每一個元素移動到對應的桶中；

3. 對每一個桶中元素進行排序，并移動到已排序集合中。

圖示過程

元素分布在桶中：

然后，元素在每個桶中排序：

代碼實現

#include<iterator>
#include<iostream>
#include<vector>
using namespace std;
const int BUCKET_NUM = 10;

struct ListNode{
    explicit ListNode(int i=0):mData(i),mNext(NULL){}
    ListNode* mNext;
    int mData;
};

ListNode* insert(ListNode* head,int val){
    ListNode dummyNode;
    ListNode *newNode = new ListNode(val);
    ListNode *pre,*curr;
    dummyNode.mNext = head;
    pre = &dummyNode;
    curr = head;
    while(NULL!=curr && curr->mData<=val){
            pre = curr;
            curr = curr->mNext;
    }
    newNode->mNext = curr;
    pre->mNext = newNode;
    return dummyNode.mNext;
}


ListNode* Merge(ListNode *head1,ListNode *head2){
    ListNode dummyNode;
    ListNode *dummy = &dummyNode;
    while(NULL!=head1 && NULL!=head2){
            if(head1->mData <= head2->mData){
                    dummy->mNext = head1;
                    head1 = head1->mNext;
            }else{
                    dummy->mNext = head2;
                    head2 = head2->mNext;
            }
            dummy = dummy->mNext;
    }
    if(NULL!=head1) dummy->mNext = head1;
    if(NULL!=head2) dummy->mNext = head2;

    return dummyNode.mNext;
}

void BucketSort(int n,int arr[]){
    vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
    for(int i=0;i<n;++i){
            int index = arr[i]/BUCKET_NUM;
            ListNode *head = buckets.at(index);
            buckets.at(index) = insert(head,arr[i]);
    }
    ListNode *head = buckets.at(0);
    for(int i=1;i<BUCKET_NUM;++i){
            head = Merge(head,buckets.at(i));
    }
    for(int i=0;i<n;++i){
            arr[i] = head->mData;
            head = head->mNext;
    }
}

基數排序

簡介

基數排序是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，在某些時候，基數排序法的效率高于其它的穩(wěn)定性排序法。

復雜度與穩(wěn)定性

圖示過程

設有一個初始序列為: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。

過程介紹

任何一個阿拉伯數，它的各個位數上的基數都是以0~9來表示的。所以我們不妨把0~9視為10個桶。

1. 我們先根據序列的個位數的數字來進行分類，將其分到指定的桶中。

2. 分類后，我們在從各個桶中，將這些數按照從編號0到編號9的順序依次將所有數取出來。

3. 得到的序列就是個位數上呈遞增趨勢的序列。

4. 按照上圖個位數排序：{50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

5. 接下來對十位數、百位數也按照這種方法進行排序，最后就能得到排序完成的序列。

主要代碼實現

public class RadixSort {
    // 獲取x這個數的d位數上的數字
    // 比如獲取123的1位數，結果返回3
    public int getDigit(int x, int d) {
        int a[] = {1, 1, 10, 100}; // 本實例中的最大數是百位數，所以只要到100就可以了
        return ((x / a[d]) % 10);
    }

  public void radixSort(int[] list, int begin, int end, int digit) {
      final int radix = 10; // 基數
      int i = 0, j = 0;
      int[] count = new int[radix]; // 存放各個桶的數據統(tǒng)計個數
      int[] bucket = new int[end - begin + 1];
      // 按照從低位到高位的順序執(zhí)行排序過程
      for (int d = 1; d <= digit; d++) {
          // 置空各個桶的數據統(tǒng)計
          for (i = 0; i < radix; i++) {
              count[i] = 0;
          }
          // 統(tǒng)計各個桶將要裝入的數據個數
          for (i = begin; i <= end; i++) {
              j = getDigit(list[i], d);
              count[j]++;
          }
          // count[i]表示第i個桶的右邊界索引
          for (i = 1; i < radix; i++) {
              count[i] = count[i] + count[i - 1];
          }
          // 將數據依次裝入桶中
          // 這里要從右向左掃描，保證排序穩(wěn)定性
          for (i = end; i >= begin; i--) {
              j = getDigit(list[i], d);
              // 求出關鍵碼的第k位的數字， 例如：576的第3位是5
              bucket[count[j] - 1] = list[i];
              // 放入對應的桶中，count[j]-1是第j個桶的右邊界索引
              count[j]--; // 對應桶的裝入數據索引減一
          }
          // 將已分配好的桶中數據再倒出來，此時已是對應當前位數有序的表
          for (i = begin, j = 0; i <= end; i++, j++) {
              list[i] = bucket[j];
          }
      }
  }

  public int[] sort(int[] list) {
      radixSort(list, 0, list.length - 1, 3);
      return list;
  }

  // 打印完整序列
  public void printAll(int[] list) {
      for (int value : list) {
          System.out.print(value + "\t");
      }
      System.out.println();
  }

  public static void main(String[] args) {
      int[] array = {50, 123, 543, 187, 49, 30, 0, 2, 11, 100};
      RadixSort radix = new RadixSort();
      System.out.print("排序前:\t\t");
      radix.printAll(array);
      radix.sort(array);
      System.out.print("排序后:\t\t");
      radix.printAll(array);
  }
}

總結

10種排序算法對比，我們了解到了各種排序的原理及優(yōu)缺點，記住任何一種排序都不是十全十美的，因此在我們實際應用中，最好的方式就是揚長避短。

今天排序基礎就講到這里，下一期，我們再見！