面試官超級喜歡問的排序算法

長沙7喜 2021-11-23

展開全文

“腳本之家

”，與百萬開發(fā)者在一起

來源 | 程序員巴士（ID：tech-bus）
如若轉(zhuǎn)載請聯(lián)系原公眾號

前言

阿巴阿巴刷了半年的算法，決定出去試試水，巧了，這次面試官讓她談?wù)剬ε判蛩惴ǖ睦斫狻?/p>

面試官： 你對算法這一塊了解嗎？排序這一塊了解嗎？

阿巴阿巴： 了解一點，排序算法這一塊主要有冒泡排序、插入排序、希爾排序、選擇排序、快速排序、歸并排序、堆排序、基數(shù)排序、桶排序。

面試官： 很不錯，那你知道什么是穩(wěn)定性嗎，上述這些算法都是穩(wěn)定的嗎？他們的復(fù)雜度分別是多少呀？

阿巴阿巴： 穩(wěn)定性就是說，如果有2個元素a和b，且 a = b，且a排在b前面，如果經(jīng)過排序算進(jìn)行排序后，b在a前面了，那么我們就說這個算法是不穩(wěn)定的，這就是穩(wěn)定性。不穩(wěn)定的算法有快速排序、選擇排序、希爾排序、堆排序。俗稱'快選希堆’。

阿巴阿巴： 如下圖（狗頭），可以看到平均性能為O(nlogn)的有：快速排序，歸并排序，堆排序，這些排序算法時間復(fù)雜度低，適合大數(shù)據(jù)集排序，當(dāng)然時間復(fù)雜度高的排序算法也有自己的用武之地的。

面試官： 講一下你知道的算法的使用場景唄！

阿巴阿巴：好的。

冒泡排序適合： 適用于數(shù)據(jù)量不大，且要求排序穩(wěn)定，數(shù)據(jù)量本身基本有序的情況。
選擇排序適合： 當(dāng)數(shù)據(jù)量不大且對于穩(wěn)定性沒有要求的情況（相對冒泡排序來說減少了交換次數(shù)）。
插入排序適合： 適合于數(shù)據(jù)量不大，對算法穩(wěn)定性有要求，局部有序或整體相對有序的情況。
歸并排序適合： 數(shù)據(jù)比較大，且對算法穩(wěn)定性有要求的情況。
快速排序適合： 數(shù)據(jù)量大，且數(shù)據(jù)較為分散，且對穩(wěn)定性沒啥要求的情況。
堆排序適合： 數(shù)據(jù)量大，對穩(wěn)定性沒要求的情況。
希爾排序： 希爾排序是對直接插入排序的一種優(yōu)化，可以用于大型的數(shù)組，希爾排序比插入排序和選擇排序要快的多，并且數(shù)組越大，優(yōu)勢越大。
基數(shù)排序適合： 適合數(shù)據(jù)集中，沒有特別大的數(shù)據(jù)，對算法要求穩(wěn)定的場景。
桶排序適合： 適合數(shù)據(jù)比較集中的，對算法要求穩(wěn)定的場景。

面試官： 好的，看你是有備而來，那我問個冷門點的，可以給我詳細(xì)介紹下基數(shù)排序和桶排序嗎？

阿巴阿巴： 基數(shù)排序?qū)儆凇胺峙涫脚判颉?，又稱“桶子法”或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用。比如說有一批數(shù)據(jù)[31,19,46,23,17],那么先按照“個”位上的數(shù)值進(jìn)行排序，放進(jìn)下面的桶中。

阿巴阿巴： 放進(jìn)桶中后得到下圖所示。

阿巴阿巴： 然后繼續(xù)對桶中元素進(jìn)行排序，從第0個桶開始往第9個桶依次拿出，繼續(xù)排序，得到藍(lán)色部分?jǐn)?shù)據(jù)。

阿巴阿巴： 然后繼續(xù)對桶中元素進(jìn)行排序，從第0個桶開始往第9個桶依次拿出，繼續(xù)排序，得到藍(lán)色部分?jǐn)?shù)據(jù)，對藍(lán)色部分?jǐn)?shù)據(jù)繼續(xù)排序，按照“十位”上的數(shù)字進(jìn)行排序。

阿巴阿巴： 最后將這些數(shù)據(jù)進(jìn)行依次從第0個桶開始往第9個桶依次拿出，這樣就都有序了。

面試官： 不錯不錯，基數(shù)排序如果數(shù)字很大的話，看起來對排序很不利呢？

阿巴阿巴： 是的如果有個數(shù)字很大，那么基數(shù)排序會顯得相當(dāng)吃力，最好是數(shù)據(jù)集中數(shù)據(jù)都差不多大。

 /**
 * 基數(shù)排序
 */
public class RadixSort {

    /**
     * 獲取最高位數(shù)
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考慮負(fù)數(shù)的情況，這里擴(kuò)展一倍隊列數(shù)，其中 [0-9]對應(yīng)負(fù)數(shù)，[10-19]對應(yīng)正數(shù) (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }
    /**
     * 自動擴(kuò)容，并保存數(shù)據(jù)
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

面試官： 好的，那么桶排序呢，可以講講嗎？

阿巴阿巴： 完全可以，桶排序(Bucket sort)或所謂的箱排序，是一個排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。選擇數(shù)據(jù)范圍特別集中的數(shù)據(jù)集排序時使用，比如有一組數(shù)據(jù)如：[1,2,1,3,5,3,2,1,2,3,4,5,2,1]，由于這部分?jǐn)?shù)據(jù)集中在1-5之間，所以需要創(chuàng)建出5個桶，然后把元素放進(jìn)匹配的桶里即可：1號元素放入1號桶，2號元素放入2號桶....

阿巴阿巴： 將元素放入到匹配的桶中。

阿巴阿巴： 再依次從桶中拿出這些元素即排好序了。

面試官： 不錯，把桶排序講的清晰明了，那這樣看來桶排序適合數(shù)據(jù)集中跨度不大的數(shù)據(jù)集的排序情況。

阿巴阿巴： 是的，桶排序適合于下面這些情況。

針對高考學(xué)生單科成績進(jìn)行排序，成績一般是0-100，這時候建立100個桶，然后對這些成績進(jìn)行排序即可。
醫(yī)院需要針對患者年齡進(jìn)行排序，年齡一般0-150，這時候建立150個桶，然后針對患者年齡進(jìn)行排序即可。

//桶排序
 public class BucketSort {
 
    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
        if (arr.length == 0) {
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        // 利用映射函數(shù)將數(shù)據(jù)分配到各個桶中
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // 對每個桶進(jìn)行排序，這里使用了插入排序
            bucket = insertSort.sort(bucket);
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }
        
        return arr;
    }

    /**
     * 自動擴(kuò)容，并保存數(shù)據(jù)
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

}

阿巴阿巴：以上就是我對桶排序的理解啦。

面試官： 沒想到你這么熟悉，那就再講下快排唄??

阿巴阿巴： 快速排序算法通過多次比較和交換來實現(xiàn)排序，其排序流程如下 (1)首先設(shè)定一個基準(zhǔn)值，通過該基準(zhǔn)值將數(shù)組分成左右兩部分。(2)將大于或等于基準(zhǔn)值的數(shù)據(jù)集中到數(shù)組右邊，小于基準(zhǔn)值的數(shù)據(jù)集中到數(shù)組的左邊。此時，左邊部分中各元素都小于或等于基準(zhǔn)值，而右邊部分中各元素都大于或等于基準(zhǔn)值。(3)然后，左邊和右邊的數(shù)據(jù)可以獨立排序。對于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個基準(zhǔn)值，將該部分?jǐn)?shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理。(4)重復(fù)上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當(dāng)左、右兩個部分各數(shù)據(jù)排序完成后，整個數(shù)組的排序也就完成了。

如有一組數(shù)據(jù)需要排序：[31,33,46,12,17]

阿巴阿巴： 先選取基準(zhǔn)值，這里選的是31

阿巴阿巴： 然后從基準(zhǔn)值后第一個元素開始向右遍歷找到一個大于基準(zhǔn)值的數(shù)同時從最后一個元素開始向左遍歷找到一個小于基準(zhǔn)值的數(shù)。

阿巴阿巴： 將這倆個元素進(jìn)行交換。

阿巴阿巴： 繼續(xù)向右遍歷找到一個大于基準(zhǔn)值的數(shù)同時從最后一個元素開始向左遍歷找到一個小于基準(zhǔn)值的數(shù)。

阿巴阿巴： 繼續(xù)按照規(guī)則進(jìn)行交換

阿巴阿巴： 得到如下圖所示

阿巴阿巴： 最后將標(biāo)準(zhǔn)值放到右側(cè)”指針“最后運行的位置使得基準(zhǔn)值左邊的數(shù)都小于等于基準(zhǔn)值，基準(zhǔn)值右邊的數(shù)都大于等于基準(zhǔn)值

阿巴阿巴： 這樣一輪就結(jié)束了，快排中會進(jìn)行遞歸，所以每個元素最終都能找到屬于自己的位置

阿巴阿巴： 下面代碼就是安裝這個邏輯來實現(xiàn)的。

public class QuickSort{

  public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;;
        // 返回基準(zhǔn)值的小標(biāo)，然后遞歸基準(zhǔn)值左側(cè)和基準(zhǔn)值右側(cè)數(shù)組
        int j = handler(arr, left, right);
        //遞歸基準(zhǔn)值左側(cè)數(shù)組
        quickSort(arr,0, j - 1);
        //遞歸基準(zhǔn)值右側(cè)數(shù)組
        quickSort(arr,j + 1, right);
    }


    public static int handler(int[] arr, int start, int end) {
        // 定義左邊和右邊用來尋找左側(cè)大于基準(zhǔn)值的數(shù)和右側(cè)小于基準(zhǔn)值的數(shù)
        int left = start;
        int right = end;
        int bound = arr[start];

        while (left < right) {
            //一直找直到找到或越界了
            while(left < right && arr[left] <= bound) left++;
            while(left <= right=''>= bound) right--;
            // 將左側(cè)找到的值和右側(cè)進(jìn)行交互
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        // 這一步很關(guān)鍵，用來定位基準(zhǔn)值的位置
        int temp = arr[start];
        arr[start] = arr[right];
        arr[right] = temp;
        return  right;
    }

}

阿巴阿巴： 再走一遍整個流程。

面試官： 好的明天來上班??

算法是面試中必不可少的一部分，而排序算法被問到的頻率相對來說也很高，因此對于基本的排序算法都需要掌握好。除此之外，leetcode中有一些題也是帶有排序算法的思維，下面是leetcode上有一些關(guān)于排序的算法題。

參考https://www.runoob.com/

本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點擊一鍵舉報。

小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

面試官超級喜歡問的排序算法

前言