算法学习:快速排序
排序是指以特定顺序(数字或字母)排列线性表的元素。排序通常与搜索一起配合使用。 有许多排序算法,而迄今为止最快的算法之一是快速排序(Quicksort)
介绍
快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),简称快排,一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序n个项目要O(nLogn)次比较。在最坏状况下则需要O(n^2)次比较,但这种状况并不常见。事实上,快速排序O(nLogn)通常明显比其他算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地达成
基本步骤
- 从数组中选择一个元素作为基准点
- 排序数组,所有比基准值小的元素摆放在左边,而大于基准值的摆放在右边。每次分割结束以后基准值会插入到中间去。
- 最后利用递归,将摆放在左边的数组和右边的数组在进行一次上述的1和2操作。
![](https://tva1.js.work/large/008i3skNgy1gwu1dh7dgdj30ca09w3yl.jpg)
Javascript实现
const arr = [30, 10, 111, 35, 1899, 50, 45, 2, 1];
function sort(arr) {
// end
if (arr.length <= 1) return arr;
// body
var idx = Math.floor(arr.length / 2);
var point = arr[idx];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (i === idx) continue;
var el = arr[i];
if (el < point) {
left.push(el);
}
if (el >= point) {
right.push(el);
}
}
// recursive
return sort(left).concat(point, sort(right));
}
console.log(sort(arr));
关于递归的思考
- 什么时候需要开始递归(
recursive
) - 什么时候终止(
end
) - 逻辑体(
body
)