什么是快速排序?
(以从小到大排序为例) 快速排序可以简单的理解为以下思路:
每次选择一个基数(一般默认取数组下标为零的数).把比基数大的数放在基数右边.把比基数小的数放在基数左边.把被基数分开的数组两边分开处理重复上述操作,直到数组为有序. 举个列子: 先不用考虑程序如何实现 base = 2,把 数组中大于 2 的数 4, 3, 5 和小于base 的数 1,0选出来 手动的调整数组顺序 现在考虑被 2 分开的两个子数组 按照上述思想 处理数组[1,0] ==> [0,1] 处理数组[4,3,5] ==> [3,4,5] 这样一个人工的快速排序就完成了.
现在考虑真正编程如何实现上述的排序过程
准备两个下标left 和 right 分别指向 数组的 第一个元素和最后一个元素 如图
控制 right 下标找到一个比 base 小的数,然后控制 left 下标 找到一个比base 大的数 并交换 如图:
继续 right 下标 找一个比 base 小的数 发现走到了left == right 此时应退出 此循环操作,同时交换 base 和 left指向的数 如图:
依照上述思想,把{0,1,2} 和{3,4,5}分别作为数组递归执行上述步骤.
下面是代码部分
Array
.prototype
.quickSort_recursion = function (left
, right
) {
if (left
>= right
)
return;
let arr
= this, i
= left
, j
= right
;
let base
= left
;
while (i
< j
) {
while (arr
[j
] > arr
[base
] && j
> i
) j
--;
while (arr
[i
] < arr
[base
] && i
< j
) i
++;
if (i
!= j
) {
let temp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = temp
;
}
}
if (i
== j
) {
let temp
= arr
[base
];
arr
[base
] = arr
[i
];
arr
[i
] = temp
;
}
this.quickSort_recursion(left
, i
);
this.quickSort_recursion(i
+ 1, right
);
}
Array
.prototype
.quickSort = function () {
let len
= this.length
;
this.quickSort_recursion(0, len
- 1);
}
let arr
= [2, 1, 4, 3, 0, 5];
arr
.quickSort();
总结一下
快速排序的时间复杂度为O(nlogn~n^2) nlogn 的情况是,当每次选择的base 把数组两部分平分的情况 n^2 的情况是,当 每次选择的base 正好是数组中的最大值或者最小值的时候,会退化为冒泡排序
