面試題1：你說一下常用的排序算法都有哪些？

追問1：談一談你對快排的理解吧

快速排序，顧名思義就是一種以效率快為特色的排序算法，快速排序（Quicksort）是對冒泡排序的一種改進(jìn)。由英國計(jì)算機(jī)專家:托尼·霍爾（Tony Hoare）在1960年提出。

從排序數(shù)組中找出一個(gè)數(shù)，可以隨機(jī)取，也可以取固定位置，一般是取第一個(gè)或最后一個(gè)，稱為基準(zhǔn)數(shù)。然后將比基準(zhǔn)小的排在左邊，比基準(zhǔn)大的放到右邊；

如何放置呢，就是和基準(zhǔn)數(shù)進(jìn)行交換，交換完左邊都是比基準(zhǔn)小的，右邊都是比較基準(zhǔn)大的，這樣就將一個(gè)數(shù)組分成了兩個(gè)子數(shù)組，然后再按照同樣的方法把子數(shù)組再分成更小的子數(shù)組，直到不能分解（子數(shù)組只有一個(gè)值）為止。以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

快速排序采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)，現(xiàn)在各種語言中自帶的排序庫很多使用的都是快速排序。

空間復(fù)雜度

快速排序是一種原地排序，只需要一個(gè)很小的棧作為輔助空間，空間復(fù)雜度為O(log2n)，所以適合在數(shù)據(jù)集比較大的時(shí)候使用。

時(shí)間復(fù)雜度

時(shí)間復(fù)雜度比較復(fù)雜，最好的情況是O(n)，最差的情況是O(n2)，所以平時(shí)說的O(nlogn)，為其平均時(shí)間復(fù)雜度。

• O(n)：理想的情況，每次劃分所選擇的中間數(shù)恰好將當(dāng)前序列幾乎等分，經(jīng)過log2n趟劃分，便可得到長度為1的子表。這樣，整個(gè)算法的時(shí)間復(fù)雜度為O(nlog2n)。
• O(n2)：最壞的情況，每次所選的中間數(shù)是當(dāng)前序列中的最大或最小元素，這使得每次劃分所得的子表中一個(gè)為空表，另一子表的長度為原表的長度-1。這樣，長度為n的數(shù)據(jù)表的快速排序需要經(jīng)過n趟劃分，使得整個(gè)排序算法的時(shí)間復(fù)雜度為O(n2)。

追問2：說一下快排的算法原理

算法步驟

• 選定一個(gè)基準(zhǔn)數(shù)（一般取第一位數(shù)字）作為中心點(diǎn)（Pivot）；
• 將大于Pivot的數(shù)字放到Pivot的左邊；
• 將小于Pivot的數(shù)字放到Pivot的右邊；
• 第一次排序結(jié)束后，分別對左右子序列繼續(xù)遞歸重復(fù)前三步操作，直到左右子序列長度只有單個(gè)元素為止。

demo示例

實(shí)例數(shù)組：arr[] = {19，97，9，17，1，8}；

取出基準(zhǔn)數(shù)Pivot，以該值為中心軸。

快速排序中的規(guī)則：右邊有坑，就從左邊Arr[L + n]取值來填，反之左邊有坑，則從右邊Arr[R - n]取值來填；

從左邊取的基準(zhǔn)值，左邊的Arr[L]就空出來了，則先從右側(cè)取值來填，從最右側(cè)下標(biāo)開始，在Arr[R] 取到第一個(gè)值“8”；

將取到的Arr[R]與基準(zhǔn)值比較，發(fā)現(xiàn)小于基準(zhǔn)值，則插入到Arr[R]，占到了基準(zhǔn)值Pivot的位置上。

然后從Arr[L+1]的位置取出值，繼續(xù)向右匹配并排序，將匹配到的值（匹配規(guī)則如下）插入到右側(cè)Arr[R]的空位置上；

匹配規(guī)則：大于基準(zhǔn)值的插入到Arr[R]，如果小于，則直接忽略并跳過，繼續(xù)向右取值，直到坐標(biāo)L和坐標(biāo)R重合。

發(fā)現(xiàn)取出的值大于Pivot（基準(zhǔn)值），則將其插入到Arr[R]。

左邊有坑，從右邊Arr[R-1]繼續(xù)匹配，Arr[R-1] = 1，小于基準(zhǔn)值，則插入到Arr[L]的坑中；

右邊有坑了，繼續(xù)從左邊取值繼續(xù)匹配，則取到Arr[L+1] = 9,小于基準(zhǔn)值，則忽略并跳過，繼續(xù)找Arr[L + 1]繼續(xù)匹配。

繼續(xù)從左邊坐標(biāo) + 1 取值繼續(xù)匹配，則取到Arr[L] = 17，又小于基準(zhǔn)值，則忽略并跳過，繼續(xù)找Arr[L + 1]繼續(xù)匹配。

最后L坐標(biāo)和R坐標(biāo)重合了，將Pivot基準(zhǔn)值填入

至此，快速排序第一輪完整流程結(jié)束，分出了左右子序列，左邊都是小于Pivot基準(zhǔn)值的，右邊都是大于Pivot基準(zhǔn)值的。

繼續(xù)對左、右子序列遞歸進(jìn)行處理，一直縮小到左、右都是一個(gè)值，則快速排序結(jié)束，最終得出順序數(shù)組{1,8,9,17,19,97}；中間遞歸流程這里不再贅述。

追問3：來吧！給我手敲一個(gè)快排

package com.softsec.demo;
/**
 * Created with IDEA
 *
 * @Author Chensj
 * @Date 2020/5/17 19:04
 * @Description
 * @Version 1.0
 */
public class quickSortDemo {
    public static void main(String[] args) {
        // 創(chuàng)建測試數(shù)組
        int[] arr = new int[]{19,97,9,17,1,8};
        System.out.println("排序前：");
        showArray(arr); // 打印數(shù)組
        // 調(diào)用快排接口
        quickSort(arr);
        System.out.println("\n" + "排序后：");
        showArray(arr);// 打印數(shù)組
    }
    /**
     * 快速排序
     * @param array
     */
    public static void quickSort(int[] array) {
        int len;
        if(array == null
                || (len = array.length) == 0
                || len == 1) {
            return ;
        }
        sort(array, 0, len - 1);
    }
    /**
     * 快排核心算法，遞歸實(shí)現(xiàn)
     * @param array
     * @param left
     * @param right
     */
    public static void sort(int[] array, int left, int right) {
        if(left > right) {
            return;
        }
        // base中存放基準(zhǔn)數(shù)
        int base = array[left];
        int i = left, j = right;
        while(i != j) {
            // 順序很重要，先從右邊開始往左找，直到找到比base值小的數(shù)
            while(array[j] >= base && i < j) {
                j--;
            }
            // 再從左往右邊找，直到找到比base值大的數(shù)
            while(array[i] <= base && i < j) {
                i++;
            }
            // 上面的循環(huán)結(jié)束表示找到了位置或者(i>=j)了，交換兩個(gè)數(shù)在數(shù)組中的位置
            if(i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
        // 將基準(zhǔn)數(shù)放到中間的位置（基準(zhǔn)數(shù)歸位）
        array[left] = array[i];
        array[i] = base;
        // 遞歸，繼續(xù)向基準(zhǔn)的左右兩邊執(zhí)行和上面同樣的操作
        // i的索引處為上面已確定好的基準(zhǔn)值的位置，無需再處理
        sort(array, left, i - 1);
        sort(array, i + 1, right);
    }
    /**
     * 數(shù)組打印
     * @param num
     */
    private static void showArray(int[] num) {
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + " ");
        }
    }
}

面試題2：來！再給我手?jǐn)]一個(gè)Spring

我：？？？

追問1：哦，咳咳…說一下構(gòu)成遞歸的前提條件有啥？

函數(shù)內(nèi)部調(diào)用的自身函數(shù)的編程技巧稱為遞歸（recursion）。

構(gòu)成遞歸的條件：

• 子問題須與原始問題為同樣的事，且更為簡單；
• 不能無限制地調(diào)用本身，須有個(gè)出口，化簡為非遞歸狀況處理。

追問2：遞歸都有哪些優(yōu)缺點(diǎn)？

優(yōu)點(diǎn)：

1.簡潔

2.在樹的前序，中序，后序遍歷算法中，遞歸的實(shí)現(xiàn)明顯要比循環(huán)簡單得多。

缺點(diǎn)：

1.遞歸由于是函數(shù)調(diào)用自身，而函數(shù)調(diào)用是有時(shí)間和空間的消耗的：每一次函數(shù)調(diào)用，都需要在內(nèi)存棧中分配空間以保存參數(shù)、返回地址以及臨時(shí)變量，而往棧中壓入數(shù)據(jù)和彈出數(shù)據(jù)都需要時(shí)間。（效率）

2.遞歸中很多計(jì)算都是重復(fù)的，由于其本質(zhì)是把一個(gè)問題分解成兩個(gè)或者多個(gè)小問題，多個(gè)小問題存在相互重疊的部分，則存在重復(fù)計(jì)算，如fibonacci斐波那契數(shù)列的遞歸實(shí)現(xiàn)。（效率）

3.調(diào)用棧可能會(huì)溢出，其實(shí)每一次函數(shù)調(diào)用會(huì)在內(nèi)存棧中分配空間，而每個(gè)進(jìn)程的棧的容量是有限的，當(dāng)調(diào)用的層次太多時(shí)，就會(huì)超出棧的容量，從而導(dǎo)致棧溢出。（性能）

追問3：給我手寫一個(gè)簡單的遞歸算法的實(shí)現(xiàn)吧

例如遞歸計(jì)算一下n的階乘

package com.softsec;
/**
 * 遞歸計(jì)算n的階乘
 * @author Chenhh
 */
public class demo {
    public static void main(String[] args) {
        System.out.println(recursion(5));
    }
    /**
     * 遞歸計(jì)算n的階乘
     */
    private static int recursion(int n) {
        if (n <1) {
            throw new IllegalArgumentException("參數(shù)必須大于0");
        } else if (n == 1) {
            return 1;
        } else {
            return n * recursion(n - 1);
        }
    }
}

面試題3： 10億個(gè)數(shù)中找出最大的100000個(gè)數(shù)（top K問題）

先拿100000個(gè)數(shù)建堆，然后一次添加剩余元素，如果大于堆頂?shù)臄?shù)（100000中最小的），將這個(gè)數(shù)替換堆頂，并調(diào)整結(jié)構(gòu)使之仍然是一個(gè)最小堆，這樣，遍歷完后，堆中的100000個(gè)數(shù)就是所需的最大的100000個(gè)。建堆時(shí)間復(fù)雜度是O(m)，算法的時(shí)間復(fù)雜度為1次建堆時(shí)間+n次堆調(diào)整時(shí)間=O(m+nlogm)=O(nlogm)（n為10億，m為100000）。

優(yōu)化的方法：可以把所有10億個(gè)數(shù)據(jù)分組存放，比如分別放在1000個(gè)文件中。這樣處理就可以分別在每個(gè)文件的10^6個(gè)數(shù)據(jù)中找出最大的100000個(gè)數(shù)，合并到一起在再找出最終的結(jié)果。

top K問題

在大規(guī)模數(shù)據(jù)處理中，經(jīng)常會(huì)遇到的一類問題：在海量數(shù)據(jù)中找出出現(xiàn)頻率最好的前k個(gè)數(shù)，或者從海量數(shù)據(jù)中找出最大的前k個(gè)數(shù)，這類問題通常被稱為top K問題。例如，在搜索引擎中，統(tǒng)計(jì)搜索最熱門的10個(gè)查詢詞；在歌曲庫中統(tǒng)計(jì)下載最高的前10首歌等。

針對top K類問題，通常比較好的方案是分治+Trie樹/hash+小頂堆（就是上面提到的最小堆），即先將數(shù)據(jù)集按照Hash方法分解成多個(gè)小數(shù)據(jù)集，然后使用Trie樹活著Hash統(tǒng)計(jì)每個(gè)小數(shù)據(jù)集中的query詞頻，之后用小頂堆求出每個(gè)數(shù)據(jù)集中出現(xiàn)頻率最高的前K個(gè)數(shù)，最后在所有top K中求出最終的top K。

對于有10億個(gè)整數(shù)，如何找出其中最大的10萬個(gè)這個(gè)問題

最容易想到的方法是將數(shù)據(jù)全部排序，然后在排序后的集合中進(jìn)行查找，最快的排序算法的時(shí)間復(fù)雜度一般為O（nlogn），如快速排序。但是如果按每個(gè)int類型占4個(gè)字節(jié)，10億個(gè)整數(shù)就要占用4G的存儲(chǔ)空間，對于一些java運(yùn)行內(nèi)存小于4G的計(jì)算機(jī)而言，直接OOM（out of memory）了。其實(shí)即使內(nèi)存能夠滿足要求（我機(jī)器內(nèi)存都是8GB），該方法也并不高效，因?yàn)轭}目的目的是尋找出最大的100000個(gè)數(shù)即可，而排序卻是將所有的元素都排序了，做了很多的無用功。

第二種方法為局部淘汰法，該方法與排序方法類似，用一個(gè)容器保存前100000個(gè)數(shù)，然后將剩余的所有數(shù)字——與容器內(nèi)的最小數(shù)字相比，如果所有后續(xù)的元素都比容器內(nèi)的100000個(gè)數(shù)還小，那么容器內(nèi)這個(gè)100000個(gè)數(shù)就是最大100000個(gè)數(shù)。如果某一后續(xù)元素比容器內(nèi)最小數(shù)字大，則刪掉容器內(nèi)最小元素，并將該元素插入容器，最后遍歷完這1億個(gè)數(shù)，得到的結(jié)果容器中保存的數(shù)即為最終結(jié)果了。此時(shí)的時(shí)間復(fù)雜度為O（n+m^2），其中m為容器的大小，即100000。

第三種方法是分治法，將10億個(gè)數(shù)據(jù)分成1000份，每份100萬個(gè)數(shù)據(jù)，找到每份數(shù)據(jù)中最大的100000個(gè)，最后在剩下的1000 * 100000個(gè)數(shù)據(jù)里面找出最大的100000個(gè)。如果100萬數(shù)據(jù)選擇足夠理想，那么可以過濾掉1億數(shù)據(jù)里面99%的數(shù)據(jù)。100萬個(gè)數(shù)據(jù)里面查找最大的100000個(gè)數(shù)據(jù)的方法如下：用快速排序的方法，將數(shù)據(jù)分為2堆，如果大的那堆個(gè)數(shù)N大于100000個(gè)，繼續(xù)對大堆快速排序一次分成2堆，如果大的那堆個(gè)數(shù)N大于100000個(gè)，繼續(xù)對大堆快速排序一次分成2堆，如果大堆個(gè)數(shù)N小于100000個(gè)，就在小的那堆里面快速排序一次，找第100000-n大的數(shù)字；遞歸以上過程，就可以找到第10w大的數(shù)。參考上面的找出第10w大的數(shù)字，就可以類似的方法找到前100000大數(shù)字了。此種方法需要每次的內(nèi)存空間為10^6*4=4MB，一共需要101次這樣的比較。

第四種方法是Hash法。如果這1億個(gè)書里面有很多重復(fù)的數(shù)，先通過Hash法，把這10億個(gè)數(shù)字去重復(fù)，這樣如果重復(fù)率很高的話，會(huì)減少很大的內(nèi)存用量，從而縮小運(yùn)算空間，然后通過分治法或最小堆法查找最大的100000個(gè)數(shù)。

第五種方法采用最小堆。首先讀入前100000個(gè)數(shù)來創(chuàng)建大小為100000的最小堆，建堆的時(shí)間復(fù)雜度為O(m)（m為數(shù)組的大小即為100000），然后遍歷后續(xù)的數(shù)字，并于堆頂（最?。?shù)字進(jìn)行比較。如果比最小的數(shù)小，則繼續(xù)讀取后續(xù)數(shù)字；如果比堆頂數(shù)字大，則替換堆頂元素并重新調(diào)整堆為最小堆。整個(gè)過程直至10億個(gè)數(shù)全部遍歷完為止。然后按照中序遍歷的方式輸出當(dāng)前堆中的所有100000個(gè)數(shù)字。該算法的時(shí)間復(fù)雜度為O（nmlogm），空間復(fù)雜度是100000（常數(shù)）。

總結(jié)

本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！

最新評論