前端筆試題——手撕快速排序（保姆級手撕）

• 2020 年 8 月 14 日
• 筆記
• javascript, Web前端, 前端面試, 算法

引言：

許多互聯網公司在招聘前端開發人才時，不僅考察面試者對於前端知識的掌握程度，數據結構與算法也漸漸成為了默許的要求。

除了考察鏈表、二叉樹、圖等數據結構以外，在算法中最具有代表性的就是「手撕」快速排序算法。

快速排序算法，對於大多數人而言確實具有一定的難度。排序思路，代碼設計以及難以理解的遞歸思想。

本文一步步帶你寫基於原生JavaScript語言的快速排序算法。

思想：

快速排序最核心的是分治思想，顧名思義，分而治之。

簡單來說就是，按照一個標準（也稱基準），將一個集合劃分為多個集合，分開求解。

再通俗一點就是，將強大的敵軍分成一塊一塊的，再逐個擊破。

舉個例子：

這個數組是亂序的。現在我們模擬快速排序的過程。

首先第一趟是這樣的：

1.我們規定基準是當前數組第一個元素，也就是array[0]。

2.將當前數組遍歷，比基準小的放left里，大的放right里。

3.一趟完成時，array會被劃分為left、mid和right三部分。

如圖所示：沒有比mid小的元素，所以left數組裡是空的；除mid外，其他比mid值大的元素全在right里。

第二趟也是同樣的道理：

1.對於left數組為空，則忽略。

2.對於right數組，裡邊的元素數量不止一個，那麼就可以進行第二趟快排了：

接着再對left和right分別進行劃分，快排，宏觀看來就是這樣：

這種結構是不是非常熟悉，有點像二叉樹呢？

設計與實現：

我們搞懂了過程，現在我們需要設計算法了。

在筆試中需要手撕快排，最好的辦法就是盡量精簡代碼，寫着也容易，看着也舒服！

根據前邊我們看到的結構，是不是能夠聯想到二叉樹的遍歷呢？

二叉樹遍歷最精簡的代碼就是使用遞歸。（不管先序、中序還是後序）

說白了，遞歸就是在函數中調用自己，返回自己。

但最重要的還是要有個終止條件，也就是當數組中的元素數量不大於一個時，就沒必要排序了。

無論怎樣，先定義個quickSort方法：

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
}

然後我們還需要定義數組left和right，還要將mid初始化為arr[0]。

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let left = [];
    let right = [];
    let mid = arr[0];
}

這時我們就要遍曆數組了，從mid後邊的元素開始。

若第i個元素比mid小，就放到left中。

若第i個元素比mid大或者一樣大，就放到right中。

所以，上代碼：

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let left = [];
    let right = [];
    let mid = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < mid) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
}

這樣，第一趟排序的結果就可以知道了，我們用js的concat方法將left、mid和right拼接一下。

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let left = [];
    let right = [];
    let mid = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < mid) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return left.concat(mid, right);
}

我們運行一下，看結果：

我們用流程推理一下，果然是第一趟排序的結果。

接下來，我們需要進行第二趟、第三趟……最後一趟排序。

這時我們就要用到遞歸思想了，我們需要對left和right再進行quickSort方法的調用。

那麼顯而易見，這麼寫就順理成章了：

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let left = [];
    let right = [];
    let mid = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < mid) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat(mid, quickSort(right));
}

好了，這個方法寫完了，一切都是那麼合理，我們調用一下看看結果：

console.log(quickSort([1, 5, 2, 3, 6, 8, 8, 7, 4]));

和想像中的一樣，一切都在計劃中：

至此，快速排序就寫完了，至少在筆試中這麼寫足夠用了！

分析：

對於快速排序，平均情況的時間複雜度為：O(n*lgn)。

當一個序列基本有序，就個別一個元素位置不對，那麼也就是快速排序算法的最差情況，時間複雜度為：O(n*n)。

所以，與其他排序算法相比，快速排序的性價比還是最高的，因此使用也最廣泛。

原創地址：//www.cnblogs.com/ElemSN/p/13503459.html。