前言
在上一篇文章《排序算法:快速排序的理解与实现》中，我按照书中所描述的思路将其实现后，大家看了我的文章后提醒我，我的那个排序算法的实现不是最优的，非原地快排，会造成额外的内存浪费，同时性能也不是很好。
这篇文章就跟大家讲解下快速排序的最优实现方式：三路快排，并且使用JavaScript将其实现，三路快排是一个原地快排，同时性能也很好，欢迎各位感兴趣的前端开发者阅读本文
概念
从序列中随机找一个基准值(piovt)，移动序列中的元素进行分区，将小于基准值的元素移动至左分区，将等于基准值的元素移动至中间分区，将大于基准值的元素移动至右分区。分区完成后对左、右分区的元素分别进行快排。
图解示例
如图所示，我们将数组中的0号元素设为基准值(piovt)，设为p，将元素分为小于p,等于p，大于p三个部分。
元素i指向当前进行比较的元素，L为数组的起点，R为数组的末尾。
区间[L+1,lt]是小于p的元素，区间[lt+1,i-1]是等于p的元素，从右侧的R往内，形成的区间[gt,R]存放的是大于P的元素。
排序一开始，这些区间都是不存在的，我们需要确定边界，i的开始索引指向L+1，lt的初始值L，而gt的初始值是则是R+1，表示这三个区间均为空；
用JS实现三路快排
我们将上述图解整理下，得出的实现思路如下：
- 如果当前i指向的元素等于p，则i+1
- 如果当前i指向的元素小于p，则将lt+1处的元素与索引i处的值进行交换，然后lt+1,并且i+1
- 如果当前i指向的元素大于p，则将gt-1处的元素与索引i处的值进行交换，然后gt-1
- 最后当i走到gt处时，即gt==i时；那就说明，除了第一个元素之外，其余的空间已经分区完毕，只要将首个元素与lt处的元素进行交换，然后lt-1；我们就形成了想要的三个区间，小于p，等于p，大于p
接下来，我们将上述实现思路转换为代码
- 实现分区函数，用于返回：小于p,和大于p的元素区间信息
/**
*
* @param arr 需要进行三路快排的数组
* @param L 数组的起始位置
* @param R 数组的末尾位置
* @returns {{lt: *, gt: *}}
*/
const partition = function (arr, L, R) {
// 基准值为数组的零号元素
let p = arr[L];
// 左区间的初始值: L
let lt = L;
// 右区间的初始值: R+1
let gt = R + 1;
for (let i = L + 1; i < gt;){
if(arr[i] === p){
// 当前i指向的元素等于p
i++;
} else if(arr[i] > p){
// 当前i指向的元素大于p，将gt-1处的元素与当前索引处的元素交换位置，gt--
[arr[gt -1],arr[i]] = [arr[i],arr[gt - 1]];
gt--;
}else{
// 当前i指向的元素小于p，将lt+1处的元素与当前索引处的元素交换位置，lt+1，i+1
[arr[lt + 1],arr[i]] = [arr[i],arr[lt + 1]];
lt++;
i++;
}
}
// i走向gt处，除了基准值外的元素，其余的空间已经分区完毕，交换基准值与lt处的元素，lt-1，最终得到我们需要的三个区间
[arr[L],arr[lt]] = [arr[lt],arr[L]];
lt--;
console.log(`三路快排后的数组: ${arr}`);
return {lt : lt, gt : gt};
}
对分区函数进行测试
const dataArr = [3,5,8,1,2,9,4,7,6];
console.log(partition(dataArr,0,dataArr.length - 1));
- 实现三路快排函数
const threeWayFastRow = function (arr,L,R) {
// 当前数组的起始位置大于等于数组的末尾位置时退出递归
if(L >= R){
return false;
}
let obj = partition(arr, L, R);
// 递归执行: 将没有大于p,和小于p区间的元素在进行三路快排
threeWayFastRow(arr,L,obj.lt);
threeWayFastRow(arr,obj.gt,R);
}
对三路快排进行测试
console.time("三路快排");
const dataArr = [3,5,8,1,2,9,4,7,6];
threeWayFastRow(dataArr,0,dataArr.length - 1);
console.log(`三路快排完成: ${dataArr}`);
console.timeEnd("三路快排");
对比普通快排与三路快排
我们将上一篇文章中写的普通快排与本篇文章写的三路快排进行运行速度的比对，我们看看哪种排序更快一些。
- 我们随机生成10000个乱序元素的数组，用快速排序和三路快排进行测试
// 其他部分省略
/**
* 生成一个随机数组
* @param count
* @returns {[]}
*/
const randomArray = function(count){
let arr = [];
for (let i = 0; i < count; i++) {
arr[i] = Math.floor(Math.random() * 50 + 1);
}
return arr;
}
// ****普通快排其他部分省略****
// 生成数组
const dataArr = randomArray(10000);
console.time("普通快排");
quickSort(dataArr);
console.timeEnd("普通快排");
// ****三路快排其他部分省略****
// 生成数组
const dataArr = randomArray(10000);
console.time("三路快排");
threeWayFastRow(dataArr,0,dataArr.length - 1);
console.timeEnd("三路快排");
- 普通快排执行结果
- 三路快排执行结果
执行结果很明显，三路快排的排序效率是普通快排的2倍。
写在最后
- 文中如有错误，欢迎在评论区指正，如果这篇文章帮到了你，欢迎点赞和关注😊
- 本文首发于掘金，未经许可禁止转载💌
评论区