一图读懂快速排序（Quick Sort）
2021-09-06 本文已影响0人
老鼠AI大米_Java全栈
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法介绍
快速排序(Quick Sort)使用分治法策略。
它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法描述：
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 "基准"（pivot），
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
动图演示
quickSort.gif
注意：这里基准值是基于数组下标取的。
代码实现
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
说明：
选择基数为参照，划分数组，分而治之，对于新手来理解快排的核心思想“参照-划分-递归”，很容易理解 。
既实现了排序，又符合快速排序的思想，为什么还会为人所诟病呢？原来是因为：
-
基数用的是splice()函数取，而不是算法中常用的取下标。基数只是一个参照对象，在比对的时候，只要能从数组中取到即可，所以只需要知道它的索引即可，调用函数删除基数只会更耗时；
-
根据基数来划分时，生成两个数组来存储，从而占用了更多的存储空间（增加了空间复杂度）。
更快的排序
实现思路：
- 通过下表取排序区间的第0个数为基数
- 排序区间基数以后，从右往左，寻找比基数小的，从左往右，寻找比基数大的，原地交换；
- 重复步骤2直到 i >= j；
- 将基数与下标为 i 的元素原地交换，从而实现划分；
- 递归排序基数左边的数，递归排序基数右边的数，返回数组。
代码实现
var quickSort_New = function(ary, left, right) {
if(left >= right) {
return ary;
}
var i = left,
j = right;
base = ary[left];
while (i < j) {
// 从右边起，寻找比基数小的数
while (i<j && ary[j] >= base) {
j--;
}
// 从左边起，寻找比基数大的数
while (i<j && ary[i] <= base) {
i++
}
if (i<j) {
var temp = ary[i];
ary[i] = ary[j];
ary[j] = temp;
}
}
ary[left] = ary[i];
ary[i] = base;
quickSort_New(ary, left, i-1);
quickSort_New(ary, i+1, right);
return ary;
}
说明：
以上方式使用双向递归快速查找的方式实现，效率翻倍。
朵拉姐【ITI2018】的前端摸鱼技术群
欢迎大家技术交流 内推 摸鱼 求助皆可 - 链接
