20張圖帶你搞懂十大經(jīng)典排序算法
十大排序算法思路匯總
在面試的過(guò)程中經(jīng)常會(huì)遇到手寫(xiě)排序算法,所以本文就簡(jiǎn)單總結(jié)一下。不對(duì)算法的細(xì)節(jié)做介紹,只做一個(gè)概括性的描述。
交換類(lèi):通過(guò)元素之間的兩兩交換來(lái)實(shí)現(xiàn)排序
插入類(lèi):將數(shù)分為2部分,依次將無(wú)序的數(shù)插入到有序的數(shù)列中
選擇類(lèi):從待排序數(shù)列中找到最小值或者最大值元素,放到已拍好序的序列后面
「計(jì)數(shù)排序和基數(shù)排序可以認(rèn)為是桶排序的一種特殊實(shí)現(xiàn),都不是通過(guò)元素之間的比較來(lái)實(shí)現(xiàn)排序的」
冒泡排序
冒泡排序,從頭開(kāi)始,依次比較數(shù)組中相鄰的2個(gè)元素,如果后面的數(shù)比前面的數(shù)大,則交換2個(gè)數(shù),否則不交換。每進(jìn)行一輪比較,都會(huì)把數(shù)組中最大的元素放到最后面。
如下圖,一輪比較的過(guò)程如下
當(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面試題一般就可以用快排和堆排序來(lái)解決」。我們?cè)谙乱还?jié)手寫(xiě)堆排序來(lái)分析吧
插入排序
將數(shù)組分為2端,有序數(shù)組和無(wú)序數(shù)組,依次將無(wú)序數(shù)組中的值插入到無(wú)序數(shù)組中。
如下圖3 6 7為有序數(shù)組,4 2為無(wú)序數(shù)組。依次將4,2插入到無(wú)序數(shù)組中即可
如圖,插入4的過(guò)程如下
程序怎么劃分有序數(shù)組和無(wú)序數(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;
- }
「可以看到有很多無(wú)用的交換位置的過(guò)程,我們可以先直接定位到要交換的元素,然后進(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ù)組整體有序(剛開(kāi)始移動(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;
- }
堆排序
我們來(lái)手寫(xiě)一下堆排序,首先我們解釋一下什么是堆?
- 堆是一種數(shù)據(jù)結(jié)構(gòu),需要滿足如下幾個(gè)特性
- 堆是一顆完全二叉樹(shù)(生成節(jié)點(diǎn)的順序是從左往右,從上往下依次進(jìn)行)
堆中某個(gè)節(jié)點(diǎn)值總是不大于或者不小于其父節(jié)點(diǎn)的值
「將根結(jié)點(diǎn)最大的堆叫做最大堆或大根堆,根結(jié)點(diǎn)最小的堆叫做最小堆或小根堆」
大根堆和小根堆如下圖所示
假設(shè)有如下一個(gè)完全二叉樹(shù),如何將它調(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)整的過(guò)程稱為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)整過(guò)程和1類(lèi)似)
- 最終4節(jié)點(diǎn)和5節(jié)點(diǎn)進(jìn)行交換。二叉樹(shù)變?yōu)槎?/li>
在實(shí)際開(kāi)發(fā)的過(guò)程中,我們并不會(huì)用樹(shù)這種結(jié)構(gòu)來(lái)表示堆,而是用數(shù)組。通過(guò)下標(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ù)組表示堆,我們寫(xiě)一下對(duì)如下4這個(gè)節(jié)點(diǎn)heapify的過(guò)程
- /**
- * @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è)完全二叉樹(shù)變?yōu)槎涯?」
「只要對(duì)非葉子節(jié)點(diǎn)從左邊往右,從下到上依次進(jìn)行heapify即可。」 如下圖只需要依次對(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);
- }
- }
我們來(lá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)整的過(guò)程,我們?cè)俜治龆雅判虻倪^(guò)程就非常簡(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)的方法」。我就不寫(xiě)實(shí)現(xiàn)了,用圖演示一下流程,有興趣的可以寫(xiě)一下,「大部分語(yǔ)言都會(huì)內(nèi)置堆的實(shí)現(xiàn),即優(yōu)先級(jí)隊(duì)列(Java中為PriorityQueue),所以當(dāng)我們有用到堆的場(chǎng)景時(shí),直接用PriorityQueue即可」
當(dāng)堆插入節(jié)點(diǎn)時(shí),插入的位置是完全二叉樹(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;
- }
「快速排序」
把快速排序的過(guò)程簡(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,說(shuō)明數(shù)組中的元素比較集中,我們就可以用計(jì)數(shù)排序來(lái)解決這個(gè)問(wèn)題,因?yàn)閍rr[i]的最大值10000為,所以我每次直接開(kāi)一個(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ù)排序
新開(kāi)辟一個(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í),我們就得開(kāi)辟一個(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]--;
- }
- }
- }
「面試過(guò)程中經(jīng)常會(huì)遇到求一個(gè)數(shù)組中的眾數(shù)時(shí),就可以用計(jì)數(shù)排序的思想來(lái)解決」
基數(shù)排序
「面試過(guò)程中快拍和歸并排序問(wèn)的比較多,應(yīng)用場(chǎng)景也比較多」,基數(shù)排序基本沒(méi)被問(wèn)到,不做解釋了。
桶排序
「前面我們提到的計(jì)數(shù)排序和基數(shù)排序可以說(shuō)是桶排序思想的一種特殊體現(xiàn),就是不需要進(jìn)行數(shù)組元素之間的比較」?;緵](méi)被問(wèn)到,不做解釋了
各種排序算法的應(yīng)用
面試中常問(wèn)的Top k問(wèn)題,就可以先排序,然后求出Top k的元素。各種排序算法的效率如下圖片「更高效的思路是用堆和快排。Top K問(wèn)題問(wèn)法很多,本質(zhì)思路都一樣,例如求前K個(gè)最大的元素,求前K個(gè)最小的元素,求前K個(gè)高頻元素」
本文轉(zhuǎn)載自微信公眾號(hào)「Java識(shí)堂」,可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系Java識(shí)堂公眾號(hào)。