十大排序算法--多圖預警

? <> <> <> <>
十大排序算法

?

* 十大排序算法
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e58d81e5a4a7e68e92e5ba8fe7ae97e6b395_1>
* 簡單的排序算法
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e7ae80e58d95e79a84e68e92e5ba8fe7ae97e6b395_2>
* 插入排序
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e68f92e585a5e68e92e5ba8f_3>
* 冒泡排序
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e58692e6b3a1e68e92e5ba8f_4>
* 選擇排序
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e98089e68ba9e68e92e5ba8f_5>
* 高效的比較排序算法
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e9ab98e69588e79a84e6af94e8be83e68e92e5ba8fe7ae97e6b395_6>
* 希爾排序
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e5b88ce5b094e68e92e5ba8f_7>
* 快速排序
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e5bfabe9809fe68e92e5ba8f_8>
* 歸并排序
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e5bd92e5b9b6e68e92e5ba8f_9>
* 堆排序
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e5a086e68e92e5ba8f_10>
* 犧牲空間的線性排序算法
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e789bae789b2e7a9bae997b4e79a84e7babfe680a7e68e92e5ba8fe7ae97e6b395_11>
* 計數(shù)排序
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e8aea1e695b0e68e92e5ba8f_12>
* 桶排序
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e6a1b6e68e92e5ba8f_13>
* 基數(shù)排序
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e59fbae695b0e68e92e5ba8f_14>
* 綜合分析
<https://www.cnblogs.com/jiaweixie/p/11286968.html#e7bbbce59088e58886e69e90_15>
?
<> <> <> <>
簡單的排序算法

Θ(n^2)
<> <> <> <>
插入排序

* 動畫演示
?

enter description here
?

*
原理


將數(shù)組看成兩部分，一部分為已排序好的數(shù)組，后面的部分為未排序數(shù)組，每次從后面的數(shù)組中取出元素與前面的有序元素一一比較，若小于則向前移動，直到找到正確的位置插入。遍歷后面的數(shù)組直到整個數(shù)組排序完成。

*
代碼
// 準備工作，交換函數(shù) public static void exc(int[] a,int i, int j) { if (a[i]!=a[j]) {
a[i]^=a[j]; a[j]^=a[i]; a[i]^=a[j]; } }// 插入排序 public static void insertSort(int
[] a,int n) { for (int i = 1; i < n; i++) { for (int j = i; j>0&&a[j-1]>a[j];
j--) { exc(a, j, j-1); } } }
*
分析

時間復雜度

* 平均： n×n/4 次比較，n×n/4 次交換
* 最好： n-1 次比較，0次交換
* 最壞： n×n/2 次比較， n×n/2 交換
評價：

? 插入排序與數(shù)組的逆序度有關，最好情況為 O(n)，所以經常與快速排序一起出現(xiàn)，詳見C語言的quickSort的實現(xiàn)
<> <> <> <>
冒泡排序

*
動畫演示



*
原理

就像泡泡一樣，不斷把大的數(shù)字往上浮，遍歷完整個數(shù)組排序即完成。

*
代碼
public static void bubbleSort(int[] a, int n) { boolean flag = true; for (int
i =0; i < n-1&&flag; i++) { flag = false; for (int j = 0; j < n-i-1; j++) { if
(a[j]>a[j+1]) { exc(a, j, j+1); flag=true; } } } }
*
分析

時間復雜度：

* 平均情況下：冒泡比較的次數(shù)約是插入排序的兩倍，移動次數(shù)一致。
* 平均情況下： 冒泡比較的次數(shù)與比較排序是一樣的，移動次數(shù)多出n次。
評價：

大家也看到上述代碼有個標記變量 flag，這是冒泡排序的一種改進，如果在第二次循環(huán)中沒有發(fā)生交換說明排序已經完成，不需要再循環(huán)下去了。
<> <> <> <>
選擇排序

*
動畫演示



*
原理

選擇排序的原理很簡單，就是從需要排序的數(shù)據(jù)中選擇最小的（從小到大排序），然后放在第一個，選擇第二小的放在第二個……

*
代碼
// 選擇排序，穩(wěn)定 public static void selectSort(int[] a,int n) { for (int i = 0; i <
n; i++) {int min=i; for (int j = i+1; j < n; j++) { if(a[min]>a[j]){ min = j; }
}if (min!=i) { exc(a, i, min); } } }
*
分析

時間復雜度：

*
比較的次數(shù)： (n-1)+(n-2)+...+1= n(n-1)/2

*
交換的次數(shù)： n

評價:

* 運行時間與輸入無關，因為前一次的操作，不能為后面提供信息
* 數(shù)據(jù)的移動次數(shù)是最小的 <> <> <> <>
高效的比較排序算法

Θ(nlog?n)
<> <> <> <>
希爾排序

*
圖片演示



*
原理

希爾排序是基于插入排序進行改進，又稱之為遞減增量排序
。在前面中我們知道，插入排序是將小的元素往前挪動位置，并且每次只移動一個位置。那么希爾排序是怎么解決這個問題的呢？

希爾排序的理念和梳排序的理念有點類似。在梳排序中，我們比較距離相差為step的兩個元素來完成交換。在希爾排序中，我們的做法也是類似。我們在數(shù)組中每隔h
取出數(shù)組中的元素，然后進行插入排序。當h=1時，則就是前面所寫的插入排序了。

*
代碼
// 6. 希爾排序 public static void shellSort(int[] a, int n) { int h =1; while (h<n/
3) { // 數(shù)組 1,4,13,40... h = h*3+1; } while (h>=1) { for (int i = h; i < n; i++)
{for(int j=i;j>=h&&a[j-h]>a[j];j-=h){ exc(a, j, j-h); } } h/=3; } }
*
分析

是第一個突破時間復雜度O(n^2)的算法
思路--計算步長，對每次分組進行直接插入排序，減小逆序度
算法時間復雜度在插入排序和快速排序之間
<> <> <> <>
快速排序

*
動畫演示



*
原理

快速排序使用了， Divide and Conquer
（分治）策略，不斷地把數(shù)組分為較大和較小的兩個子序列，然后對每個子序列進行遞歸，直到不可再分。思路就是在拆分的同時進行排序 與 歸并排序不同。

*
步驟：

*
挑選基準值：從數(shù)列中挑出一個元素，稱為“基準”（pivot），

*

分割：重新排序數(shù)列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面（與基準值相等的數(shù)可以到任何一邊）。在這個分割結束之后，對基準值的排序就已經完成。

*
遞歸排序子序列：遞歸地將小于基準值元素的子序列和大于基準值元素的子序列排序。

遞歸到最底部的判斷條件是數(shù)列的大小是零或一，此時該數(shù)列顯然已經有序。

*
代碼
// 第一部分 public static int partition(int[] a,int l,int h) { int mid = l+((h-l)>>
1); int pivot = a[mid]; exc(a, l, mid); int i = l; int j = h+1; while (true) {
while (a[++i]<pivot) { if(i==h) break; } while (a[--j]>pivot) { if(j==l) break;
}if (i>=j) { break; } exc(a, i, j); } exc(a, l, j); return j; } public static
void quickSort(int[] a, int n) { quickSort(a, 0, n-1); } // 第二部分 public static
void quickSort(int[] a, int lo, int h) { if (lo>=h) { return; } int j =
partition(a, lo, h); quickSort(a, lo, j-1); quickSort(a, j+1, h); }
*
分析

快速排序的最壞時間復雜度為O(n^2)，平均時間復雜度為 O(n logn)，快速排序基本上被認為是比較排序算法中，平均性能最好的。
多種語言皆實現(xiàn)了快速排序的類庫。
<> <> <> <>
歸并排序

*
動畫演示



*
原理

采用分治法:

* 分割：遞歸地把當前序列平均分割成兩半。
* 集成：在保持元素順序的同時將上一步得到的子序列集成到一起（歸并）。
* 與快速排序不同的是，歸并是拆分完成后，在合并階段進行排序，而快速排序 是邊拆分邊排序
*
代碼
// 第一部分 合并 public static void merge(int[] a, int low, int mid, int high) { //
第一種寫法 int i = low; int j = mid + 1; int k = 0; int[] a2 = new int[high - low + 1
];while (i <= mid && j <= high) { if (a[i] < a[j]) { a2[k] = a[i]; i++; k++; }
else { a2[k] = a[j]; j++; k++; } } while (i <= mid) { a2[k] = a[i]; i++; k++; }
while (j <= high) { a2[k] = a[j]; j++; k++; } for (k = 0, i = low; i <= high;
k++, i++) { a[i] = a2[k]; } }public static void mergeSort(int[] a, int n) {
mergeSort(a,0, n - 1); } // 第二部分 遞歸 public static void mergeSort(int[] a, int
low,int high) { if (low >= high) return; int mid = (high + low) / 2;
mergeSort(a, low, mid); mergeSort(a, mid +1, high); merge(a, low, mid, high); }
*
分析

歸并排序是一種穩(wěn)定的且十分高效的排序。時間復雜度總是 O(nlogn),不論好壞，但缺點是，它不是原地排序，占用額外的空間，空間復雜度為 O(n)
<> <> <> <>
堆排序

*
動畫演示



*
原理

堆排序是借助堆 <https://baike.baidu.com/item/%E5%A0%86/20606834?fr=aladdin>這一數(shù)據(jù)結構實現(xiàn)的排序



我們利用大頂堆（堆頂元素最大）實現(xiàn)排序，在一個堆中，位置k的結點的父元素的位置是(k+1)/2-1，而它的兩個子節(jié)點的位置分別是2k+1和2k+2
，這樣我們就可以通過計算數(shù)組的索引在樹中上下移動。

思路： 不斷把堆頂?shù)脑嘏c最后的元素交換位置，重新堆化，不斷得到第k(=1,2,3...)大的元素。相當于一個將大的元素 sink(下沉) 的過程。

*
代碼
// 建堆 public static void buildHeap(int[] a, int n) { for (int i = n / 2; i >= 0
; i--) { heapify(a, n -1, i); } } // 堆化 public static void heapify(int[] a, int
n,int i) { while (true) { int maxPos = i; if (i * 2 + 1 <= n && a[i] < a[2 * i +
1]) { maxPos = i * 2 + 1; } if (i * 2 + 2 <= n && a[maxPos] < a[i * 2 + 2]) {
maxPos = i *2 + 2; } if (i == maxPos) { break; } exc(a, i, maxPos); i = maxPos;
} }public static void heapSort(int[] a, int n) { buildHeap(a, n); int k = n - 1;
while (k > 0) { // 交換堆頂元素，把第1,2,3...大元素放到底部 exc(a, 0, k); --k; heapify(a, k, 0
); } }
*
分析

* 時間復雜度一直都是 O(nlogn)，不論最好最壞情況。
* 缺點：
* 不穩(wěn)定算法
* 堆排序的每次排序其數(shù)組逆序度都比其他算法高
* 對內存訪問不友好(不連續(xù)) <> <> <> <>
犧牲空間的線性排序算法

Θ(n)
<> <> <> <>
計數(shù)排序

*
動畫演示



*
原理

計數(shù)排序使用一個額外的數(shù)組C，其中 C 中第i個元素是待排序數(shù)組A中值等于i的元素的個數(shù)。然后根據(jù)數(shù)組C 來將A中的元素排到正確的位置。

tips:當然，如果數(shù)據(jù)比較集中的話，我們大可不必創(chuàng)建那么大的數(shù)組，我們找出最小和最大的元素，以最小的元素作為基底以減小數(shù)組的大小。

*
代碼
// 非比較排序 public static void countSort(int[] a, int n) { int max = a[0]; for (
int i = 0; i < n; i++) { if (a[i] > max) { max = a[i]; } } int[] c = new int
[max +1]; int indexArray = 0; for (int i = 0; i < n; i++) { c[a[i]]++; } for (
int i = 0; i <= max; i++) { if (c[i] != 0) { a[indexArray] = i; c[i]--;
indexArray++; } } } <> <> <> <>
桶排序

*
圖片演示



*
原理


桶排序的基本思想是假設數(shù)據(jù)在[min,max]之間均勻分布，其中min、max分別指數(shù)據(jù)中的最小值和最大值。那么將區(qū)間[min,max]等分成n份，這n個區(qū)間便稱為n個桶。將數(shù)據(jù)加入對應的桶中，然后每個桶內單獨排序。由于桶之間有大小關系，因此可以從大到小(或從小到大)將桶中元素放入到數(shù)組中。

*
代碼
public static void bucketSort(int[] a, int n, int bucketSize) { int max = a[0];
int min = a[1]; for (int v : a) { if (v > max) { max = v; } else if (v < min) {
min = v; } }// 桶的大小 int bucketCount = (max - min) / bucketSize + 1; int
bucket[][] =new int[bucketCount][bucketSize]; int indexArr[] = new int
[bucketCount];// 將數(shù)字放到對應的桶中 for (int v : a) { int j = (v - min) / bucketSize; if
(indexArr[j] == bucket[j].length) { ensureCapacity(bucket, j); }
bucket[j][indexArr[j]++] = v; }// 每個桶快排 // 也可以使用插入保證穩(wěn)定性 int k = 0; for (int i =
0; i < bucketCount; i++) { if (indexArr[i] == 0) { continue; }
quickSort(bucket[i], indexArr[i]);for (int j = 0; j < indexArr[i]; j++) {
a[k++] = bucket[i][j]; } } }// 擴容函數(shù) private static void ensureCapacity(int[][]
bucket,int j) { int[] tempArr = bucket[j]; int[] newArr = new int
[tempArr.length *2]; for (int k = 0; k < tempArr.length; k++) { newArr[k] =
tempArr[k]; } bucket[j] = newArr; }
*
分析

桶排序是線性排序的一種，桶排序的核心就是根據(jù)數(shù)據(jù)的范圍 （m） ,把數(shù)據(jù) （大小為n），盡可能均勻得放到 K個桶
里，每個桶再各自實現(xiàn)排序，然后把桶從小到大的列出來，即完成排序。

* 時間復雜度 O(N+C)，其中C=N*(logN-logK)，空間復雜度為 O(N+K)
* 更適用于外部排序，尤其是當 N很大，而M較小時，比如高考排名，分數(shù)是固定的，從 0-750分，考生人數(shù)很多，用桶排序就能很快得出排名。 <> <>
<> <>
基數(shù)排序

*
動畫演示



*
原理

在日常的使用中，我們接觸基數(shù)排序比較少，它也是桶排序的一種變形 <https://en.wikipedia.org/wiki/Radix_sort>。

它的具體實現(xiàn)分為 LSD (Least sgnificant digital) ， MSD (Most sgnificant digital)
兩種方法，上面的演示是第一種(LSD)，從低位到高位，根據(jù)每一位上的數(shù)字將元素放入桶中，再按順序取出，直到比較完最高位，完成排序。

*
代碼
/** * * @param x 每一位上的值 * @param d 第d位 * @param dg 輔助數(shù)組 * @return 對應的桶的標號 */
public static int getDigit(int x, int d, int[] dg) { return (x / dg[d - 1] % 10
); }/** * * @param a 待排序數(shù)組 * @param n 數(shù)組長度 */ public static void radixSort(int
[] a,int n) { // 最大的數(shù) int max = 0; int j = 0, i = 0; // 默認十進制 final int radix =
10; for (int val : a) { if (val > max) { max = val; } } // 求最大位數(shù) int N; if (max
==0) { N = 1; } else { N = (int) Math.log10(max) + 1; } // 設置輔助數(shù)組 int dg[] = new
int[N + 1]; for (i = 1, dg[0] = 1; i < N + 1; i++) { dg[i] = 10 * dg[i - 1]; }
// 初始化桶 int bucket[][] = new int[radix][n]; int indexArr[] = new int[radix]; for
(int d = 1; d <= N; d++) { for (int var : a) { j = getDigit(var, d, dg);
bucket[j][indexArr[j]++] = var; }int count = 0; for (i = 0; i < radix; i++) { if
(indexArr[i] !=0) { for (int k = 0; k < indexArr[i]; k++) { a[count++] =
bucket[i][k]; } indexArr[i] =0; } } } }
*
分析

時間復雜度為 O(k*n)，空間復雜度為O(n),當處理較大（位數(shù)多）的數(shù)字排序時，比計數(shù)排序更好用。
<> <> <> <>
綜合分析

*
我們可以看出基于比較的排序算法，他的時間復雜度的最好上界是逼近 O(nlogn) 的，這是因為，比較排序可以看成是決策樹，而數(shù)組共有 n! 種排列方式，根據(jù)
斯特林公式 <https://en.wikipedia.org/wiki/Stirling%27s_approximation>
比較排序的時間復雜度的最好上界是接近于 nlogn的

*
我們可以看出基于非比較排序的線性時間排序的思路，大致相同，都是找到與元素匹配的桶，完成排序。都是空間換時間的思想。

文章最后，感謝大家的閱讀，文中若有錯漏之處，請在留言區(qū)積極指出，十分歡迎大家一起交流討論！

另外感謝朋友們的支持，友情鏈接 <https://www.cnblogs.com/xiaohuiduan/> 。

• ? 上一篇：抽象類及接口詳解
• ? 下一篇：【網站公告】.NET Core 版博客站點第二次發(fā)布嘗試