八大經(jīng)典排序算法入門

排序算法入門

????在我們初學(xué)算法的時(shí)候，最先接觸到的就是排序算法
，這些排序算法應(yīng)用十分廣泛，而且是很多算法的基礎(chǔ)，可以說是每個(gè)程序員都必須得掌握的了。今天小編就來帶你一舉拿下經(jīng)典的八大排序算法，每種算法都會(huì)有算法思想描述，動(dòng)圖演示，代碼實(shí)現(xiàn)，復(fù)雜度及穩(wěn)定性分析等。

01冒泡排序



1. 原理

假如我們要將一個(gè)無序數(shù)列升序排列，那么冒泡排序的思想就是將“大”的元素經(jīng)過交換慢慢“浮”到數(shù)列頂端，具體步驟如下：

? ?a.
從第一個(gè)元素開始，比較該元素與它的下一個(gè)元素的大小，如果第一個(gè)大于第二個(gè)就交換兩個(gè)元素的位置，一直比較到序列末尾，我們稱這個(gè)為一輪排序過程，此時(shí)我們可以將數(shù)組分成未排序部分和有序部分（當(dāng)前只有一個(gè)最大值）；

? ?b. 對(duì)數(shù)組的未排序部分執(zhí)行一輪冒泡排序，最大值加入有序部分（排在數(shù)組倒數(shù)第二位）；

? ?c. 繼續(xù)對(duì)未排序數(shù)組執(zhí)行上述操作，直到整個(gè)數(shù)組有序。

2. 演示





3. 代碼實(shí)現(xiàn)

?
1 public static int[] bubbleSort(int[] array) { 2 if (array.length == 0) 3
return array; 4 for (int i = 0; i < array.length; i++){ 5 boolean isSwap =
false; 6 for (int j = 0; j < array.length - 1 - i; j++) 7 if (array[j + 1] <
array[j]) { 8 int temp = array[j + 1]; 9 array[j + 1] = array[j]; 10 array[j] =
temp;11 isSwap = true; 12 } 13 if(!isSwap) 14 break; 15 } 16 return array; 17
}18
?

4. 時(shí)間復(fù)雜度

冒泡排序平均時(shí)間復(fù)雜度為O(n^2)，最好時(shí)間復(fù)雜度為O(n)，最壞時(shí)間復(fù)雜度為O(n^2)。

最好情況：如果待排序元素本來是正序的，那么一趟冒泡排序就可以完成排序工作，比較和移動(dòng)元素的次數(shù)分別是 (n - 1) 和
0，因此最好情況的時(shí)間復(fù)雜度為O(n)。

最壞情況：如果待排序元素本來是逆序的，需要進(jìn)行 (n - 1) 趟排序，所需比較和移動(dòng)次數(shù)分別為 n * (n - 1) / 2和 3 * n *
(n-1) / 2。因此最壞情況下的時(shí)間復(fù)雜度為O(n^2)。

5. 空間復(fù)雜度

? ?冒泡排序使用了常數(shù)空間，空間復(fù)雜度為O(1)

6. 穩(wěn)定性

? ?當(dāng) array[j] == array[j+1] 的時(shí)候，我們不交換 array[i] 和 array[j]，所以冒泡排序是穩(wěn)定的。

02選擇排序



1. 原理

選擇排序是從未排序序列中找到最?。ù螅┰?，放到排序序列起始位置，然后從剩余未排序序列中繼續(xù)找最?。ù螅┰兀诺揭雅判蛐蛄械哪┪?，具體步驟如下：

? ?a. 初始時(shí)，整個(gè)數(shù)組為無序數(shù)組A[0...n-1]，有序數(shù)組為空；

? ?b. 第i趟排序（i=0,1,...,n-2），從A[i+1...n-1]中找到最小的元素，將它與第i個(gè)元素交換；

? ?c. i=n-1時(shí)，排序結(jié)束。

2. 演示



3. 代碼實(shí)現(xiàn)

?
1 public static int[] selectionSort(int[] array) { 2 if (array.length == 0)
3 return array; 4 for (int i = 0; i < array.length; i++) { 5 int minIndex = i;
6 for (int j = i; j < array.length; j++) { 7 if (array[j] < array[minIndex])
8 minIndex = j; 9 } 10 int temp = array[minIndex]; 11 array[minIndex] =
array[i];12 array[i] = temp; 13 } 14 return array; 15 }
?

4. 時(shí)間復(fù)雜度

? ?簡(jiǎn)單選擇排序平均時(shí)間復(fù)雜度為O(n^2)，最好時(shí)間復(fù)雜度為O(n^2)，最壞時(shí)間復(fù)雜度為O(n^2)。

最好情況：如果待排序元素本來是正序的，則移動(dòng)元素次數(shù)為 0，但需要進(jìn)行 n * (n - 1) / 2 次比較。

最壞情況：如果待排序元素中第一個(gè)元素最大，其余元素從小到大排列，則仍然需要進(jìn)行 n * (n - 1) / 2 次比較，且每趟排序都需要移動(dòng) 3
次元素，即移動(dòng)元素的次數(shù)為3 * (n - 1)次。

需要注意的是，簡(jiǎn)單選擇排序過程中需要進(jìn)行的比較次數(shù)與初始狀態(tài)下待排序元素的排列情況無關(guān)。

5. 空間復(fù)雜度

? ?簡(jiǎn)單選擇排序使用了常數(shù)空間，空間復(fù)雜度為O(1)

6. 穩(wěn)定性

? ?簡(jiǎn)單選擇排序不穩(wěn)定，比如序列 2、4、2、1，我們知道第一趟排序第 1 個(gè)元素 2 會(huì)和 1 交換，那么原序列中 2 個(gè) 2
的相對(duì)前后順序就被破壞了，所以簡(jiǎn)單選擇排序不是一個(gè)穩(wěn)定的排序算法。

03插入排序



1. 原理

對(duì)未排序的序列，在已排序的序列中從后向前掃描，找到相應(yīng)的位置插入，具體步驟如下：

? ?a. 從第一個(gè)元素開始，認(rèn)為該元素已經(jīng)被排序；

? ?b. 取出未排序數(shù)組的第一個(gè)元素a，在已經(jīng)排序的元素序列中從后先前掃描，如果該元素大于a，將該元素移到下一個(gè)位置；

? ?c.繼續(xù)向前找直到找到一個(gè)元素小于或等于a，則將a插入該元素后面；

????d. 重復(fù)步驟b,c，直到未排序序列為空。

2. 演示



?

3. 代碼實(shí)現(xiàn)

?
1 public static int[] insertionSort(int[] array) { 2 if (array.length == 0)
3 return array; 4 int current; 5 for (int i = 1; i < array.length; i++) { 6
current = array[i]; 7 int preIndex = i - 1; 8 while (preIndex >= 0 && current
< array[preIndex]) { 9 array[preIndex + 1] = array[preIndex]; 10 preIndex--; 11
}12 array[preIndex + 1] = current; 13 } 14 return array; 15 }
?

4. 時(shí)間復(fù)雜度

? ?直接插入排序平均時(shí)間復(fù)雜度為O(n^2)，最好時(shí)間復(fù)雜度為O(n)，最壞時(shí)間復(fù)雜度為O(n^2)。

最好情況：如果待排序元素本來是正序的，則移動(dòng)元素次數(shù)為 0，但需要進(jìn)行(n - 1)次比較。

最壞情況：如果待排序元素本來就是逆序，需要進(jìn)行(n-1)趟排序，比較和移動(dòng)的次數(shù)分別是n*(n-1)/2 和
n*(n-1)/2，所以最壞情況下時(shí)間復(fù)雜度為O(n^2)。

5. 空間復(fù)雜度

? ?直接插入排序使用了常數(shù)空間，空間復(fù)雜度為O(1)

6. 穩(wěn)定性

? ?直接插入排序是穩(wěn)定的。

04希爾排序



1. 原理

希爾排序是第一個(gè)突破O(n^2)的排序算法，是直接插入排序的改進(jìn)算法，是一種縮小增量排序，具體步驟如下：

? ?a. 將整個(gè)序列分割成gap個(gè)子序列（gap初始值一般取len/2），每個(gè)子序列由位置相差為gap的元素組成，每個(gè)子系列有n/gap個(gè)元素；

? ?b. 對(duì)每一個(gè)子序列分別進(jìn)行直接插入排序，然后縮減gap為原來的一般在進(jìn)行插排；

? ?c.當(dāng)gap==1時(shí)，希爾排序變成直接插入排序，而此時(shí)序列已經(jīng)基本有序，效率很高；

2. 演示



?

?

3. 代碼實(shí)現(xiàn)
1 public static int[] ShellSort(int[] array) { 2 int len = array.length; 3
if(len == 0) 4 return array; 5 int current, gap = len / 2; 6 while (gap > 0)
{ 7 for (int i = gap; i < len; i++) { 8 current = array[i]; 9 int preIndex =
i - gap; 10 while (preIndex >= 0 && array[preIndex] > current) { 11
array[preIndex + gap] = array[preIndex]; 12 preIndex -= gap; 13 } 14
array[preIndex + gap] = current; 15 } 16 gap /= 2; 17 } 18 return array; 19 }
?

4. 時(shí)間復(fù)雜度

? ?希爾排序平均時(shí)間復(fù)雜度為O(nlogn)，最好時(shí)間復(fù)雜度為O(nlogn)，最壞時(shí)間復(fù)雜度為O(nlogn)。其時(shí)間復(fù)雜度與增量序列的選取有關(guān)。

5. 空間復(fù)雜度

? ?希爾排序使用了常數(shù)空間，空間復(fù)雜度為O(1)

6. 穩(wěn)定性

? ?相同元素可能在不同的子序列中進(jìn)行插入排序，穩(wěn)定性會(huì)被打亂。

?

05歸并排序

1. 原理

歸并排序是采用分治法的排序算法，主要思想是將已有序的子序列合并成更長(zhǎng)的有序序列，具體步驟如下：

? ?a. 將長(zhǎng)度為n的序列分成兩個(gè)長(zhǎng)度為n/2的子序列；

? ?b. 對(duì)這兩個(gè)子序列分別采用歸并排序；

? ?c.將兩個(gè)排好序的子序列合并成一個(gè)排序序列；

2. 演示



3. 代碼實(shí)現(xiàn)

?
1 public static int[] MergeSort(int[] array) { 2 if (array.length < 2) return
array; 3 int mid = array.length / 2; 4 int[] left = Arrays.copyOfRange(array,
0, mid); 5 int[] right = Arrays.copyOfRange(array, mid, array.length); 6
return merge(MergeSort(left), MergeSort(right)); 7 } 8 public static int[]
merge(int[] left, int[] right) { 9 int[] result = new int[left.length +
right.length];10 int i = 0,j = 0,k = 0; 11 while (i < left.length && j <
right.length) {12 if (left[i] <= right[j]) { 13 result[k++] = left[i++]; 14 }
else { 15 result[k++] = right[j++]; 16 } 17 } 18 while (i < left.length) { 19
result[k++] = left[i++]; 20 } 21 while (j < right.length) { 22 result[k++] =
right[j++]; 23 } 24 return result; 25 }
?

4. 時(shí)間復(fù)雜度

? ?歸并排序平均時(shí)間復(fù)雜度為O(nlogn)，最好時(shí)間復(fù)雜度為O(nlogn)，最壞時(shí)間復(fù)雜度為O(nlogn)。

5. 空間復(fù)雜度

? ?空間復(fù)雜度為O(n)

6. 穩(wěn)定性

? ?歸并排序是穩(wěn)定的。

06快速排序



1. 原理

快速排序就是給基準(zhǔn)數(shù)找到其正確的索引位置的過程，它其實(shí)是基于分治的思想，具體步驟如下：

? ?a. 在數(shù)組中選擇一個(gè)基準(zhǔn)點(diǎn)（基準(zhǔn)點(diǎn)的選取可能影響效率）；

? ?b.
分別從數(shù)組兩端掃描，left指向起始位置，right指向末尾，先從后向前掃，如果發(fā)現(xiàn)有元素比該基準(zhǔn)值小，就交換left和right對(duì)應(yīng)元素的值，然后從前往后掃，如果發(fā)現(xiàn)有元素比該基準(zhǔn)值大，就交換left和right對(duì)應(yīng)元素值，如此往復(fù)，直到left>=right，然后把基準(zhǔn)值放到left索引的位置；

? ?c.以基準(zhǔn)值最終索引的位置為分割點(diǎn)，分別遞歸地對(duì)前后兩部分進(jìn)行排序；

2. 演示



?

?

3. 代碼實(shí)現(xiàn)
1 public static void Quicksort(int array[], int left, int right) { 2 if(left
< right){ 3 int pos = partition(array, left, right); 4 Quicksort(array, left,
pos - 1); 5 Quicksort(array, pos + 1, right); 6 } 7 } 8 public static int
partition(int[] array,int left,int right) { 9 int key = array[left]; 10 while
(left < right) { 11 while(left < right && array[left] <= key ) 12 left++; 13
array[right] = array[left]; 14 while(left <right && array[right] >= key) 15
right--; 16 array[left] = array[right]; 17 } 18 array[left] = key; 19 return
left;20 }
?

4. 時(shí)間復(fù)雜度

? ?快速排序平均時(shí)間復(fù)雜度為O(nlogn)，最好時(shí)間復(fù)雜度為O(nlogn)，最壞時(shí)間復(fù)雜度為O(n^2)。

5. 空間復(fù)雜度

?
?主要考慮遞歸時(shí)使用的?？臻g，最好情況下partition每次恰好能均分序列，空間復(fù)雜度為O(logn),最壞情況下，退化為冒泡排序，空間復(fù)雜度為O(n)，平均為O(logn).

6. 穩(wěn)定性

? ?快速排序是不穩(wěn)定的。

07堆排序



1. 原理

堆排序是基于堆這種數(shù)據(jù)結(jié)構(gòu)的排序算法，將數(shù)組看作一棵完全二叉樹的存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中父節(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的關(guān)系選取最大（?。┰?，具體步驟如下：

? ?a. 將數(shù)組構(gòu)建成大頂堆，此時(shí)最大元素是堆頂元素；

? ?b. 將堆頂元素與最后一個(gè)元素交換，然后對(duì)堆中除最后一個(gè)元素以外的元素重新調(diào)整為一個(gè)大根堆；

? ?c.重復(fù)b，堆中只有一個(gè)元素；

2. 演示



?

3. 代碼實(shí)現(xiàn)
1 public static int[] HeapSort(int[] array) { 2 len = array.length; 3 if
(len == 0)return array; 4 buildMaxHeap(array); 5 while (len > 0) { 6
swap(array, 0, len - 1); 7 len--; 8 adjustHeap(array, 0); 9 } 10 return
array;11 } 12 public static void adjustHeap(int[] array, int i) { 13 int
maxIndex = i; 14 if (2 * i + 1 < len && array[2 * i + 1] > array[maxIndex]) 15
maxIndex = 2 * i + 1; 16 if (2 * i + 2 < len && array[2 * i + 2] >
array[maxIndex])17 maxIndex = 2 * i + 2; 18 if (maxIndex != i) { 19
swap(array, maxIndex, i);20 adjustHeap(array, maxIndex); 21 } 22 } 23 public
static void buildMaxHeap(int[] array) { 24 for (int i = (len - 2) / 2; i >= 0;
i--) { 25 adjustHeap(array, i); 26 } 27 }
?

4. 時(shí)間復(fù)雜度

? ?堆排序平均時(shí)間復(fù)雜度為O(nlogn)，最好時(shí)間復(fù)雜度為O(nlogn)，最壞時(shí)間復(fù)雜度為O(nlogn)。

5. 空間復(fù)雜度

? ?堆排序使用常數(shù)空間O(1).

6. 穩(wěn)定性

? ?堆排序是不穩(wěn)定的。

08計(jì)數(shù)排序



1. 原理


計(jì)數(shù)排序不是基于比較的排序算法，它要求輸入數(shù)據(jù)必須是有確定范圍的整數(shù)，主要原理是將輸入數(shù)據(jù)轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中，是一種線性時(shí)間復(fù)雜度的排序，具體步驟如下：

? ?a. 找出數(shù)組中的最大和最小元素；

? ?b. 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入計(jì)數(shù)數(shù)組C的第i項(xiàng)；

? ?c.對(duì)所有計(jì)數(shù)進(jìn)行累加，從計(jì)數(shù)數(shù)組的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加；

????d. 反向填充數(shù)組，每個(gè)元素i放在新數(shù)組的C[i]位置，每放一個(gè)元素就將C[i]減去1.

2. 演示



?

3. 代碼實(shí)現(xiàn)
1 public static int[] CountingSort(int[] array) { 2 if (array.length == 0)
return array; 3 int bias, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; 4
for (int i = 0; i < array.length; i++) { 5 max = Math.max(max, array[i]); 6
min = Math.min(min, array[i]); 7 } 8 bias = -min; 9 int[] bucket = new int
[max - min + 1]; 10 Arrays.fill(bucket, 0); 11 for (int i = 0; i <
array.length; i++) { 12 bucket[array[i] + bias]++; 13 } 14 int index = 0, i = 0
;15 while (index < array.length) { 16 if (bucket[i] != 0) { 17 array[index] = i
- bias; 18 bucket[i]--; 19 index++; 20 } else 21 i++; 22 } 23 return array; 24
}
?

4. 時(shí)間復(fù)雜度

? ?計(jì)數(shù)排序時(shí)間復(fù)雜度為O(n+k)，n為遍歷一趟數(shù)組計(jì)數(shù)過程的復(fù)雜度，k為遍歷一趟桶取出元素過程的時(shí)間復(fù)雜度。

5. 空間復(fù)雜度

? ?計(jì)數(shù)排序使用空間O(k)，k為桶數(shù)組的長(zhǎng)度。

6. 穩(wěn)定性

? ?堆排序是穩(wěn)定的。

?

?

? ? ? ? ? 關(guān)注我 獲取更多知識(shí)



長(zhǎng)按掃碼關(guān)注你點(diǎn)的每個(gè)贊，我都認(rèn)真當(dāng)成了喜歡

?

• ? 上一篇：認(rèn)識(shí)JVM的內(nèi)存分配
• ? 下一篇：了解一下Spring中用了哪些設(shè)計(jì)模式？這樣回答面試官才穩(wěn)