引言：

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

除了考察鏈表、二叉樹、圖等資料結構以外，在演算法中最具有代表性的就是“手撕”快速排序演算法，

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

本文一步步帶你寫基于原生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)，

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

原創地址：https://www.cnblogs.com/ElemSN/p/13503459.html，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/5452.html

標籤：JavaScript

上一篇：TypeScript是什么，為什么要使用它？

下一篇：WEB第二十三課——js運算子

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

引言：

思想：

設計與實作：

分析：