寫在前面：博主是一位普普通通的19屆雙非軟工在讀生，平時最大的愛好就是聽聽歌，逛逛B站。博主很喜歡的一句話花開堪折直須折，莫待無花空折枝：博主的理解是頭一次為人，就應該做自己想做的事，做自己不后悔的事，做自己以后不會留有遺憾的事，做自己覺得有意義的事，不浪費這大好的青春年華。博主寫博客目的是記錄所學到的知識并方便自己復習，在記錄知識的同時獲得部分瀏覽量，得到更多人的認可，滿足小小的成就感，同時在寫博客的途中結交更多志同道合的朋友，讓自己在技術的路上并不孤單。

目錄:
1.冒泡排序
2.選擇排序
???? ?? 簡單選擇排序
???? ?? 樹形選擇排序
3.堆排序
4.插入排序
???? ?? 直接插入排序
???? ?? 折半插入排序
???? ?? 2-路插入排序算法
???? ?? 表插入排序
5.希爾排序
6.快速排序
7.歸并排序
8.基數排序
9.總結

本篇博客部分圖片及代碼參考一文總結十大經典排序算法（思維導圖 + 動圖演示 + 代碼實現 C/C++/Python + 致命吐槽）

1.冒泡排序

兩兩比較，把較大的數放在后面，每一輪循環循環結束會找出一個最大值，完成排序

//C void swap(int *a,int *b){int temp = *a;*a = *b;*b = temp; } void bubble_sort(int arr[], int len){int i, j, temp;for (i = 0; i < len - 1; i++)for (j = 0; j < len - 1 - i; j++)if (arr[j] > arr[j + 1]) {swap(&arr[j], &arr[j + 1]);} }

冒泡排序的改進：

比如我們給出一個數組[2,1,3,4,5,6,7,8,9]從小到大排序，我們可以看出只需要交換一次就完成排序，但是普通的冒泡排序即使在完成排序后執行完兩個for循環里邊的代碼，導致時間復雜度為O(n²),所以我們需要對冒泡排序進行改進

冒泡排序的改進思路：

如果在某一輪冒泡過程中，沒有一次交換，那么說明后面已經正確排序不用再進行下一輪比較，直接跳出循環

void swap(int *a,int *b){int temp = *a;*a = *b;*b = temp; } void bubble_sort(int arr[], int len){int i, j, temp;bool flag;for (i = 0; i < len - 1; i++){flag=false;for (j = 0; j < len - 1 - i; j++)if (arr[j] > arr[j + 1]) {false=true;swap(&arr[j], &arr[j + 1]);}if(flag==false)break;} }

時間復雜度：最好情況O(n),最壞情況O(n2),平均時間復雜度O(n2)
空間復雜度：只需要一個變量作為輔助空間，空間復雜度O(1)
算法特點：
1.穩定排序。
2.移動的次數比較多，當初始記錄無序，n較大時，算法不適用。

2.選擇排序

2.1簡單選擇排序

描述：

第一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數據元素的個數為零。

//C void swap(int *a,int *b){int temp = *a;*a = *b;*b = temp; } void selection_sort(int arr[], int len){int i,j;for (i = 0 ; i < len - 1 ; i++){int min = i;//遍歷未排序的元素for (j = i + 1; j < len; j++){if (arr[j] < arr[min]) //找到目前最小值min = j; //記錄最小值swap(&arr[min], &arr[i]); //做交換}} }

時間復雜度：最好情況O(n2),最壞情況O(n2),平均時間復雜度O(n2)
空間復雜度：只需要一個變量作為輔助空間，空間復雜度O(1)
算法特點：
1.是一種穩定的排序算法。
2.移動次數較少，每當一記錄占用空間比較多的時候，這種排序比插入排序快

2.2樹形選擇排序

樹形選擇排序（又稱“錦標賽排序”），是一種按照錦標賽的思想進行選擇排序的方法，即所有記錄采取兩兩分組，篩選出較小（較大）的值；然后從篩選出的較小（較大）值中再兩兩分組選出更小（更大）值，依次類推，直到最后選出一個最小（最大）值。同樣可以采用此方式篩選出次小（次大）值等。

整個排序的過程，可以用一棵具有 n 個葉子結點的完全二叉樹表示。例如對無序表{49，38，65，97，76，13，27，49}采用樹形選擇的方式排序，過程如下：

首先將無序表中的記錄采用兩兩分組，篩選出各組中的較小值（如圖中的（a）過程）；然后將篩選出的較小值兩兩分組，篩選出更小的值，以此類推（如圖中的（b）（c）過程），最終整棵樹的根結點中的關鍵字即為最小關鍵字：

篩選出關鍵字 13 之后，繼續重復此方式找到剩余記錄中的最小值，此時由于關鍵字 13 已經篩選完成，需要將關鍵字 13 改為“最大值”，繼續重復此過程，如下圖 所示：

通過不斷地重復此過程，可依次篩選出從小到大的所有關鍵字。該算法的時間復雜度為O(nlog2n)，同簡單選擇排序相比，該算法減少了不同記錄之間的比較次數，但是程序運行所需要的空間較多。

3.堆排序

堆：在含有 n 個元素的序列中，如果序列中的元素滿足下面其中一種關系時，此序列可以稱之為堆

ki≤ k2i 且 ki ≤ k2i+1（在 n 個記錄的范圍內，第 i 個關鍵字的值小于第 2*i 個關鍵字，同時也小于第 2*i+1 個關鍵字）

ki ≥ k2i 且 ki ≥ k2i+1（在 n 個記錄的范圍內，第 i 個關鍵字的值大于第 2*i 個關鍵字，同時也大于第 2*i+1 個關鍵字）

對于堆的定義也可以使用完全二叉樹來解釋，因為在完全二叉樹中第 i 個結點的左孩子恰好是第 2i 個結點，右孩子恰好是 2i+1 個結點。如果該序列可以被稱為堆，則使用該序列構建的完全二叉樹中，每個根結點的值都必須不小于（或者不大于）左右孩子結點的值。

以無序表{49，38，65，97，76，13，27，49}來講，其對應的堆用完全二叉樹來表示為:

堆用完全二叉樹表示時，其表示方法不唯一，但是可以確定的是樹的根結點要么是無序表中的最小值，要么是最大值。

講完了堆，那么我們來講堆排序：

通過將無序表轉化為堆，可以直接找到表中最大值或者最小值，然后將其提取出來，令剩余的記錄再重建一個堆，取出次大值或者次小值，如此反復執行就可以得到一個有序序列，此過程為堆排序。

堆排序過程的代碼實現需要解決兩個問題：

如何將得到的無序序列轉化為一個堆？

在輸出堆頂元素之后（完全二叉樹的樹根結點），如何調整剩余元素構建一個新的堆？

如下例子：

當根節點13輸出后，我們用最后一個節點代替根節點即：

此時由于結點 97 比左右孩子結點的值都大，破壞了堆的結構，所以需要進行調整：首先以 堆頂元素 97 同左右子樹比較，同值最小的結點交換位置，即 27 和 97 交換位置：

由于替代之后破壞了根結點右子樹的堆結構，所以需要進行和上述一樣的調整，即令 97 同 49 進行交換位置：

通過上述的調整，之前被破壞的堆結構又重新建立。從根結點到葉子結點的整個調整的過程，被稱為“篩選”。這樣我們的第2個問題就被解決了

那么第一個問題如何解決呢，別急！還是這個無序表{49，38，65，97，76，13，27，49}初步建立的完全二叉樹

在對上圖做篩選工作時，規律是從底層結點開始，一直篩選到根結點。對于具有 n 個結點的完全二叉樹，篩選工作開始的結點為第 ?n/2?個結點（此結點后序都是葉子結點，無需篩選）。

所以，對于有 9 個結點的完全二叉樹，篩選工作從第 4 個結點 97 開始，由于 97 > 49 ,所以需要相互交換，交換后如下圖所示：

然后再篩選第 3 個結點 65 ，由于 65 比左右孩子結點都大，則選擇一個最小的同 65 進行交換，交換后的結果為：

然后篩選第 2 個結點，由于其符合要求，所以不用篩選；最后篩選根結點 49 ，同 13 進行交換，交換后的結果為：

交換后，發現破壞了其右子樹堆的結構，所以還需要調整，最終調整后的結果為：

//C void swap(int *a, int *b) {int temp = *b;*b = *a;*a = temp; }void max_heapify(int arr[], int start, int end) {// 建立一個父指針，一個子指針int dad = start;int son = dad * 2 + 1;while (son <= end) { // 子指針和數組范圍比較防止越界if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較左右孩子的大小，選擇大的和父親比較son++;if (arr[dad] > arr[son]) //如果父親大于較大的孩子那么直接跳出終止循環return;else { // 否則交換父子的元素值，再防止交換后的值破壞原有的堆結構swap(&arr[dad], &arr[son]);dad = son;son = dad * 2 + 1;}} }void heap_sort(int arr[], int len) {int i;//初始化i的值，由于數組下標從0開始所以需要減1for (i = len / 2 - 1; i >= 0; i--)max_heapify(arr, i, len - 1);// 先將第一個+元素和已排好元素前一位做交換，再重新調整，直到排序完畢for (i = len - 1; i > 0; i--) {swap(&arr[0], &arr[i]);max_heapify(arr, 0, i - 1);} }

最好情況O(nlogn)
最壞情況O(nlogn)
平均時間復雜度O(nlogn)
空間復雜度：
只需要一個記錄大小交換用的輔助空間，空間復雜度O(1)
算法特點：
1.是一種不穩定的排序算法。
2.建立堆所需要的比較次數比較多，因此記錄數較少的時候不宜采用。

4.插入排序

4.1直接插入排序

插入排序算法是所有排序方法中最簡單的一種算法，其主要的實現思想是將數據按照一定的順序一個一個的插入到有序的表中，最終得到的序列就是已經排序好的數據。

直接插入排序是插入排序算法中的一種，采用的方法是：在添加新的記錄時，使用順序查找的方式找到其要插入的位置，然后將新記錄插入。

例如采用直接插入排序算法將無序表{3,1,7,5,2,4,9,6}進行升序排序的過程為：

首先考慮記錄 3 ，由于插入排序剛開始，有序表中沒有任何記錄，所以 3 可以直接添加到有序表中，則有序表和無序表可以如圖

向有序表中插入記錄 1 時，同有序表中記錄 3 進行比較，1<3，所以插入到記錄 3 的左側，如圖

向有序表插入記錄 7 時，同有序表中記錄 3 進行比較，3<7，所以插入到記錄 3 的右側，如圖

向有序表中插入記錄 5 時，同有序表中記錄 7 進行比較，5<7，同時 5>3，所以插入到 3 和 7 中間，如圖

向有序表插入記錄 2 時，同有序表中記錄 7進行比較，2<7，再同 5，3，1分別進行比較，最終確定 2 位于 1 和 3 中間，如圖

最終：

動態圖：

//C void insertion_sort(int arr[], int len){int i,j,key;for (i=1;i<len;i++){key = arr[i];j=i-1;while((j>=0) && (arr[j]>key)) {arr[j+1] = arr[j];j--;}arr[j+1] = key;} }

4.2折半插入排序

直接插入排序算法在查找插入位置時，采用的是順序查找的方式，而在查找表中數據本身有序的前提下，可以使用折半查找來代替順序查找，這種排序的算法就是折半插入排序算法。

#include <stdio.h> void print(int a[], int n ,int i){printf("%d:",i);for(int j=0; j<8; j++){printf("%d",a[j]);}printf("\n"); }void BInsertSort(int a[],int size){int i,j,low = 0,high = 0,mid;int temp = 0;for (i=1; i<size; i++) {low=0;high=i-1;temp=a[i];//采用折半查找法判斷插入位置，最終變量 low 表示插入位置while (low<=high) {mid=(low+high)/2;if (a[mid]>temp) {high=mid-1;}else{low=mid+1;}}//有序表中插入位置后的元素統一后移for (j=i; j>low; j--) {a[j]=a[j-1];}a[low]=temp;//插入元素print(a, 8, i);}} int main(){int a[8] = {3,1,7,5,2,4,9,6};BInsertSort(a, 8);return 0; }

4.3 2-路插入排序算法

2-路插入排序算法是在折半插入排序的基礎上對其進行改進，減少其在排序過程中移動記錄的次數從而提高效率。

具體實現思路為：另外設置一個同存儲記錄的數組大小相同的數組 d，將無序表中第一個記錄添加進 d[0] 的位置上，然后從無序表中第二個記錄開始，同 d[0] 作比較：如果該值比 d[0] 大，則添加到其右側；反之添加到其左側。在這里的數組 d 可以理解成一個環狀數組。

使用 2-路插入排序算法對無序表{3,1,7,5,2,4,9,6}排序的過程如下：

插入1：

插入7：

插入5,由于其比 7小，但是比 3 大，所以需要移動 7 的位置，然后將 5 插入:

將記錄 2 插入到數組 d 中，由于比 1大，比 3 小，所以需要移動 3、7、5 的位置，然后將 2 插入:

將記錄 4 插入到數組 d 中，需要移動 5 和 7 的位置:

將記錄 9 插入到數組 d 中:

將記錄 6 插入到數組 d 中:

最終存儲在原數組時，從 d[7] 開始依次存儲。

C語言完整代碼實現：

#include <stdio.h> #include <stdlib.h> void insert(int arr[], int temp[], int n) {int i,first,final,k;first = final = 0;//分別記錄temp數組中最大值和最小值的位置temp[0] = arr[0];for (i = 1; i < n; i ++){// 待插入元素比最小的元素小if (arr[i] < temp[first]){first = (first - 1 + n) % n;temp[first] = arr[i];}// 待插入元素比最大元素大else if (arr[i] > temp[final]){final = (final + 1 + n) % n;temp[final] = arr[i];}// 插入元素比最小大，比最大小else {k = (final + 1 + n) % n;//當插入值比當前值小時，需要移動當前值的位置while (temp[((k - 1) + n) % n] > arr[i]) {temp[(k + n) % n] =temp[(k - 1 + n) % n];k = (k - 1 + n) % n;}//插入該值temp[(k + n) % n] = arr[i];//因為最大值的位置改變，所以需要實時更新final的位置final = (final + 1 + n) % n;}}// 將排序記錄復制到原來的順序表里for (k = 0; k < n; k ++) {arr[k] = temp[(first + k) % n];} }int main() {int a[8] = {3,1,7,5,2,4,9,6};int temp[8];insert(a,temp,8);for (int i = 0; i < 8; i ++){printf("%d ", a[i]);}return 0; }

4.4表插入排序

表插入排序，即使用鏈表的存儲結構對數據進行插入排序。在對記錄按照其關鍵字進行排序的過程中，不需要移動記錄的存儲位置，只需要更改結點間指針的指向。

鏈表的存儲結構：

#define SIZE 100 typedef struct {int rc;//記錄項int next;//指針項，由于在數組中，所以只需要記錄下一個結點所在數組位置的下標即可。 }SLNode; typedef struct {SLNode r[SIZE];//存儲記錄的鏈表int length;//記錄當前鏈表長度 }SLinkListType;

在使用數組結構表示的鏈表中，設定數組下標為 0 的結點作為鏈表的表頭結點，并令其關鍵字取最大整數。則表插入排序的具體實現過程是：首先將鏈表中數組下標為 1 的結點和表頭結點構成一個循環鏈表，然后將后序的所有結點按照其存儲的關鍵字的大小，依次插入到循環鏈表中。

例如，將無序表{49，38，76，13，27}用表插入排序的方式進行排序，其過程為：

首先使存儲 49 的結點與表頭結點構成一個初始的循環鏈表，完成對鏈表的初始化，如下表所示：

然后將以 38 為關鍵字的記錄插入到循環鏈表中（只需要更改其鏈表的 next 指針即可），插入后的鏈表為：

再將以 76 為關鍵字的結點插入到循環鏈表中，插入后的鏈表為:

直到最后：

最終：

從表插入排序的實現過程上分析，與直接插入排序相比只是避免了移動記錄的過程（修改各記錄結點中的指針域即可），而插入過程中同其它關鍵字的比較次數并沒有改變，所以表插入排序算法的時間復雜度仍是O(n2)。

5.希爾排序

希爾排序，又稱“縮小增量排序”，也是插入排序的一種，但是同前面幾種排序算法比較來看，希爾排序在時間效率上有很大的 改進。 在使用直接插入排序算法時，如果表中的記錄只有個別的是無序的，多數保持有序，這種情況下算法的效率也會比較高；除此之 外，如果需要排序的記錄總量很少，該算法的效率同樣會很高。希爾排序就是從這兩點出發對算法進行改進得到的排序算法。

希爾排序的具體實現思路是：先將整個記錄表分割成若干部分，分別進行直接插入排序，然后再對整個記錄表進行一 次直接插入排序

例如無序表{49，38，65，97，76，13，27，49，55，4}進行希爾排序的過程為：

首先對 {49，13}，{38，27}，{65，49}，{97，55}，{76，4} 分別進行直接插入排序（如果需要調換位置也只是互換存儲 位置上圖中兩兩進行比較，例如 下圖49 和 13 進行比較，13<49，所以交換存儲位置。）

通過一次排序，無序表中的記錄已基本有序，此時還可以再進行一次分割，這一次我們把數據分成三組，如下圖所示：

經過兩次分割，無序表中已基本有序，此時對整張表進行一次直接插入排序（只需要做少量的比較和插入操作即可），最 終希爾排序的結果為：

動圖展示：

代碼實現：

//C void shell_sort(int arr[], int len) {int gap, i, j;int temp;for (gap = len >> 1; gap > 0; gap >>= 1){for (i = gap; i < len; i++) {temp = arr[i];for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)arr[j + gap] = arr[j];arr[j + gap] = temp;}} }

時間復雜度：
最好情況O(nlog2n)
最壞情況O(nlog2n)
平均時間復雜度O(nlogn)
空間復雜度：
只需要一個變量作為輔助空間，空間復雜度O(1)
算法特點：
1.這種跳躍式得的移動導致算法不是很穩定
2.這個增量序列有各種不同的取法Hibbard增量和sedgewick增量，據說這兩種序列會降低其算法復雜度
3.n較大時，效果越明顯，適用于n較大的情況

6.快速排序

C 語言中自帶函數庫中就有快速排序——qsort 函數 ，包含在 <stdlib.h> 頭文件中

具體思路：

快速排序算法是在起泡排序的基礎上進行改進的一種算法，其實現的基本思想是：通過一次排序將整個無序表分成相互獨立的兩 部分，其中一部分中的數據都比另一部分中包含的數據的值小，然后繼續沿用此方法分別對兩部分進行同樣的操作，直到每一個 小部分不可再分，所得到的整個序列就成為了有序序列。

例如，對無序表{49，38，65，97，76，13，27，49}進行快速排序，大致過程為：

首先從表中選取一個記錄的關鍵字作為分割點（稱為“樞軸”或者支點，一般選擇第一個關鍵字），例如選取 49；

將表格中大于 49 個放置于 49 的右側，小于 49 的放置于 49 的左側，假設完成后的無序表為：{27，38，13，49， 65，97，76，49}；

. 以 49 為支點，將整個無序表分割成了兩個部分，分別為{27，38，13}和{65，97，76，49}，繼續采用此種方法分別對 兩個子表進行排序；

. 前部分子表以 27 為支點，排序后的子表為{13，27，38}，此部分已經有序；后部分子表以 65 為支點，排序后的子表為 {49，65，97，76}；

. 此時前半部分子表中的數據已完成排序；后部分子表繼續以 65 為支點，將其分割為{49}和{97，76}，前者不需排序，后 者排序后的結果為{76，97}；

. 通過以上幾步的排序，最后由子表{13，27，38}、{49}、{49}、{65}、{76，97}構成有序表：{13，27，38，49，49， 65，76，97}；

對于上述描述我們需要設置兩個指針 low 和 high，分別指向無序表的表頭和表尾：

先由 high 指針從右往左依次遍歷，直到找到一個比 49 小的關鍵字，所以 high 指針走到 27 的地方停止。找到之后將 該關鍵字同 low 指向的關鍵字進行互換：

然后指針 low 從左往右依次遍歷，直到找到一個比 49 大的關鍵字為止，所以 low 指針走到 65 的地方停止。同樣找 到后同 high 指向的關鍵字進行互換：

指針 high 繼續左移，到 13 所在的位置停止（13<49），然后同 low 指向的關鍵字進行互換：

指針 low 繼續右移，到 97 所在的位置停止（97>49），然后同 high 指向的關鍵字互換位置：

指針 high 繼續左移，此時兩指針相遇，第一趟快速排序結束；

當所有數據的支點前后都只有一個元素的時候整個快速排序過程結束

動態圖：

//C void swap(int *x, int *y) {int t = *x;*x = *y;*y = t; }void quick_sort_recursive(int arr[], int start, int end) {if (start >= end)return;int mid = arr[end];//代碼是以最后一個下標為支點int left = start, right = end - 1;while (left < right) {while (arr[left] < mid && left < right)left++;while (arr[right] >= mid && left < right)right--;swap(&arr[left], &arr[right]);}if (arr[left] >= arr[end])swap(&arr[left], &arr[end]);elseleft++;if (left)quick_sort_recursive(arr, start, left - 1);quick_sort_recursive(arr, left + 1, end); }void quick_sort(int arr[], int len) {quick_sort_recursive(arr, 0, len - 1); }

時間復雜度：
最好情況O(nlogn)
最壞情況O(n2)
平均時間復雜度O(nlogn)
空間復雜度：
執行時需要有一個棧來存放相應的數據，所以最大遞歸調用次數與遞歸樹的深度一致，最好情況為O(logn)，最壞情況下為O(n)
算法特點：
1.是一種不穩定的排序算法。
2.是所有內部排序的最快的排序算法。
3.缺點較多，但是c++STL庫中針對其缺點已經做出了優化。

7.歸并排序

其排序的實現思想是先將所有的記錄完全分開，然后兩兩合 并，在合并的過程中將其排好序，最終能夠得到一個完整的有序表。

例如對于含有 n 個記錄的無序表，首先默認表中每個記錄各為一個有序表（只不過表的長度都為 1），然后進行兩兩合并，使 n 個有序表變為 ? n/2? 個長度為 2 或者 1 的有序表（例如 4 個小有序表合并為 2 個大的有序表），通過不斷地進行兩兩合 并，直到得到一個長度為 n 的有序表為止。這種歸并排序方法稱為：2-路歸并排序。

例如對無序表{49，38，65，97，76，13，27}進行 2-路歸并排序的過程如圖

歸并過程中，每次得到的新的子表本身有序，所以最終得到的為有序表。

動圖展示：

//C void merge_sort_recursive(int arr[], int reg[], int start, int end) {if (start >= end)return;int len = end - start, mid = (len >> 1) + start;int start1 = start, end1 = mid;int start2 = mid + 1, end2 = end;merge_sort_recursive(arr, reg, start1, end1);merge_sort_recursive(arr, reg, start2, end2);int k = start;while (start1 <= end1 && start2 <= end2)reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];while (start1 <= end1)reg[k++] = arr[start1++];while (start2 <= end2)reg[k++] = arr[start2++];for (k = start; k <= end; k++)arr[k] = reg[k]; } void merge_sort(int arr[], const int len) {int reg[len];merge_sort_recursive(arr, reg, 0, len - 1); }

歸并排序算法在具體實現時，首先需要將整個記錄表進行折半分解，直到分解為一個記錄作為單獨的一張表為 止，然后在進行兩兩合并。整個過程為分而后立的過程。該算法相比于堆排序和快速排序，其主要的優點是：當記錄表中含有值相同的記錄時， 排序前和排序后在表中的相對位置不會改變。例如，在記錄表中記錄 a 在記錄 b 的前面（記錄 a 和 b 的關鍵字的值相等），使用歸并排序之后記錄 a 還在記錄 b 的前 面。這就體現出了該排序算法的穩定性。而堆排序和快速排序都是不穩定的。

時間復雜度：
最好情況O(nlogn)
最壞情況O(nlogn)
平均時間復雜度O(nlogn)
空間復雜度：
只需要一個跟待排數組大小相同的輔助空間，空間復雜度為O(n)
算法特點：
1.是一種穩定的排序算法。
2.比較占用內存。

8.基數排序

基數排序不同于之前所介紹的各類排序，前邊介紹到的排序方法或多或少的是通過使用比較和移動記錄來實現排序，而基數排序 的實現不需要進行對關鍵字的比較，只需要對關鍵字進行“分配”與“收集”兩種操作即可完成。

例如對無序表{50，123，543，187，49，30，0，2，11，100}進行基數排序，由于每個關鍵字都是整數數值，且其中的最大 值由個位、十位和百位構成，每個數位上的數字從 0 到 9，首先將各個關鍵字按照其個位數字的不同進行分配分配表如下圖所 示

通過按照各關鍵字的個位數進行分配，按照順序收集得到的序列變為：{50，30，0，100，11，2，123，543，187，49}。在 該序列表的基礎上，再按照各關鍵字的十位對各關鍵字進行分配，得到的分配表如下圖所示：

通過按照各關鍵字的個位數進行分配，按照順序收集得到的序列變為：{50，30，0，100，11，2，123，543，187，49}。在 該序列表的基礎上，再按照各關鍵字的十位對各關鍵字進行分配，得到的分配表如下圖所示：

由上表順序收集得到的記錄表為：{0、100、2、11、123、30、543、49、50、187}。在該無序表的基礎上，依次將表中的記 錄按照其關鍵字的百位進行分配，得到的分配如下圖所示：

最終通過三次分配與收集，最終得到的就是一個排好序的有序表：{0、2、11、30、49、50、100、123、187、543}。

例子中是按照個位-十位-百位的順序進行基數排序，此種方式是從最低位開始排序，所以被稱為最低位優先法（簡稱“LSD 法”）。 同樣還可以按照百位-十位-各位的順序進行排序，稱為最高位優先法（簡稱“MSD 法”），使用該方式進行排序同最低位優先 法不同的是：當無序表中的關鍵字進行分配后，相當于進入了多個子序列，后序的排序工作分別在各個子序列中進行（最低位優 先法每次分配與收集都是相對于整個序列表而言的）。 例如還是對{50，123，543，187，49，30，0，2，11，100}使用最高位優先法進行排序，首先按照百位的不同進行分配，得 到的分配表為

由上圖所示，整個無序表被分為了 3 個子序列，序列 1 和序列 2 中含有多個關鍵字，序列 3 中只包含了一個關鍵字，最高 位優先法完成排序的標準為：直到每個子序列中只有一個關鍵字為止，所以需要分別對兩個子序列進行再分配，各自的分配表如 下圖所示：

上表中，序列 1 中還有含有兩個關鍵字的子序列，所以還需要根據個位進行分配，最終按照各子序列的順序同樣會得到一個有 序表。

動圖：

//C void print(int *a, int n) {int i;for (i = 0; i < n; i++) {printf("%d\t", a[i]);} }void radixsort(int *a, int n) {int i, b[MAX], m = a[0], exp = 1;for (i = 1; i < n; i++) {if (a[i] > m) {m = a[i];}}while (m / exp > 0) {int bucket[BASE] = { 0 };for (i = 0; i < n; i++) {bucket[(a[i] / exp) % BASE]++;}for (i = 1; i < BASE; i++) {bucket[i] += bucket[i - 1];}for (i = n - 1; i >= 0; i--) {b[--bucket[(a[i] / exp) % BASE]] = a[i];}for (i = 0; i < n; i++) {a[i] = b[i];}exp *= BASE;#ifdef SHOWPASSprintf("\nPASS : ");print(a, n); #endif} }

時間復雜度：
最好情況O(nk)
最壞情況O(nk)
平均時間復雜度O(n*k)
空間復雜度：
空間復雜度（n+k）
算法特點：
1.是一種穩定的排序算法。
2.時間復雜度可以突破基數關鍵詞比較一類方法的下界O(nlogn)達到O(n)
3.使用條件具有嚴格的要求。

9.總結

本篇博客轉載C語言中文網

總結

以上是生活随笔為你收集整理的万字长文总结八大经典内部排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。