20張圖帶你搞懂十大經(jīng)典排序算法
十大排序算法思路匯總
在面試的過程中經(jīng)常會(huì)遇到手寫排序算法，所以本文就簡(jiǎn)單總結(jié)一下。不對(duì)算法的細(xì)節(jié)做介紹，只做一個(gè)概括性的描述。
交換類：通過元素之間的兩兩交換來實(shí)現(xiàn)排序
插入類：將數(shù)分為2部分，依次將無序的數(shù)插入到有序的數(shù)列中
選擇類：從待排序數(shù)列中找到最小值或者最大值元素，放到已拍好序的序列后面
「計(jì)數(shù)排序和基數(shù)排序可以認(rèn)為是桶排序的一種特殊實(shí)現(xiàn)，都不是通過元素之間的比較來實(shí)現(xiàn)排序的」
冒泡排序
冒泡排序，從頭開始，依次比較數(shù)組中相鄰的2個(gè)元素，如果后面的數(shù)比前面的數(shù)大，則交換2個(gè)數(shù)，否則不交換。每進(jìn)行一輪比較，都會(huì)把數(shù)組中最大的元素放到最后面。
如下圖，一輪比較的過程如下
當(dāng)數(shù)組中有n個(gè)元素時(shí)，只需要進(jìn)行n輪比較，則整個(gè)數(shù)組就是有序的
public static void bubbleSort(int[] a) {
// 進(jìn)行i輪比較
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
}
}
}
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
快速排序
快速排序的執(zhí)行流程主要分為如下三步
從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù) 分區(qū)，將比它大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊 再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)
public static void quickSort(int[] a, int left, int right) {
if (left >= right) {
return;
}
int index = sort(a, left, right);
quickSort(a, left, index - 1);
quickSort(a, index + 1, right);
}
public static int sort(int[] a, int left, int right) {
int key = a[left];
while (left < right) {
// 從high所指位置向前搜索找到第一個(gè)關(guān)鍵字小于key的記錄和key互相交換
while (left < right && a[right] >= key) {
right--;
}
a[left] = a[right];
// 從low所指位置向后搜索，找到第一個(gè)關(guān)鍵字大于key的記錄和key互相交換
while (left < right && a[left] <= key) {
left++;
}
a[right] = a[left];
}
// 放key值，此時(shí)left和right相同
a[left] = key;
return left;
}
下圖演示了一次分區(qū)的流程
「經(jīng)典的Top K面試題一般就可以用快排和堆排序來解決」。我們?cè)谙乱还?jié)手寫堆排序來分析吧
插入排序
將數(shù)組分為2端，有序數(shù)組和無序數(shù)組，依次將無序數(shù)組中的值插入到無序數(shù)組中。
如下圖3 6 7為有序數(shù)組，4 2為無序數(shù)組。依次將4，2插入到無序數(shù)組中即可
如圖，插入4的過程如下
程序怎么劃分有序數(shù)組和無序數(shù)組呢？可以認(rèn)為第一個(gè)元素為有序數(shù)組，后面的值依次插入即可
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
for (int j = i; j > 0; j--) {
while (a[j] < a[j - 1]) {
swap(a, j, j - 1);
}
}
}
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
「可以看到有很多無用的交換位置的過程，我們可以先直接定位到要交換的元素，然后進(jìn)行一次交換即可。改進(jìn)后的插入排序代碼」
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int temp = a[i];
int j;
// 查到合適的插入位置，插入即可
for (j = i - 1; j >= 0 && a[j] > temp; j--) {
a[j + 1] = a[j];
}
a[j + 1] = temp;
}
}
希爾排序
「希爾排序是基于插入排序改進(jìn)后的算法。因?yàn)楫?dāng)數(shù)據(jù)移動(dòng)次數(shù)太多時(shí)會(huì)導(dǎo)致效率低下。所以我們可以先讓數(shù)組整體有序（剛開始移動(dòng)的幅度大一點(diǎn)，后面再小一點(diǎn)），這樣移動(dòng)的次數(shù)就會(huì)降低，進(jìn)而提高效率」
圖片原文地址：博客園《圖解排序算法(二)之希爾排序》
public static void shellSort(int[] a) {
for (int step = a.length / 2; step > 0; step /= 2) {
for (int i = step; i < a.length; i++) {
int temp = a[i];
int j;
for (j = i - step; j >= 0 && a[j] > temp ; j -= step) {
a[j + step] = a[j];
}
a[j + step] = temp;
}
}
}
選擇排序
第一次迭代，將最小的放在數(shù)組第0個(gè)位置
第二次迭代，將次小的放在數(shù)組第1個(gè)位置
public static void selectionSort(int[] a) {
for (int i = 0; i < a.length; i++) {
int index = i;
for (int j = i + 1; j < a.length; j++) {
if (a[index] > a[j]) {
index = j;
}
}
if (index != i) {
swap(a, index, i);
}
}
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
堆排序
我們來手寫一下堆排序，首先我們解釋一下什么是堆？
堆是一種數(shù)據(jù)結(jié)構(gòu)，需要滿足如下幾個(gè)特性
堆是一顆完全二叉樹（生成節(jié)點(diǎn)的順序是從左往右，從上往下依次進(jìn)行） 堆中某個(gè)節(jié)點(diǎn)值總是不大于或者不小于其父節(jié)點(diǎn)的值
「將根結(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根結(jié)點(diǎn)最小的堆叫做最小堆或小根堆」
大根堆和小根堆如下圖所示
假設(shè)有如下一個(gè)完全二叉樹，如何將它調(diào)整為一個(gè)堆呢？
可以看到10及其子節(jié)點(diǎn)符合條件，3及其子節(jié)點(diǎn)符合條件，4這個(gè)節(jié)點(diǎn)不符合條件。
「所以要對(duì)4這個(gè)節(jié)點(diǎn)進(jìn)行調(diào)整，調(diào)整的過程稱為heapify」
從4這個(gè)節(jié)點(diǎn)的左右節(jié)點(diǎn)找一個(gè)大的節(jié)點(diǎn)（即10這個(gè)節(jié)點(diǎn)）和4這個(gè)節(jié)點(diǎn)進(jìn)行交換 交換完有可能交換后的節(jié)點(diǎn)不符合條件，所以還需要進(jìn)行調(diào)整（調(diào)整過程和1類似） 最終4節(jié)點(diǎn)和5節(jié)點(diǎn)進(jìn)行交換。二叉樹變?yōu)槎?img class="rich_pages wxw-img" data-fileid="100008243" data-ratio="0.36324167872648333" src="https://filescdn.proginn.com/a4d12870fe01597f41ac04fd4503523f/541eb97c84e113ef08f2ddae1c95ee71.webp" data-type="png" data-w="691" style="border-radius: 6px;display: block;margin: 20px auto;object-fit: contain;box-shadow: rgb(153, 153, 153) 2px 4px 7px;">
在實(shí)際開發(fā)的過程中，我們并不會(huì)用樹這種結(jié)構(gòu)來表示堆，而是用數(shù)組。通過下標(biāo)的特點(diǎn)，可以總結(jié)出如下規(guī)律
假如一個(gè)節(jié)點(diǎn)在數(shù)組中的節(jié)點(diǎn)下標(biāo)為i，則
父節(jié)點(diǎn)下標(biāo)為：parent = (i - 1) / 2 左節(jié)點(diǎn)下標(biāo)為：c1 = 2 * i + 1 右節(jié)點(diǎn)下標(biāo)為：c2 = 2 * i + 2
所以上圖中的堆，用數(shù)組表示為[10, 5, 3, 4, 1, 2, 0]
知道了如何用數(shù)組表示堆，我們寫一下對(duì)如下4這個(gè)節(jié)點(diǎn)heapify的過程
/**
* @param a 數(shù)組
* @param n 數(shù)組長(zhǎng)度
* @param i 要進(jìn)行heapify的節(jié)點(diǎn)
*/
public static void heapify(int[] a, int n, int i) {
// 遞歸出口
if (i >= n) {
return;
}
// 左節(jié)點(diǎn)下標(biāo)
int c1 = 2 * i + 1;
// 右節(jié)點(diǎn)下標(biāo)
int c2 = 2 * i + 2;
int max = i;
if (c1 < n && a[c1] > a[max]) {
max = c1;
}
if (c2 < n && a[c2] > a[max]) {
max = c2;
}
// 將左節(jié)點(diǎn)，右節(jié)點(diǎn)中的最大值和父節(jié)點(diǎn)交換
if (max != i) {
swap(a, max ,i);
heapify(a, n, max);
}
}
@Test
public void heapify() {
int[] array = new int[]{4, 10, 3, 5, 1, 2};
// 調(diào)整后為 10， 5， 3， 4， 1， 2
HeapSort.heapify(array, array.length,0);
}
「我們?nèi)绾伟岩粋€(gè)完全二叉樹變?yōu)槎涯?？?/strong>
「只要對(duì)非葉子節(jié)點(diǎn)從左邊往右，從下到上依次進(jìn)行heapify即可?！?/strong> 如下圖只需要依次對(duì)10，3，4進(jìn)行heapify即可
public static void buildTree(int[] a) {
// 找到最后一個(gè)非葉子節(jié)點(diǎn)
int lastNode = a.length - 1;
int parent = (lastNode - 1) / 2;
for (int i = parent; i >= 0; i--) {
heapify(a, a.length, i);
}
}
我們來測(cè)試一下
@Test
public void buildTree() {
int[] array = new int[]{3, 5, 7, 2, 4, 9, 6};
// 9 5 7 2 4 3 6
HeapSort.buildTree(array);
}
知道了堆是如何生成以及如何調(diào)整的過程，我們?cè)俜治龆雅判虻倪^程就非常簡(jiǎn)單了！
以大頂堆為例，最大值一定是根節(jié)點(diǎn)。
將根節(jié)點(diǎn)和最后一個(gè)葉子節(jié)點(diǎn)交換，然后將這個(gè)葉子節(jié)點(diǎn)移出堆 此時(shí)根節(jié)點(diǎn)是不符合要求的，所以對(duì)根節(jié)點(diǎn)進(jìn)行heapify后，又變成了一個(gè)堆了 重復(fù)1，2步，就能找出剩余節(jié)點(diǎn)中的最大值
因?yàn)槊看握页龅淖畲笾担际窃跀?shù)組的最后一位，所以我們不需要真正的進(jìn)行移除堆這個(gè)操作，只是進(jìn)行heapify的時(shí)候，數(shù)組長(zhǎng)度逐漸遞減即可。最終的數(shù)組就是升序的
public static void heapSort(int[] a) {
// 先構(gòu)建一個(gè)堆
buildTree(a);
// 每次將堆的根節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)進(jìn)行交換，然后進(jìn)行heapify
for (int i = a.length - 1; i >= 0; i--) {
swap(a, i, 0);
heapify(a, i, 0);
}
}
所以最終一個(gè)堆排序的代碼如下
public class HeapSort {
public static void heapSort(int[] a) {
buildTree(a);
for (int i = a.length - 1; i >= 0; i--) {
swap(a, i, 0);
heapify(a, i, 0);
}
}
public static void buildTree(int[] a) {
// 找到最后一個(gè)非葉子節(jié)點(diǎn)
int lastNode = a.length - 1;
int parent = (lastNode - 1) / 2;
for (int i = parent; i >= 0; i--) {
heapify(a, a.length, i);
}
}
/**
* @param a 數(shù)組
* @param n 數(shù)組長(zhǎng)度
* @param i 要進(jìn)行heapify的節(jié)點(diǎn)
*/
public static void heapify(int[] a, int n, int i) {
if (i >= n) {
return;
}
int c1 = 2 * i + 1;
int c2 = 2 * i + 2;
int max = i;
if (c1 < n && a[c1] > a[max]) {
max = c1;
}
if (c2 < n && a[c2] > a[max]) {
max = c2;
}
if (max != i) {
swap(a, max ,i);
heapify(a, n, max);
}
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
我們這里只演示了一下如何構(gòu)建一個(gè)堆，以及堆排序的流程是怎樣的？
「要實(shí)現(xiàn)一個(gè)完整的堆，我們還需要提供一個(gè)插入節(jié)點(diǎn)和刪除根節(jié)點(diǎn)的方法」。我就不寫實(shí)現(xiàn)了，用圖演示一下流程，有興趣的可以寫一下，「大部分語言都會(huì)內(nèi)置堆的實(shí)現(xiàn)，即優(yōu)先級(jí)隊(duì)列（Java中為PriorityQueue），所以當(dāng)我們有用到堆的場(chǎng)景時(shí)，直接用PriorityQueue即可」
堆插入節(jié)點(diǎn)
當(dāng)堆插入節(jié)點(diǎn)時(shí)，插入的位置是完全二叉樹的最后一個(gè)位置。比如我們插入一個(gè)新節(jié)點(diǎn)，值是8
我們讓8和它的父節(jié)點(diǎn)比較，8>5，則讓新節(jié)點(diǎn)上浮，和父節(jié)點(diǎn)交換位置
交換完后繼續(xù)和父節(jié)點(diǎn)比較，8<9，則不用調(diào)整了
堆刪除節(jié)點(diǎn)
堆刪除節(jié)點(diǎn)時(shí)，刪除的是堆頂?shù)墓?jié)點(diǎn)。比如我們刪除大頂堆的9節(jié)點(diǎn)
為了維持堆的結(jié)構(gòu)，我們把堆的最后一個(gè)節(jié)點(diǎn)6補(bǔ)到堆頂?shù)奈恢?/p>
接著我們讓堆頂?shù)墓?jié)點(diǎn)和它的左右孩子節(jié)點(diǎn)進(jìn)行比較，如果左右孩子中最大的一個(gè)比節(jié)點(diǎn)6大，那么則讓節(jié)點(diǎn)6下沉
接著和左右節(jié)點(diǎn)進(jìn)行比較，3<6，則不用調(diào)整了
前 K 個(gè)高頻元素
題目地址：劍指 Offer 40. 最小的k個(gè)數(shù)
輸入整數(shù)數(shù)組 arr ，找出其中最小的 k 個(gè)數(shù)。例如，輸入4、5、1、6、2、7、3、8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1、2、3、4。
輸入：arr = [3,2,1], k = 2
輸出：[1,2] 或者 [2,1]
限制：
0 <= k <= arr.length <= 10000 0 <= arr[i] <= 10000
「堆」
維護(hù)一個(gè)大頂堆 當(dāng)堆中的元素不夠k時(shí)，一直往堆中放元素即可 當(dāng)堆中的元素大于等于k時(shí)，將堆頂?shù)脑睾托绿砑拥脑剡M(jìn)行比較。如果新添的元素比堆頂?shù)脑匦?，則應(yīng)該把堆頂?shù)脑貏h除，將新填的元素放入堆，這樣就能保證堆中的元素一直是最小的k個(gè)
public int[] getLeastNumbers(int[] arr, int k) {
if (arr.length == 0 || k == 0) {
return new int[0];
}
PriorityQueue<Integer> queue = new PriorityQueue<>((num1, num2) -> num2 - num1);
for (int num : arr) {
if (queue.size() < k) {
queue.add(num);
} else if (num < queue.peek()) {
queue.poll();
queue.add(num);
}
}
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = queue.poll();
}
return result;
}
「快速排序」
把快速排序的過程簡(jiǎn)單改一下就行了，我們根據(jù)基準(zhǔn)值和k的的位置決定對(duì)左段還是右段進(jìn)行排序即可，而不是對(duì)整個(gè)數(shù)組進(jìn)行排序
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (arr.length == 0 || k == 0) {
return new int[0];
}
return quickSort(arr, 0, arr.length - 1, k - 1);
}
public int[] quickSort(int[] nums, int left, int right, int k) {
int index = sort(nums, left, right);
if (index == k) {
return Arrays.copyOf(nums, k + 1);
}
// 根據(jù) index 和 k 的位置決定切左段還是右段
return index > k ? quickSort(nums, left, index - 1, k) : quickSort(nums, index + 1, right, k);
}
public int sort(int[] a, int left, int right) {
int key = a[left];
while (left < right) {
while (left < right && a[right] >= key) {
right--;
}
a[left] = a[right];
while (left < right && a[left] <= key) {
left++;
}
a[right] = a[left];
}
a[left] = key;
return left;
}
}
「計(jì)數(shù)排序」
因?yàn)轭}目中有這樣一個(gè)條件0 <= arr[i] <= 10000，說明數(shù)組中的元素比較集中，我們就可以用計(jì)數(shù)排序來解決這個(gè)問題，因?yàn)閍rr[i]的最大值10000為，所以我每次直接開一個(gè)10001大的數(shù)組
public int[] getLeastNumbers(int[] arr, int k) {
if (arr.length == 0 || k == 0) {
return new int[0];
}
int[] countArray = new int[10001];
for (int num : arr) {
countArray[num]++;
}
int[] result = new int[k];
int index = 0;
for (int i = 0; i < countArray.length && index < k; i++) {
while (countArray[i] > 0 && index < k) {
countArray[i]--;
result[index++] = i;
}
}
return result;
}
歸并排序
先把數(shù)組拆分為只有一個(gè)元素，然后對(duì)拆分的數(shù)組進(jìn)行合并，主要合并的時(shí)候要保證合并后的數(shù)組有序，當(dāng)合并完成時(shí)，整個(gè)數(shù)組有序
public static void mergeSort(int[] a, int left, int right) {
// 將數(shù)組分段成只有一個(gè)元素
if (left == right) {
return;
}
int mid = (left + right) / 2;
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
public static void merge(int[] a, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
// 復(fù)制左邊數(shù)組剩余的值
while (i <= mid) {
temp[k++] = a[i++];
}
// 復(fù)制右邊數(shù)組剩余的值
while (j <= right) {
temp[k++] = a[j++];
}
int index = 0;
while (left <= right) {
a[left++] = temp[index++];
}
}
計(jì)數(shù)排序
新開辟一個(gè)數(shù)組，num[i]的含義為原數(shù)組中值為i的數(shù)有num[i]個(gè)。所以算法的局限性比較大，只適合數(shù)組元素跨度區(qū)間不大的場(chǎng)景。
public static void countingSort(int[] a) {
int max = Integer.MIN_VALUE;
for (int num : a) {
max = Integer.max(max, num);
}
int[] count = new int[max + 1];
for (int num : a) {
count[num]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
a[index++] = i;
count[i]--;
}
}
}
上面的算法其實(shí)還有個(gè)缺陷，但數(shù)組中的元素為10000，10001，10002時(shí)，我們就得開辟一個(gè)10003大小的數(shù)組，不現(xiàn)實(shí)。所以我們可以改一下映射關(guān)系 num[i]的含義為原數(shù)組中值為i+min的個(gè)數(shù)為num[i]
進(jìn)階版
public static void countingSort(int[] a) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int num : a) {
max = Integer.max(max, num);
min = Integer.min(min, num);
}
int[] count = new int[max - min + 1];
for (int num : a) {
count[num - min]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
a[index++] = i + min;
count[i]--;
}
}
}
「面試過程中經(jīng)常會(huì)遇到求一個(gè)數(shù)組中的眾數(shù)時(shí)，就可以用計(jì)數(shù)排序的思想來解決」
基數(shù)排序
「面試過程中快拍和歸并排序問的比較多，應(yīng)用場(chǎng)景也比較多」，基數(shù)排序基本沒被問到，不做解釋了。
桶排序
「前面我們提到的計(jì)數(shù)排序和基數(shù)排序可以說是桶排序思想的一種特殊體現(xiàn)，就是不需要進(jìn)行數(shù)組元素之間的比較」?；緵]被問到，不做解釋了
各種排序算法的應(yīng)用
面試中常問的Top k問題，就可以先排序，然后求出Top k的元素。各種排序算法的效率如下
「更高效的思路是用堆和快排。Top K問題問法很多，本質(zhì)思路都一樣，例如求前K個(gè)最大的元素，求前K個(gè)最小的元素，求前K個(gè)高頻元素」