-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathquick.js
More file actions
32 lines (30 loc) · 1.51 KB
/
Copy pathquick.js
File metadata and controls
32 lines (30 loc) · 1.51 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 快排
// 快排必须要用到递归，采用分而治之的思路
// 选择一个基准值（通常选最中间的值，一定概率上可以降低复杂度）
// 声明两个数组 less、greater，比基准值大的放入 greater，小的放入 less
// 递归地再对 less、greater 进行相同的操作，并把结果 concat 起来得到最终结果
// 其实每次递归，都需要 n 次操作，但是总递归次数，取决于基准值的选择
// 比如对于已排序的数组，选择 arr[0] 做基准值
// 那每次递归，只有一个元素放到 less，剩余的元素都放到 greater
// 也就是最终的递归次数是 n，时间复杂度为 O(n^2)
// 如果选择 arr[Math.floor(arr.length / 2)] 作为基准值，
// 那 less、greater 每次都分别能放入一半的次数
// 也就总递归次数为 2 为底的对数，时间复杂度是 n*O(log n)
// 时间复杂度：平均n*O(log n) 最差O(n^2) 最好n*O(log n)
// 空间复杂度 O(log n)
function quickSort (arr) {
if (arr.length < 2) return arr
const midIndex = Math.floor(arr.length / 2)
const mid = arr[midIndex]
// 需要从数组中移除元素，因为下面的大小写判断是用的 else
// 不移除的话，该元素会重复进入数组
arr.splice(midIndex, 1)
const less = []
const greater = []
for (let i = 0; i < arr.length; i++) {
if (arr[i] < mid) less.push(arr[i])
else greater.push(arr[i])
}
return quickSort(less).concat([mid], quickSort(greater))
}
console.log(quickSort([2, 9, 0, 40, 50, 29, 12, 15, 10]))