[[433768]]

十大排序算法思路匯總

在面試的過程中經常會遇到手寫排序算法，所以本文就簡單總結一下。不對算法的細節做介紹，只做一個概括性的描述。

交換類：通過元素之間的兩兩交換來實現排序

插入類：將數分為2部分，依次將無序的數插入到有序的數列中

選擇類：從待排序數列中找到最小值或者最大值元素，放到已拍好序的序列后面

「計數排序和基數排序可以認為是桶排序的一種特殊實現，都不是通過元素之間的比較來實現排序的」

冒泡排序

冒泡排序，從頭開始，依次比較數組中相鄰的2個元素，如果后面的數比前面的數大，則交換2個數，否則不交換。每進行一輪比較，都會把數組中最大的元素放到最后面。

如下圖，一輪比較的過程如下

當數組中有n個元素時，只需要進行n輪比較，則整個數組就是有序的

public static void bubbleSort(int[] a) { 
 // 進行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; 
} 

快速排序

快速排序的執行流程主要分為如下三步

從數列中取出一個數作為基準數

分區，將比它大的數全放到它的右邊，小于或等于它的數全放到它的左邊

再對左右區間重復第二步，直到各區間只有一個數

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所指位置向前搜索找到第一個關鍵字小于key的記錄和key互相交換 
        while (left < right && a[right] >= key) { 
            right--; 
        } 
        a[left] = a[right]; 
        // 從low所指位置向后搜索，找到第一個關鍵字大于key的記錄和key互相交換 
        while (left < right && a[left] <= key) { 
            left++; 
        } 
        a[right] = a[left]; 
    } 
    // 放key值，此時left和right相同 
    a[left] = key; 
    return left; 
} 

下圖演示了一次分區的流程

「經典的Top K面試題一般就可以用快排和堆排序來解決」。我們在下一節手寫堆排序來分析吧

插入排序

將數組分為2端，有序數組和無序數組，依次將無序數組中的值插入到無序數組中。

如下圖3 6 7為有序數組，4 2為無序數組。依次將4，2插入到無序數組中即可

如圖，插入4的過程如下

程序怎么劃分有序數組和無序數組呢?可以認為第一個元素為有序數組，后面的值依次插入即可

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; 
} 

「可以看到有很多無用的交換位置的過程，我們可以先直接定位到要交換的元素，然后進行一次交換即可。改進后的插入排序代碼」

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; 
    } 
} 

希爾排序

「希爾排序是基于插入排序改進后的算法。因為當數據移動次數太多時會導致效率低下。所以我們可以先讓數組整體有序(剛開始移動的幅度大一點，后面再小一點)，這樣移動的次數就會降低，進而提高效率」

原文地址：博客園《圖解排序算法(二)之希爾排序》

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; 
        } 
    } 
} 

選擇排序

第一次迭代，將最小的放在數組第0個位置 第二次迭代，將次小的放在數組第1個位置

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; 
} 

堆排序

我們來手寫一下堆排序，首先我們解釋一下什么是堆?

1. 堆是一種數據結構，需要滿足如下幾個特性
2. 堆是一顆完全二叉樹(生成節點的順序是從左往右，從上往下依次進行)

堆中某個節點值總是不大于或者不小于其父節點的值

「將根結點最大的堆叫做最大堆或大根堆，根結點最小的堆叫做最小堆或小根堆」

大根堆和小根堆如下圖所示

假設有如下一個完全二叉樹，如何將它調整為一個堆呢?

可以看到10及其子節點符合條件，3及其子節點符合條件，4這個節點不符合條件。

「所以要對4這個節點進行調整，調整的過程稱為heapify」

• 從4這個節點的左右節點找一個大的節點(即10這個節點)和4這個節點進行交換
• 交換完有可能交換后的節點不符合條件，所以還需要進行調整(調整過程和1類似)
• 最終4節點和5節點進行交換。二叉樹變為堆

在實際開發的過程中，我們并不會用樹這種結構來表示堆，而是用數組。通過下標的特點，可以總結出如下規律

假如一個節點在數組中的節點下標為i，則

父節點下標為：parent = (i - 1) / 2 左節點下標為：c1 = 2 * i + 1 右節點下標為：c2 = 2 * i + 2

所以上圖中的堆，用數組表示為[10, 5, 3, 4, 1, 2, 0]

知道了如何用數組表示堆，我們寫一下對如下4這個節點heapify的過程

/** 
 * @param a 數組 
 * @param n 數組長度 
 * @param i 要進行heapify的節點 
 */ 
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); 
    } 
} 

@Test 
public void heapify() { 
    int[] array = new int[]{4, 10, 3, 5, 1, 2}; 
    // 調整后為 10， 5， 3， 4， 1， 2 
    HeapSort.heapify(array, array.length,0); 

「我們如何把一個完全二叉樹變為堆呢?」

「只要對非葉子節點從左邊往右，從下到上依次進行heapify即可。」 如下圖只需要依次對10，3，4進行heapify即可

public static void buildTree(int[] a) { 
    // 找到最后一個非葉子節點 
    int lastNode = a.length - 1; 
    int parent = (lastNode - 1) / 2; 
    for (int i = parent; i >= 0; i--) { 
        heapify(a, a.length, i); 
    } 
} 

我們來測試一下

@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); 
} 

知道了堆是如何生成以及如何調整的過程，我們再分析堆排序的過程就非常簡單了!

以大頂堆為例，最大值一定是根節點。

1. 將根節點和最后一個葉子節點交換，然后將這個葉子節點移出堆
2. 此時根節點是不符合要求的，所以對根節點進行heapify后，又變成了一個堆了
3. 重復1，2步，就能找出剩余節點中的最大值

因為每次找出的最大值，都是在數組的最后一位，所以我們不需要真正的進行移除堆這個操作，只是進行heapify的時候，數組長度逐漸遞減即可。最終的數組就是升序的

public static void heapSort(int[] a) { 
    // 先構建一個堆 
    buildTree(a); 
    // 每次將堆的根節點和最后一個節點進行交換，然后進行heapify 
    for (int i = a.length - 1; i >= 0; i--) { 
        swap(a, i, 0); 
        heapify(a, i, 0); 
    } 
} 

所以最終一個堆排序的代碼如下

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) { 
        // 找到最后一個非葉子節點 
        int lastNode = a.length - 1; 
        int parent = (lastNode - 1) / 2; 
        for (int i = parent; i >= 0; i--) { 
            heapify(a, a.length, i); 
        } 
    } 
 
    /** 
     * @param a 數組 
     * @param n 數組長度 
     * @param i 要進行heapify的節點 
     */ 
    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; 
    } 
} 

我們這里只演示了一下如何構建一個堆，以及堆排序的流程是怎樣的?

「要實現一個完整的堆，我們還需要提供一個插入節點和刪除根節點的方法」。我就不寫實現了，用圖演示一下流程，有興趣的可以寫一下，「大部分語言都會內置堆的實現，即優先級隊列(Java中為PriorityQueue)，所以當我們有用到堆的場景時，直接用PriorityQueue即可」

堆插入節點

當堆插入節點時，插入的位置是完全二叉樹的最后一個位置。比如我們插入一個新節點，值是8

我們讓8和它的父節點比較，8>5，則讓新節點上浮，和父節點交換位置

交換完后繼續和父節點比較，8<9，則不用調整了

堆刪除節點

堆刪除節點時，刪除的是堆頂的節點。比如我們刪除大頂堆的9節點

為了維持堆的結構，我們把堆的最后一個節點6補到堆頂的位置

接著我們讓堆頂的節點和它的左右孩子節點進行比較，如果左右孩子中最大的一個比節點6大，那么則讓節點6下沉

接著和左右節點進行比較，3<6，則不用調整了

前 K 個高頻元素

題目地址：劍指 Offer 40. 最小的k個數

輸入整數數組 arr ，找出其中最小的 k 個數。例如，輸入4、5、1、6、2、7、3、8這8個數字，則最小的4個數字是1、2、3、4。

輸入：arr = [3,2,1], k = 2 
輸出：[1,2] 或者 [2,1] 

限制：

0 <= k <= arr.length <= 10000 0 <= arr[i] <= 10000

「堆」

維護一個大頂堆 當堆中的元素不夠k時，一直往堆中放元素即可 當堆中的元素大于等于k時，將堆頂的元素和新添加的元素進行比較。如果新添的元素比堆頂的元素小，則應該把堆頂的元素刪除，將新填的元素放入堆，這樣就能保證堆中的元素一直是最小的k個

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; 
} 

「快速排序」

把快速排序的過程簡單改一下就行了，我們根據基準值和k的的位置決定對左段還是右段進行排序即可，而不是對整個數組進行排序

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); 
        } 
        // 根據 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; 
    } 
} 

「計數排序」

因為題目中有這樣一個條件0 <= arr[i] <= 10000，說明數組中的元素比較集中，我們就可以用計數排序來解決這個問題，因為arr[i]的最大值10000為，所以我每次直接開一個10001大的數組

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; 
} 

歸并排序

先把數組拆分為只有一個元素，然后對拆分的數組進行合并，主要合并的時候要保證合并后的數組有序，當合并完成時，整個數組有序

public static void mergeSort(int[] a, int left, int right) { 
    // 將數組分段成只有一個元素 
    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++]; 
        } 
    } 
    // 復制左邊數組剩余的值 
    while (i <= mid) { 
        temp[k++] = a[i++]; 
    } 
    // 復制右邊數組剩余的值 
    while (j <= right) { 
        temp[k++] = a[j++]; 
    } 
    int index = 0; 
    while (left <= right) { 
        a[left++] = temp[index++]; 
    } 
} 

計數排序

新開辟一個數組，num[i]的含義為原數組中值為i的數有num[i]個。所以算法的局限性比較大，只適合數組元素跨度區間不大的場景。

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]--; 
        } 
    } 
} 

上面的算法其實還有個缺陷，但數組中的元素為10000，10001，10002時，我們就得開辟一個10003大小的數組，不現實。所以我們可以改一下映射關系 num[i]的含義為原數組中值為i+min的個數為num[i]

進階版

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]--; 
        } 
    } 
} 

「面試過程中經常會遇到求一個數組中的眾數時，就可以用計數排序的思想來解決」

基數排序

「面試過程中快拍和歸并排序問的比較多，應用場景也比較多」，基數排序基本沒被問到，不做解釋了。

桶排序

「前面我們提到的計數排序和基數排序可以說是桶排序思想的一種特殊體現，就是不需要進行數組元素之間的比較」。基本沒被問到，不做解釋了

各種排序算法的應用

面試中常問的Top k問題，就可以先排序，然后求出Top k的元素。各種排序算法的效率如下圖片「更高效的思路是用堆和快排。Top K問題問法很多，本質思路都一樣，例如求前K個最大的元素，求前K個最小的元素，求前K個高頻元素」

本文轉載自微信公眾號「Java識堂」，可以通過以下二維碼關注。轉載本文請聯系Java識堂公眾號。