98.快速排序
Opened this issue · 0 comments
webVueBlog commented
// 原理
// 分治的**
// 先随机选出一个元素作为基准
// 比基准点小的放在左边
// 比基准点大的放在右边
// 时间复杂度:O(nlogn)
/**
* 最简单的快速排序
* @param {any[]} arr
*/
function quickSort(arr) {
if (arr.length < 2) {
return arr.slice();
}
// 随机找到基准点
const pivot = arr[Math.floor(Math.random() * arr.length)];
let left = [];
let middle = [];
let right = [];
for (let index = 0; index < arr.length; index++) {
const value = arr[index];
if (value < pivot) {
letf.push(value);
}
if (value === pivot) {
middle.push(value);
}
if (value > pivot) {
right.push(value);
}
}
// 递归进行
return quickSort(left).concat(middle, quickSort(right));
}
let arr = [23,45,3,232];
console.log( quickSort(arr) );