十大排序算法可以說是每個(gè)程序員都必須得掌握的了，花了一天的時(shí)間把代碼實(shí)現(xiàn)且整理了一下，為了方便大家學(xué)習(xí)，我把它整理成一篇文章，每種算法會(huì)有簡(jiǎn)單的算法思想描述，為了方便大家理解，我還找來了動(dòng)圖演示；這還不夠，我還附上了對(duì)應(yīng)的優(yōu)質(zhì)文章，看完不懂你來砍我，如果不想砍我就給我來個(gè)好看。
術(shù)語鋪墊
有些人可能不知道什么是穩(wěn)定排序、原地排序、時(shí)間復(fù)雜度、空間復(fù)雜度，我這里先簡(jiǎn)單解釋一下：
1、穩(wěn)定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，則為穩(wěn)定排序。
2、非穩(wěn)定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，則為非穩(wěn)定排序。
3、原地排序：原地排序就是指在排序過程中不申請(qǐng)多余的存儲(chǔ)空間，只利用原來存儲(chǔ)待排數(shù)據(jù)的存儲(chǔ)空間進(jìn)行比較和交換的數(shù)據(jù)排序。
4、非原地排序：需要利用額外的數(shù)組來輔助排序。
5、時(shí)間復(fù)雜度：一個(gè)算法執(zhí)行所消耗的時(shí)間。
6、空間復(fù)雜度：運(yùn)行完一個(gè)算法所需的內(nèi)存大小。
十大排序講解順序
為了方便大家查找，我這里弄一個(gè)偽目錄，沒有跳轉(zhuǎn)功能。
選擇排序
插入排序
冒泡排序
非優(yōu)化版本
優(yōu)化版本
希爾排序
歸并排序
遞歸式歸并排序
非遞歸式歸并排序
快速排序
堆排序
基數(shù)排序
非優(yōu)化版本
優(yōu)化版本
桶排序
基數(shù)排序
1、選擇排序
過程簡(jiǎn)單描述：
首先，找到數(shù)組中最小的那個(gè)元素，其次，將它和數(shù)組的第一個(gè)元素交換位置(如果第一個(gè)元素就是最小元素那么它就和自己交換)。其次，在剩下的元素中找到最小的元素，將它與數(shù)組的第二個(gè)元素交換位置。如此往復(fù)，直到將整個(gè)數(shù)組排序。這種方法我們稱之為選擇排序。
為方便理解我還準(zhǔn)備了動(dòng)圖：
代碼如下(代碼片可以左右拉動(dòng)，下同)：
int* selectSort(int a[],int n)?
{
?for (int i = 0; i < n - 1; i++)
?{
?int min = i;
?for (int j = i + 1; j < n; j++)
?{
?if (a[min] > a[j]) min = j;
?}
?//交換
int temp = a[i];
?a[i] = a[min];
?a[min] = temp;
}
?return a;
}
性質(zhì)：1、時(shí)間復(fù)雜度：O(n2) 2、空間復(fù)雜度：O(1) 3、非穩(wěn)定排序 4、原地排序
2、插入排序
我們?cè)谕娲蚺频臅r(shí)候，你是怎么整理那些牌的呢？一種簡(jiǎn)單的方法就是一張一張的來，將每一張牌插入到其他已經(jīng)有序的牌中的適當(dāng)位置。當(dāng)我們給無序數(shù)組做排序的時(shí)候，為了要插入元素，我們需要騰出空間，將其余所有元素在插入之前都向右移動(dòng)一位，這種算法我們稱之為插入排序。
過程簡(jiǎn)單描述：
1、從數(shù)組第2個(gè)元素開始抽取元素。
2、把它與左邊第一個(gè)元素比較，如果左邊第一個(gè)元素比它大，則繼續(xù)與左邊第二個(gè)元素比較下去，直到遇到不比它大的元素，然后插到這個(gè)元素的右邊。
3、繼續(xù)選取第3，4，….n個(gè)元素,重復(fù)步驟 2 ，選擇適當(dāng)?shù)奈恢貌迦搿?/p>
為方便理解我還準(zhǔn)備了動(dòng)圖：
代碼如下：
int* insertSort(int arr[] ,int n)?
{
if (arr == NULL || n < 2)
{
return arr;
}
for (int i = 1; i < n; i++) {
int temp = arr[i];
int k = i - 1;
while (k >= 0 && arr[k] > temp)
k--;
?//騰出位置插進(jìn)去,要插的位置是 k + 1;
for (int j = i; j > k + 1; j--)
arr[j] = arr[j - 1];
//插進(jìn)去
arr[k + 1] = temp;
}
return arr;
}
性質(zhì)：1、時(shí)間復(fù)雜度：O(n2) 2、空間復(fù)雜度：O(1) 3、穩(wěn)定排序 4、原地排序
3、冒泡排序
1、把第一個(gè)元素與第二個(gè)元素比較，如果第一個(gè)比第二個(gè)大，則交換他們的位置。接著繼續(xù)比較第二個(gè)與第三個(gè)元素，如果第二個(gè)比第三個(gè)大，則交換他們的位置….
我們對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)，這樣一趟比較交換下來之后，排在最右的元素就會(huì)是最大的數(shù)。
除去最右的元素，我們對(duì)剩余的元素做同樣的工作，如此重復(fù)下去，直到排序完成。
為方便理解我還準(zhǔn)備了動(dòng)圖：
代碼如下
int* bubbleSort(int arr[],int n) {
?if (arr == NULL || n < 2)
?{
?return arr;
?}
?for (int i = 0; i < n; i++)
? ? ? ? ?{
?for (int j = 0; j < n - i - 1; j++)
? ? ? ? ? ? ? ? {
?if (arr[j + 1] < arr[j])
? ? ? ? ? ? ? ? ? ? ? ?{
?int t = arr[j];
?arr[j] = arr[j + 1];
arr[j + 1] = t;
}
}
}
?return arr;
}
性質(zhì)：1、時(shí)間復(fù)雜度：O(n2) 2、空間復(fù)雜度：O(1) 3、穩(wěn)定排序 4、原地排序
優(yōu)化一下冒泡排序的算法
假如從開始的第一對(duì)到結(jié)尾的最后一對(duì)，相鄰的元素之間都沒有發(fā)生交換的操作，這意味著右邊的元素總是大于等于左邊的元素，此時(shí)的數(shù)組已經(jīng)是有序的了，我們無需再對(duì)剩余的元素重復(fù)比較下去了。
代碼如下：
int* bubbleSort1(int arr[] ,int n) {
?if (arr == NULL || n < 2)
?{
?return arr;
?}
?for (int i = 0; i < n; i++)
?{
?int flag = 1;
?for (int j = 0; j < n - i - 1; j++)
?{
?if (arr[j + 1] < arr[j])
?{
?flag = 0;
?int t = arr[j];
?arr[j] = arr[j + 1];
?arr[j + 1] = t;
}
}
?//一趟下來是否發(fā)生位置交換
if (flag)
break;
}
?return arr;
}
4、希爾排序
希爾排序可以說是插入排序的一種變種。無論是插入排序還是冒泡排序，如果數(shù)組的最大值剛好是在第一位，要將它挪到正確的位置就需要 n - 1 次移動(dòng)。也就是說，原數(shù)組的一個(gè)元素如果距離它正確的位置很遠(yuǎn)的話，則需要與相鄰元素交換很多次才能到達(dá)正確的位置，這樣是相對(duì)比較花時(shí)間了。
希爾排序就是為了加快速度簡(jiǎn)單地改進(jìn)了插入排序，交換不相鄰的元素以對(duì)數(shù)組的局部進(jìn)行排序。
希爾排序的思想是采用插入排序的方法，先讓數(shù)組中任意間隔為 h 的元素有序，剛開始 h 的大小可以是 h = n / 2,接著讓 h = n / 4，讓 h 一直縮小，當(dāng) h = 1 時(shí)，也就是此時(shí)數(shù)組中任意間隔為1的元素有序，此時(shí)的數(shù)組就是有序的了。
為方便理解我還準(zhǔn)備了圖片：
代碼如下
void insertI(int arr[], int h, int i);
int* shellSort(int arr[],int n) {
?if (arr == NULL || n < 2) return arr;
?// 對(duì)每組間隔為 h的分組進(jìn)行排序，剛開始 h = n / 2;
?for (int h = n / 2; h > 0; h /= 2) {
?//對(duì)各個(gè)局部分組進(jìn)行插入排序
?for (int i = h; i < n; i++) {
?// 將arr[i] 插入到所在分組的正確位置上
?insertI(arr, h, i);
}
}
?return arr;
}
?/**
?* 將arr[i]插入到所在分組的正確位置上
?* arr[i]] 所在的分組為 ... arr[i-2*h],arr[i-h], arr[i+h] ...
?*/
?void insertI(int arr[] , int h, int i)
?{
?int temp = arr[i];
?int k;
?for (k = i - h; k > 0 && temp < arr[k]; k -= h)
?{
?arr[k + h] = arr[k];
}
?arr[k + h] = temp;
}
需要注意的是，對(duì)各個(gè)分組進(jìn)行插入的時(shí)候并不是先對(duì)一個(gè)組排序完了再來對(duì)另一個(gè)組排序，而是輪流對(duì)每個(gè)組進(jìn)行排序。
性質(zhì)：1、時(shí)間復(fù)雜度：O(nlogn) 2、空間復(fù)雜度：O(1) 3、非穩(wěn)定排序 4、原地排序
5、歸并排序
將一個(gè)大的無序數(shù)組有序，我們可以把大的數(shù)組分成兩個(gè)，然后對(duì)這兩個(gè)數(shù)組分別進(jìn)行排序，之后在把這兩個(gè)數(shù)組合并成一個(gè)有序的數(shù)組。由于兩個(gè)小的數(shù)組都是有序的，所以在合并的時(shí)候是很快的。
通過遞歸的方式將大的數(shù)組一直分割，直到數(shù)組的大小為 1，此時(shí)只有一個(gè)元素，那么該數(shù)組就是有序的了，之后再把兩個(gè)數(shù)組大小為1的合并成一個(gè)大小為2的，再把兩個(gè)大小為2的合并成4的 ….. 直到全部小的數(shù)組合并起來。
為方便理解我還準(zhǔn)備了動(dòng)圖：
代碼如下：
void merge(int arr[], int left, int mid, int right);
int* mergeSort(int arr[], int left, int right) {
?// 如果 left == right，表示數(shù)組只有一個(gè)元素，則不用遞歸排序
?if (left < right) {
?// 把大的數(shù)組分隔成兩個(gè)數(shù)組
?int mid = (left + right) / 2;
?// 對(duì)左半部分進(jìn)行排序
?arr = mergeSort(arr, left, mid);
?// 對(duì)右半部分進(jìn)行排序
?arr = mergeSort(arr, mid + 1, right);
?//進(jìn)行合并
?merge(arr, left, mid, right);
?}
?return arr;
?}
?// 合并函數(shù)，把兩個(gè)有序的數(shù)組合并起來
// arr[left..mif]表示一個(gè)數(shù)組，arr[mid+1 .. right]表示一個(gè)數(shù)組
?void merge(int arr[], int left, int mid, int right)?
?{
?//先用一個(gè)臨時(shí)數(shù)組把他們合并匯總起來
?int *a = new int[right - left + 1];
?int i = left;
?int j = mid + 1;
?int k = 0;
?while (i <= mid && j <= right)
?{
?if (arr[i] < arr[j])
?{
?a[k++] = arr[i++];
?}
?else
?{
?a[k++] = arr[j++];
?}
?}
?while (i <= mid) a[k++] = arr[i++];
?while (j <= right) a[k++] = arr[j++];
?// 把臨時(shí)數(shù)組復(fù)制到原數(shù)組
?for (i = 0; i < k; i++)
?{
?arr[left++] = a[i];
?}
?}
性質(zhì)：1、時(shí)間復(fù)雜度：O(nlogn) 2、空間復(fù)雜度：O(n) 3、穩(wěn)定排序 4、非原地排序
然而面試官要你寫個(gè)非遞歸式的歸并排序怎么辦？別怕，我這還擼了個(gè)非遞歸式的歸并排序，代碼如下：
?int* mergeSort(int arr[],int n)
?{
?// 子數(shù)組的大小分別為1，2，4，8...
?// 剛開始合并的數(shù)組大小是1，接著是2，接著4....
?for (int i = 1; i < n; i += i)
?{
?//進(jìn)行數(shù)組進(jìn)行劃分
?int left = 0;
?int mid = left + i - 1;
?int right = mid + i;
?//進(jìn)行合并，對(duì)數(shù)組大小為 i 的數(shù)組進(jìn)行兩兩合并
?while (right < n)
?{
?// 合并函數(shù)和遞歸式的合并函數(shù)一樣
?merge(arr, left, mid, right);
?left = right + 1;
?mid = left + i - 1;
?right = mid + i;
?}
?// 還有一些被遺漏的數(shù)組沒合并，千萬別忘了
// 因?yàn)椴豢赡苊總€(gè)字?jǐn)?shù)組的大小都剛好為 i
?if (left < n && mid < n)
?{
?merge(arr, left, mid, n - 1);
?}
?}
?return arr;
?}
6、快速排序
我們從數(shù)組中選擇一個(gè)元素，我們把這個(gè)元素稱之為中軸元素吧，然后把數(shù)組中所有小于中軸元素的元素放在其左邊，所有大于或等于中軸元素的元素放在其右邊，顯然，此時(shí)中軸元素所處的位置的是有序的。也就是說，我們無需再移動(dòng)中軸元素的位置。
從中軸元素那里開始把大的數(shù)組切割成兩個(gè)小的數(shù)組(兩個(gè)數(shù)組都不包含中軸元素)，接著我們通過遞歸的方式，讓中軸元素左邊的數(shù)組和右邊的數(shù)組也重復(fù)同樣的操作，直到數(shù)組的大小為1，此時(shí)每個(gè)元素都處于有序的位置。
為方便理解我還準(zhǔn)備了動(dòng)圖：
代碼如下：
int partition(int arr[], int left, int right);
int* quickSort(int arr[], int left, int right) {
?if (left < right) {
?//獲取中軸元素所處的位置
?int mid = partition(arr, left, right);
?//進(jìn)行分割
?arr = quickSort(arr, left, mid - 1);
?arr = quickSort(arr, mid + 1, right);
?}
?return arr;
?}
int partition(int arr[], int left, int right)?
{
?//選取中軸元素
?int pivot = arr[left];
?int i = left + 1;
?int j = right;
?while (true) {
?// 向右找到第一個(gè)小于等于 pivot 的元素位置
?while (i <= j && arr[i] <= pivot) i++;
?// 向左找到第一個(gè)大于等于 pivot 的元素位置
?while (i <= j && arr[j] >= pivot) j--;
?if (i >= j)
?break;
?//交換兩個(gè)元素的位置，使得左邊的元素不大于pivot,右邊的不小于pivot
?int temp = arr[i];
?arr[i] = arr[j];
?arr[j] = temp;
?}
?arr[left] = arr[j];
?// 使中軸元素處于有序的位置
?arr[j] = pivot;
?return j;
?}
}性質(zhì)：1、時(shí)間復(fù)雜度：O(nlogn) 2、空間復(fù)雜度：O(logn) 3、非穩(wěn)定排序 4、原地排序
7、堆排序
堆的特點(diǎn)就是堆頂?shù)脑厥且粋€(gè)最值，大頂堆的堆頂是最大值，小頂堆則是最小值。
堆排序就是把堆頂?shù)脑嘏c最后一個(gè)元素交換，交換之后破壞了堆的特性，我們?cè)侔讯阎惺Ｓ嗟脑卦俅螛?gòu)成一個(gè)大頂堆，然后再把堆頂元素與最后第二個(gè)元素交換….如此往復(fù)下去，等到剩余的元素只有一個(gè)的時(shí)候，此時(shí)的數(shù)組就是有序的了。
為方便理解我還準(zhǔn)備了動(dòng)圖：
代碼如下：
void downAdjust(int arr[], int parent, int n);
int* headSort(int arr[] ,int n)
{
//構(gòu)建大頂堆
for (int i = (n - 2) / 2; i >= 0; i--) {
downAdjust(arr, i, n - 1);
}
//進(jìn)行堆排序
for (int i = n - 1; i >= 1; i--) {
// 把堆頂元素與最后一個(gè)元素交換
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
// 把打亂的堆進(jìn)行調(diào)整，恢復(fù)堆的特性
downAdjust(arr, 0, i - 1);
}
return arr;
}
//下沉操作
void downAdjust(int arr[], int parent, int n) {
//臨時(shí)保存要下沉的元素
int temp = arr[parent];
//定位左孩子節(jié)點(diǎn)的位置
int child = 2 * parent + 1;
//開始下沉
while (child <= n) {
// 如果右孩子節(jié)點(diǎn)比左孩子大，則定位到右孩子
if (child + 1 <= n && arr[child] < arr[child + 1])
child++;
// 如果孩子節(jié)點(diǎn)小于或等于父節(jié)點(diǎn)，則下沉結(jié)束
if (arr[child] <= temp) break;
// 父節(jié)點(diǎn)進(jìn)行下沉
arr[parent] = arr[child];
parent = child;
child = 2 * parent + 1;
}
arr[parent] = temp;
}
性質(zhì)：1、時(shí)間復(fù)雜度：O(nlogn) 2、空間復(fù)雜度：O(1) 3、非穩(wěn)定排序 4、原地排序
8、計(jì)數(shù)排序
計(jì)數(shù)排序是一種適合于最大值和最小值的差值不是不是很大的排序。
基本思想：就是把數(shù)組元素作為數(shù)組的下標(biāo)，然后用一個(gè)臨時(shí)數(shù)組統(tǒng)計(jì)該元素出現(xiàn)的次數(shù)，例如 temp[i] = m, 表示元素 i 一共出現(xiàn)了 m 次。最后再把臨時(shí)數(shù)組統(tǒng)計(jì)的數(shù)據(jù)從小到大匯總起來，此時(shí)匯總起來是數(shù)據(jù)是有序的。
為方便理解我還準(zhǔn)備了動(dòng)圖：
代碼如下：
int* countSort(int arr[],int n)?
{
if (arr == NULL || n < 2)
return arr;
int max = arr[0];
// 尋找數(shù)組的最大值
for (int i = 1; i < n; i++)
{
if (max < arr[i])
max = arr[i];
}
//創(chuàng)建大小為max的臨時(shí)數(shù)組
int* temp = new int[max + 1];
//統(tǒng)計(jì)元素i出現(xiàn)的次數(shù)
for (int i = 0; i < n; i++) {
temp[arr[i]]++;
}
int k = 0;
//把臨時(shí)數(shù)組統(tǒng)計(jì)好的數(shù)據(jù)匯總到原數(shù)組
for (int i = 0; i <= max; i++) {
for (int j = temp[i]; j > 0; j--) {
arr[k++] = i;
}
}
return arr;
}
性質(zhì)：1、時(shí)間復(fù)雜度：O(n+k) 2、空間復(fù)雜度：O(k) 3、穩(wěn)定排序 4、非原地排序
注：K表示臨時(shí)數(shù)組的大小，下同
優(yōu)化一下
上面的代碼中，我們是根據(jù) max 的大小來創(chuàng)建對(duì)應(yīng)大小的數(shù)組，假如原數(shù)組只有10個(gè)元素，并且最小值為 min = 10000，最大值為 max = 10005，那我們創(chuàng)建 10005 + 1 大小的數(shù)組不是很吃虧，最大值與最小值的差值為 5，所以我們創(chuàng)建大小為6的臨時(shí)數(shù)組就可以了。
也就是說，我們創(chuàng)建的臨時(shí)數(shù)組大小 (max - min + 1)就可以了，然后在把 min作為偏移量。優(yōu)化之后的代碼如下所示：
int* sort(int arr[],int n)?
{
if (arr == NULL || n < 2) return arr;
int min = arr[0];
int max = arr[0];
// 尋找數(shù)組的最大值與最小值
for (int i = 1; i < n; i++) {
if (max < arr[i])
max = arr[i];
if (min > arr[i])
min = arr[i];
}
int d = max - min + 1;
//創(chuàng)建大小為max的臨時(shí)數(shù)組
int* temp = new int[d];
//統(tǒng)計(jì)元素i出現(xiàn)的次數(shù)
for (int i = 0; i < n; i++)
{
temp[arr[i] - min]++;
}
int k = 0;
//把臨時(shí)數(shù)組統(tǒng)計(jì)好的數(shù)據(jù)匯總到原數(shù)組
for (int i = 0; i < d; i++)
{
for (int j = temp[i]; j > 0; j--)
{
arr[k++] = i + min;
}
}
return arr;
}
9、桶排序
桶排序就是把最大值和最小值之間的數(shù)進(jìn)行瓜分，例如分成 10 個(gè)區(qū)間，10個(gè)區(qū)間對(duì)應(yīng)10個(gè)桶，我們把各元素放到對(duì)應(yīng)區(qū)間的桶中去，再對(duì)每個(gè)桶中的數(shù)進(jìn)行排序，可以采用歸并排序，也可以采用快速排序之類的。
之后每個(gè)桶里面的數(shù)據(jù)就是有序的了，我們?cè)谶M(jìn)行合并匯總。
為方便理解我還準(zhǔn)備了圖片：
這里不給大家貼代碼，可以自己找資料嘗試！
性質(zhì)：1、時(shí)間復(fù)雜度：O(n+k) 2、空間復(fù)雜度：O(n+k) 3、穩(wěn)定排序 4、非原地排序
注：k 表示桶的個(gè)數(shù)，下同
10、基數(shù)排序
基數(shù)排序的排序思路是這樣的：先以個(gè)位數(shù)的大小來對(duì)數(shù)據(jù)進(jìn)行排序，接著以十位數(shù)的大小來多數(shù)進(jìn)行排序，接著以百位數(shù)的大小……
排到最后，就是一組有序的元素了。不過，他在以某位數(shù)進(jìn)行排序的時(shí)候，是用“桶”來排序的。
由于某位數(shù)（個(gè)位/十位….，不是一整個(gè)數(shù)）的大小范圍為0-9，所以我們需要10個(gè)桶，然后把具有相同數(shù)值的數(shù)放進(jìn)同一個(gè)桶里，之后再把桶里的數(shù)按照0號(hào)桶到9號(hào)桶的順序取出來，這樣一趟下來，按照某位數(shù)的排序就完成了
為方便理解我還準(zhǔn)備了動(dòng)圖：
代碼如下：
這里不給大家貼代碼，可以自己找資料嘗試！
性質(zhì)：1、時(shí)間復(fù)雜度：O(kn) 2、空間復(fù)雜度：O(n+k) 3、穩(wěn)定排序 4、非原地排序
總結(jié)
用一張圖匯總了10大排序算法的性質(zhì)
如果你是復(fù)習(xí)/學(xué)習(xí)十大排序算法，一定要自己不看示例代碼手動(dòng)實(shí)現(xiàn)一遍，一定要自己不看示例代碼手動(dòng)實(shí)現(xiàn)一遍，一定要自己不看示例代碼手動(dòng)實(shí)現(xiàn)一遍。
