最近不忙，瞭解下前端數據結構和算法，因看到不同的實現方法，故單獨寫一篇記錄快速排序，便於日後回顧。
參考書籍：《學習JavaScript數據結構與算法》第2版； 《數據結構與算法JavaScript描述》第1版
方法一：
《學習JavaScript數據結構與算法》
(1) 首先，從數組中選擇中間一項作為主元。 （取數組中間項）
(2) 創建兩個指針，左邊一個指向數組第一個項，右邊一個指向數組後一個項。移動左指 針直到我們找到一個比主元大的元素，接着，移動右指針直到找到一個比主元小的元素，然後交 換它們，重複這個過程，直到左指針超過了右指針。這個過程將使得比主元小的值都排在主元之 前，而比主元大的值都排在主元之後。這一步叫作劃分操作。
(3) 接着，算法對劃分後的小數組（較主元小的值組成的子數組，以及較主元大的值組成的 子數組）重複之前的兩個步驟，直至數組已完全排
代碼實現：
function quickSort(arr) {
// arr 數組，left 左指針，right 右指針
function sort(arr, left, right) {
if (arr.length == 0) {
return []
}
// 獲取主元，並劃分
var index = partition(arr, left, right);
// 左側重新劃分，遞歸調用
if (left < index - 1) {
sort(arr, left, index - 1)
}
// 右側重新劃分，遞歸調用
if (right > index) {
sort(arr, index, right)
}
}
//劃分過程，取一個數據中間值，使左邊的值都小於它，右邊的值都大於它
function partition(arr, left, right) {
// 取中間值
var pivot = arr[Math.floor((left + right) / 2)];
while (left <= right) {
// 循環找到左邊大於pivot的值的索引
while (arr[left] < pivot) {
left++
}
// 循環找到右邊小於pivot的值的索引
while (arr[right] > pivot) {
right--
}
// 交換位置，左指針右移，右指針左移
if (left <= right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}
//
return left;
}
// 調用
sort(arr, 0, arr.length - 1);
return arr;
}方法二：
《數據結構與算法JavaScript描述》
(1) 選擇一個基準元素，將列表分隔成兩個子序列；（取數組第一項）
(2) 對列表重新排序，將所有小於基準值的元素放在基準值的前面，所有大於基準值的元 素放在基準值的後面；
(3) 分別對較小元素的子序列和較大元素的子序列重複步驟 1 和 2
代碼實現：
function quickSort2(list) {
if (list.length == 0) {
return [];
}
var lesser = []; // 小於基準的數組
var greater = []; // 大於基準的數組
var pivot = list[0]; // 取第一個值為基準
for (var i = 1; i < list.length; i++) {
if (list[i] < pivot) {
lesser.push(list[i]);
} else {
greater.push(list[i]);
}
}
return quickSort2(lesser).concat(pivot, quickSort2(greater));
}測試代碼：
// 先生成一個隨機數組
function getRandomArr(n) {
var arr = [];
for (var i = 0; i < n; i++) {
arr.push(Math.floor(Math.random() * (n + 1)))
}
return arr;
}
var randomArr = getRandomArr(100000);
// 調用方法一
let randomArr1 = JSON.parse(JSON.stringify(randomArr));
console.log(`排序前`);
console.log(randomArr1);
console.log(`排序後`);
let startTime = new Date();
console.log(quickSort(randomArr1));
console.log(`耗時: ${new Date() - startTime}ms`)
// 調用方法二
let randomArr2 = JSON.parse(JSON.stringify(randomArr));
console.log(`排序前`);
console.log(randomArr2);
console.log(`排序後`);
let startTime2 = new Date();
console.log(quickSort2(randomArr2));
console.log(`耗時: ${new Date() - startTime2}ms`)結果發現，當數組長度為1,000時，兩種方法耗時均為10ms左右，沒有明顯差異；當數組長度為10,000+時，方法一比方法二耗時更短；當數組長度100,000時，兩種方法的耗時差更明顯。因此選擇數組中間項作比直接選擇數組第一項為pivot，效率更高。
本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。