快速排序可以说是目前所有排序算法中,最快的一种排序算法。当然,没有任何一种算法是在任意情况下都是最优的。但是,大多数情况下快速排序是比较好的选择。快速排序其实是冒泡排序的升级版;
快速排序的核心思想是分而治之,先选出一个数据(比如65),将比其小的数据都放在它的左边,将比它大的数据都放在它的右边。这个数据称为枢纽。和冒泡排序的不同:
- 我们选择的65可以一次性将它放在最正确的位置,之后就不需要做任何移动;
- 而冒泡排序即使已经找到最大值,也需要继续移动最大值,直到将它移动到最右边;
快速排序的枢纽的选择:
第一种方案: 直接选择第一个元素作为枢纽。但是,当第一个元素就是最小值的情况下,效率不高;
第二种方案: 使用随机数。随机数本身十分消耗性能,不推荐;
优秀的解决方法: 取
index
为头、中、位的三个数据排序后的中位数;如下图所示,按下标值取出的三个数据为:
92,31,0
,经排序后变为:0,31,92
,取其中的中位数31作为 枢纽(当(length-1)/2
不整除时可向下或向上取整):
实现枢纽选择:
//交换两个位置的数据
let swap = function(arr, m, n){
let temp = arr[m]
arr[m] = arr[n]
arr[n] = temp
}
//快速排序
//1.选择枢纽
let median = function(arr){
//1.取出中间的位置
let center = Math.floor(arr.length / 2)
let right = arr.length - 1
let left = 0
//2.判断大小并进行交换
if (arr[left] > arr[center]) {
swap(arr, left, center)
}
if (arr[center] > arr[right]){
swap(arr, center, right)
}
if (arr[left] > arr[right]) {
swap(arr, left, right)
}
//3.返回枢纽
return center
}
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
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
数组经过获取枢纽函数操作之后,选出的3个下标值对应的数据位置变为:
动态过程:
快速排序代码实现:
//2.快速排序
let QuickSort = function(arr){
if (arr.length == 0) {
return []
}
let center = median(arr)
//删除下标是center的元素
//splice会改变原数组 返回删除的元素
let c = arr.splice(center, 1)
let l = []
let r = []
for (let i = 0; i < arr.length; i++) {
if (arr[i] < c) {
l.push(arr[i])
}else{
r.push(arr[i])
}
}
//concat返回连接后的数组
return QuickSort(l).concat(c, QuickSort(r))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
算法的巧妙之处在于通过:
QuickSort(l).concat(c, QuickSort(r))
1
递归调用QuickSort
函数,实现了枢纽Center
左边数据l
和右边数据r
的排序;
测试代码:
let arr = [0, 13, 81, 43, 31, 27, 56, 92]
console.log(QuickSort(arr));
1
2
2
测试结果
快速排序的效率:
- 快速排序最坏情况下的效率:每次选择的枢纽都是最左边或最右边的数据,此时效率等同于冒泡排序,时间复杂度为
O(n²)
。可根据不同的枢纽选择避免这一情况; - 快速排序的平均效率:为
O(n*logn)
,虽然其他算法效率也可达到O(n*logn)
,但是其中快速排序是 最好的。