快速排序是一个使用较为广泛的排序算法,它的时间复杂度为O(nlogn),网络上很多文章讲解的快速排序都不太符合规范,本文以图文的形式详细讲解快速排序,并用JavaScript将其实现,欢迎各位感兴趣的前端开发者阅读本文?
快速排序算法:首先会在序列中随机选择一个基准值(pivot),然后将除了基准值以外的数分为“比基准值小的数” 和 “比基准值大的数”这两个类别。再将其排列成以下形式
接着,分别对基准值两边的数组进行快速排序,直至基准值的左侧只有一个数据,则排序完成。
如图所示,我们使用快速排序将其按照从小到大的顺序进行排列。
如图所示,我们已经根据基准值将数据进行了归类,将数据分为了两部分: 「左序列」和「右序列」,我们分别对这两部分数据递归进行快速排序,即可完成整体的排序。
采用同样的方法,选择基准值,比较数据,移动位置。
如图所示,执行完毕后,整体的排序工作也就完成了
正如图解示例所述,我们想实现快速排序,必须选择一个「基准值」,然后根据基准值将数据分为两个数组:「比基准值小的数组」和「比基准值大的数组」,把比基准值小的数据放进比基准值小的数组里,把大于等于基准值的数据放进比基准值大的数组里。
递归上述操作,直至基准值的左右两侧,任意一侧的数组长度小于2,则结束递归操作。
❝接下来,我们将上述思路转化为代码 ❞
/**
* 快速排序:
* @param arr 需要进行快速排序的数组
* @returns {*[]|*}
*/
const quickSort = function (arr) {
if(arr.length < 2) return arr;
// 随机选择0~arr.length之间选一个基准值
const pivot = Math.floor(Math.random() * arr.length)
// 声明两个数组,分别用于存放比基准值小的数据和比基准值大的数据
let minArr = [];
let maxArr = [];
// 根据基准值填充数组
for(let i = 0; i < arr.length; i++){
// 大于基准值就放maxArr里
if(arr[i] >= arr[pivot] && i !== pivot){
maxArr.push(arr[i]);
}
// 小于基准值就放minArr里
if(arr[i] < arr[pivot] && i !== pivot){
minArr.push(arr[i])
}
}
// 分别对基准值划分出来的数组递归调用快速排序,然后合并数组
return [...quickSort(minArr), arr[pivot], ...quickSort(maxArr)];
}
const dataArr = [3,5,8,1,2,9,4,7,6];
console.log(quickSort(dataArr))
本篇文章实现的快速排序完全符合书中对快速排序的定义,但是实际应用时它不是原地排序,会造成过多的内存消耗,且不稳定,排序效率较低。
快速排序的最优实现方式是三路排序,我们将马上来讲解!
在上半部分《排序算法:快速排序的理解与实现》中,我按照书中所描述的思路将其实现后,大家看了我的文章后提醒我,我的那个排序算法的实现不是最优的,非原地快排,会造成额外的内存浪费,同时性能也不是很好。
这篇文章就跟大家讲解下快速排序的最优实现方式:「三路快排」,并且使用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,表示这三个区间均为空;
我们将上述图解整理下,得出的实现思路如下:
❝接下来,我们将上述实现思路转换为代码 ❞
/**
*
* @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("三路快排");
我们将上一篇文章中写的普通快排与本篇文章写的三路快排进行运行速度的比对,我们看看哪种排序更快一些。
// 其他部分省略
/**
* 生成一个随机数组
* @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倍。」
● 手写async await的最简实现(20行搞定)面试必考!● Vue3 尝鲜 Hook + TypeScript 取代 Vuex 实现图书管理小型应用● 类型即正义,TypeScript 从入门到实践(四):5000字长文带你重新认识泛型
·END·