[[433768]]

十大排序算法思路匯總

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

交換類：通過元素之間的兩兩交換來實現(xiàn)排序

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

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

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

冒泡排序

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

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

當(dāng)數(shù)組中有n個元素時，只需要進行n輪比較，則整個數(shù)組就是有序的

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

快速排序

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

從數(shù)列中取出一個數(shù)作為基準數(shù)

分區(qū)，將比它大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊

再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(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所指位置向前搜索找到第一個關(guān)鍵字小于key的記錄和key互相交換 
        while (left < right && a[right] >= key) { 
            right--; 
        } 
        a[left] = a[right]; 
        // 從low所指位置向后搜索，找到第一個關(guān)鍵字大于key的記錄和key互相交換 
        while (left < right && a[left] <= key) { 
            left++; 
        } 
        a[right] = a[left]; 
    } 
    // 放key值，此時left和right相同 
    a[left] = key; 
    return left; 
} 

下圖演示了一次分區(qū)的流程

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

插入排序

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

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

如圖，插入4的過程如下

程序怎么劃分有序數(shù)組和無序數(shù)組呢?可以認為第一個元素為有序數(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; 
} 

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

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

希爾排序

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

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

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個位置 第二次迭代，將次小的放在數(shù)組第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. 堆是一種數(shù)據(jù)結(jié)構(gòu)，需要滿足如下幾個特性
2. 堆是一顆完全二叉樹(生成節(jié)點的順序是從左往右，從上往下依次進行)

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

「將根結(jié)點最大的堆叫做最大堆或大根堆，根結(jié)點最小的堆叫做最小堆或小根堆」

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

假設(shè)有如下一個完全二叉樹，如何將它調(diào)整為一個堆呢?

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

「所以要對4這個節(jié)點進行調(diào)整，調(diào)整的過程稱為heapify」

• 從4這個節(jié)點的左右節(jié)點找一個大的節(jié)點(即10這個節(jié)點)和4這個節(jié)點進行交換
• 交換完有可能交換后的節(jié)點不符合條件，所以還需要進行調(diào)整(調(diào)整過程和1類似)
• 最終4節(jié)點和5節(jié)點進行交換。二叉樹變?yōu)槎?/li>

在實際開發(fā)的過程中，我們并不會用樹這種結(jié)構(gòu)來表示堆，而是用數(shù)組。通過下標的特點，可以總結(jié)出如下規(guī)律

假如一個節(jié)點在數(shù)組中的節(jié)點下標為i，則

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

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

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

/** 
 * @param a 數(shù)組 
 * @param n 數(shù)組長度 
 * @param i 要進行heapify的節(jié)點 
 */ 
public static void heapify(int[] a, int n, int i) { 
    // 遞歸出口 
    if (i >= n) { 
        return; 
    } 
    // 左節(jié)點下標 
    int c1 = 2 * i + 1; 
    // 右節(jié)點下標 
    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é)點，右節(jié)點中的最大值和父節(jié)點交換 
    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)绾伟岩粋€完全二叉樹變?yōu)槎涯?」

「只要對非葉子節(jié)點從左邊往右，從下到上依次進行heapify即可?！?如下圖只需要依次對10，3，4進行heapify即可

public static void buildTree(int[] a) { 
    // 找到最后一個非葉子節(jié)點 
    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); 
} 

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

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

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

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

public static void heapSort(int[] a) { 
    // 先構(gòu)建一個堆 
    buildTree(a); 
    // 每次將堆的根節(jié)點和最后一個節(jié)點進行交換，然后進行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) { 
        // 找到最后一個非葉子節(jié)點 
        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ù)組長度 
     * @param i 要進行heapify的節(jié)點 
     */ 
    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)建一個堆，以及堆排序的流程是怎樣的?

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

堆插入節(jié)點

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

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

交換完后繼續(xù)和父節(jié)點比較，8<9，則不用調(diào)整了

堆刪除節(jié)點

堆刪除節(jié)點時，刪除的是堆頂?shù)墓?jié)點。比如我們刪除大頂堆的9節(jié)點

為了維持堆的結(jié)構(gòu)，我們把堆的最后一個節(jié)點6補到堆頂?shù)奈恢?/p>

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

接著和左右節(jié)點進行比較，3<6，則不用調(diào)整了

前 K 個高頻元素

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

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

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

限制：

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

「堆」

維護一個大頂堆 當(dāng)堆中的元素不夠k時，一直往堆中放元素即可 當(dāng)堆中的元素大于等于k時，將堆頂?shù)脑睾托绿砑拥脑剡M行比較。如果新添的元素比堆頂?shù)脑匦?，則應(yīng)該把堆頂?shù)脑貏h除，將新填的元素放入堆，這樣就能保證堆中的元素一直是最小的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; 
} 

「快速排序」

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

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

「計數(shù)排序」

因為題目中有這樣一個條件0 <= arr[i] <= 10000，說明數(shù)組中的元素比較集中，我們就可以用計數(shù)排序來解決這個問題，因為arr[i]的最大值10000為，所以我每次直接開一個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ù)組拆分為只有一個元素，然后對拆分的數(shù)組進行合并，主要合并的時候要保證合并后的數(shù)組有序，當(dāng)合并完成時，整個數(shù)組有序

public static void mergeSort(int[] a, int left, int right) { 
    // 將數(shù)組分段成只有一個元素 
    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++]; 
    } 
} 

計數(shù)排序

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

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ù)組中的元素為10000，10001，10002時，我們就得開辟一個10003大小的數(shù)組，不現(xiàn)實。所以我們可以改一下映射關(guān)系 num[i]的含義為原數(shù)組中值為i+min的個數(shù)為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]--; 
        } 
    } 
} 

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

基數(shù)排序

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

桶排序

「前面我們提到的計數(shù)排序和基數(shù)排序可以說是桶排序思想的一種特殊體現(xiàn)，就是不需要進行數(shù)組元素之間的比較」?；緵]被問到，不做解釋了

各種排序算法的應(yīng)用

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

本文轉(zhuǎn)載自微信公眾號「Java識堂」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系Java識堂公眾號。