都说快排是个很伟大的排序算法,名如其名,速度很快,而且是原位排序.
快排的精髓就在于,从数组中找一个基准点piovt(可以随便找,也可以找第一个),然后将数组元素移动分区,左边小于pivot,中间部分则是等于pivot,右边一部分是大于pivot的,然后对于左右两部分在进行快排.
三路快排示意图
看上图:
我们以首个元素为基准点,将元素分为小于 v ,等于 v , 大于 v 三个部分;而元素i则指向当前进行比较的元素, 区间 [l+1,lt]是小于v的元素,区间[lt+1,i-1]则表示的是等于v的元素,从最右边的索引r处开始往内,形成的区间[gt,r]存放的是大于v的元素;
当然一开始这些区间其实都是不存在的,我们需要确定边界,i的开始索引指向l+1,lt的初始值是l,而gt的初始值则是r+1,表示的是这三个区间均为空;
-
当排序开始时
- 如果当前i 指向的元素 等于v,那很好,i+1;
- 如果当前i 指向的元素 小于v,那么就将 lt+1 与索引 i处的值 进行交换,
然后lt+1, 并且 i+1; - 如果当前元素 大于 v,那么 就将 gt - 1 处的元素与 当前元素 交换,然后gt-1.
- 最后当i 走到 gt 处 即 gt==i 时 ;那就说明 除了第一个元素之外,其余的区间已经分区完毕,只要将首个元素与 lt 处的元素进行交换, 然后lt -1 ;我们就形成了想要的三个区间,小于v,等于v,然后是大于v的.
4.代码编写,首先是个交换函数,用于交换两个索引位置处的值
function swap(arr, a, b) {
let temp;
temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
5.然后就是根据上面逻辑编写的分区函数,这个函数应当返回,小于v,和大于v的元素的区间信息:
function partion(arr, l, r) {
//基准数选取区间的第一个值
let v = arr[l];
let lt = l;
let gt = r + 1;
for (let i = l + 1; i < gt; ) {
if (arr[i] == v) {
i++;
} else if (arr[i] > v) {
swap(arr, gt - 1, i);
gt--;
} else {
swap(arr, lt + 1, i);
lt++;
i++;
}
}
swap(arr, l, lt);
lt--;
return { lt: lt, gt: gt };
}
6.最后就是我们快排函数 , 明显就是用递归了,将没有大于v,和小于v区间的元素在进行快排
function quicksort(arr, l, r) {
// 只有l<r 才需要对元素进行处理
if (l >= r) {
return;
}
let obj = partion(arr, l, r);
quicksort(arr, l, obj.lt);
quicksort(arr, obj.gt, r);
}
7.好了快排到此就实现了我们来编写个测试用例 测试实现的这个快排 有多快
//生成一个近乎有序的数组
function randomNearlyOrderArray(count) {
let arr = [];
for (let i = 0; i < count; i++) {
arr[i] = Math.floor(Math.random() * 50 + 1);
}
return arr;
}
//测试数组是否已经排序
function isSorted(arr) {
for (let i = 0; i + 2 < arr.length - 1; i++) {
if (
(arr[i] > arr[i + 1] && arr[i + 1] < arr[i + 2]) ||
(arr[i] < arr[i + 1] && arr[i + 1] > arr[i + 2])
) {
return false;
}
}
return true;
}
8.来看看 node.js 下的实验结果吧,
对于生成 10000000
我们的三路快排花费 350 ms 左右
自己写的快排
使用Array.prototype.sort 来对数组进行排序
则 花费了 3500 ms 左右
Array.prototype.sort
- 总结,看来 我们的快排在处理 近乎有序 数组时 还是 效率挺高的 ,原因就是,多了个 等于元素v的区间,这部分的元素,在形成后,下次就不需要移动了,所以效率会很高.
