JavaScript實作經典排序演算法—快排
快速排序演算法的性能比之前的冒泡、選擇排序都要好，和歸并排序一樣，是一個可以用于實戰的演算法，聽說chrome用的就是快排
又聽說前端面試會考，那你實作一個快排吧！
一、快速排序的演算法思路
還是在這里看一下快排是啥意思
快速排序演算法動圖
1、快速排序的特點就是隨機設定一個基準點，比如是陣列的第一個元素，然后陣列的其他元素就跟這個基準線進行對比，比基準線大的放在左邊，比基準線小的放在右邊
2、再設定一個基準線，再這樣小的放左邊，大的放右邊，遞回，
二、編碼實作
詳細分析寫在注釋里了
Array.prototype.quickSort = function() {
const rec = (arr) => {
// 遞回都是要有盡頭的，不然會無限進行下去
// 直到Maximum call stack size exceeded
// 別問我為什么知道
// 而且注意，這里要有小于1，不然也會報錯
if(arr.length <= 1) return arr;
let left = [];
let right = [];
const base = arr[0];
// 因為基準線是arr[0]，所以從下標是1也就是第二個開始
for(let i = 1; i < arr.length; i += 1) {
if(arr[i] < base) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
// 解構一下
// 遞回左邊陣列和右邊陣列
// 左邊加上右邊加上基準才是完整陣列哈
return [...rec(left), base, ...rec(right)];
}
const res = rec(this);
// 遍歷res，賦值到this也就是當前陣列本身
res.forEach((item, key) => {
this[key] = item;
})
}
const arr = [1, 5, 9, 3, 18, 6, 2, 7]
arr.quickSort()
console.log(arr);
三、演算法時間復雜度
1、這種劈成兩半遞回，時間復雜度一般是O(logn)
2、遞回里面，for回圈對比，時間復雜度是O(n)
所以時間復雜度是O(nlogn)
寫完了，唉嘿~看完點贊的都是小可愛大聰明
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/291321.html
標籤：其他