快速排序
天下武功唯快不破,来,学习快速排序
# 快速排序
快速排序,顾名思义,是一种排序速度非常快的排序方法,该算法之所以非常快,是因为高度优化的内部循环,该算法在实际应用中非常广泛。
# 初版快排
# 思路一
快速排序和归并排序一样,采用了分治递归的思想,算法思路主要是:
取出当前数组的第一个元素,这里成为中间元素,因为我们要将当前数组分类,扫描后面的元素,大于或等于中间元素的元素放其右边,小于或等于中间元素的元素放其左边 。然后对左右两个子数组分别按照同样的方法进行分割操作(递归进行)一直递归分割到子数组只有一个或零个元素为止,此时整个数组有序。
这个过程成为 分割(partition)
分割(partition)过程
将当前数组的第一个元素v的位置用 l
来标记
用 j
作为记录分界点,也就是说 j左边的都是小于 v 的元素, j 右边的都是大于v的元素
当前扫描到的元素我们标记为 i
安装上述标记,arr[l+1...j] 都是小于v的 arr[j+1...i-1] 都是大于v的
扫描到 arr[i] > v的时候 i++即可
扫描到 arr[i] < v的时候 我们就把arr[i] 和 arr[j+1] 的位置交换 j++ 就可 如下图所示
最后,我们将arr[l]和 arr[j]的位置交换一下,即可
# 代码
function quickSort (arr) {
// 对 arr[l...r] 进行快速排序
__quickSort(arr,0,arr.length-1)
return arr
}
function __quickSort(arr,l,r) {
// 递归出口
if (l>=r) {
return
}
// 使用分割来获取中间元素的位置
let p = __partition(arr,l,r)
__quickSort(arr,l,p-1)
__quickSort(arr,p+1,r)
}
// 对arr[l...r] 进行partition操作
// 返回p arr[l...p-1] < arr[p] arr[p+1,r] > arr[p]
function __partition(arr,l,r) {
let v = arr[l]
// 这样定义j 就满足了 arr[l+1...j] 和 arr[j+1...i) 刚开始时都不存在
let j = l
for(let i=l+1; i<=r;i++) {
// 当 (arr[i] > v) 直接i++ for循环就能控制 不用再写额外代码
if(arr[i] < v) {
util.swap(arr,i,j+1)
j++
}
}
util.swap(arr,l,j)
return j
}
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
33
经过测试:
归并排序: 15.992ms
快速排序: 10.876ms
归并排序: 16.275ms
快速排序: 10.878ms
归并排序: 15.984ms
快速排序: 9.301ms
2
3
4
5
6
7
8
我们发现,我们第一版的快速排序的性能 就远超优化后的归并排序,快排果然不是浪得虚名。我们接下来探讨一下快排的优化。
# 优化
插排序优化
和之前讲的归并排序的改进方法一样,在递归到底的情况下使用插入排序处理小数据量,提高性能
保持快排期望值为O(nlogn)
第二种优化方法就是保持快速排序的期望值在O(nlogn),为什么这么说,我们看下面的例子
let arr = util.generateNearlyOrderedArray(30000, 10)
let arr1 = arr.slice()
util.testSort('归并排序', all.mergeSort, arr)
util.testSort('快速排序', quickSort, arr1)
// 归并排序: 14.907ms
// 快速排序: 80.590ms
2
3
4
5
6
当我们的数据是近乎有序的时候,快速排序明显比归并排序慢的多,快速排序操作近乎有序的数组,会退化成O(n^2),所以会比归并排序慢很多
测试的时候数据量大的话会 提示 Maximum call stack size exceeded 堆栈溢出错误。就是因为在有序的状态下快排递归树深度太深导致。归并排序可以保证出来的递归树是平衡的。
所以我们就可以在这个问题上加以改善来优化快排。
保持快排期望值为O(nlogn),而不是退化为O(n^2)
造成退化的原因是我们之前的代码是使用的每组数组的第一个元素作为比较,如果我们数组范围内随机的一个数作为分割数,那么我们就能是我们的快排在任何情况下都保持时间复杂度期望值为O(nlogn)
function __partition(arr,l,r) {
// 随机一个数和最左边的数交换位置
let random = Math.floor(Math.random() * (r - l + 1)) + l
util.swap(arr, l, random)
let v = arr[l]
// 这样定义j 就满足了 arr[l+1...j] 和 arr[j+1...i) 刚开始时都不存在
let j = l
for(let i=l+1; i<=r;i++) {
// 当 (arr[i] > v) 直接i++ for循环就能控制 不用再写额外代码
if(arr[i] < v) {
util.swap(arr,i,j+1)
j++
}
}
util.swap(arr,l,j)
return j
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
代码较前一次的代码就多了 3,4两行代码,生成一个r-l的随机数与l位置的数交换,这样就能保证我们的快排期望值为O(nlogn)
# 改变partition的思路
大量小范围下
我们又遇到一种情况,那就是当我们的数组是大量小范围情况下,我们的我们虽然拿的随机数是大概率为中间位置的数,但是由于数组中存在很多与对比元素相同的元素,那么仍然会把我们的数组分割成两个不平衡的子数组,这样的情况下我们的快速排序又退化到O(n^2)
let arr = util.randomArray(50000,0,10)
let arr1 = arr.slice()
util.testSort('归并排序', all.mergeSort,arr)
util.testSort('快速排序', quickSort, arr1)
// 归并排序: 15.351ms
// 快速排序: 146.162ms
// 数据量大的话快排仍会报堆栈溢出的错误
2
3
4
5
6
7
我们该如何解决这一问题?
我们换一个思路来解决快排:之前是我们把小于对比元素和大于对比元素都放在了一头,现在我们将其分别放在两头
当最后排序完成的时候
i停在了从左往右看 第一个 大于等于v 元素的位置
j停在了从左往右看 最后一个 小于等于v 元素的位置
function __partition(arr, l, r) {
let random = Math.floor(Math.random() * (r - l + 1)) + l
util.swap(arr, l, random)
let v = arr[l]
// arr[l+1...i) <= v arr(j...r] >= v
// 初始化满足两块均为空
let i = l+1
let j = r
while(true) {
while(i<=r&&arr[i]<v) i++
while(r>=l+1&&arr[j]>v) j--
if(i>j) break
util.swap(arr,i,j)
i++
j--
}
util.swap(arr, l, j)
return j
}
let arr = util.randomArray(50000,0,10)
let arr1 = arr.slice()
util.testSort('归并排序', all.mergeSort,arr)
util.testSort('快速排序', quickSort, arr1)
// 归并排序: 15.351ms
// 快速排序: 9.162ms
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
可以看到,我们的快速排序又王者归来了~~哈哈哈
# 三路排序
在上面的快排的基础上,我们可以把之前的大于等于v和小于等于v改变为大于v 等于v 和小于v
function quickSort3Ways(arr) {
__quickSort3Ways(arr,0,arr.length-1)
}
// ----------------- 三路快速排序 -------------------------
function __quickSort3Ways(arr, l, r) {
// 递归出口
if (r - l <= 15) {
util.innerInsertionSort(arr, l, r)
return
}
let random = Math.floor(Math.random() * (r - l + 1)) + l
util.swap(arr, l, random)
let v = arr[l]
let lt = l // arr[l+1...lt] < v
let gt = r+1 // arr[gt...r] > v
let i = l+1 // arr[lt+1...i) === v
while (i<gt) {
if (arr[i] < v) {
util.swap(arr, lt + 1, i)
lt++
i++
}
else if (arr[i] > v) {
util.swap(arr,i,gt-1)
gt--
}
else {
i++
}
}
util.swap(arr,l,lt)
// 上面没有lt-- 所以这里是lt-1
__quickSort3Ways(arr, l, lt-1)
__quickSort3Ways(arr, gt, r)
}
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
33
34
35
36
37
38
39
40
三路排序在处理有重复数据的样本时,优势比较大,在处理大量非重复数据时,效率也不比普通快排差多少,所以很常用。