为了更深入的理解,可以看下面这张图
我们根据上面这张图,来用文字描述一下
以上就是快速排序基本的一个实现思想。
这是我最近看到的一种快排代码
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));
};
以上代码的实现方式是,选择一个中间的数字为基准点,用两个数组分别去保存比基准数小的值,和比基准数大的值,最后递归左边的数组和右边的数组,用concat去做一个数组的合并。
对于这段代码的分析: 缺点:
优点:
下面是拆分的过程,其实就是对指针进行移动,找到最后指针所指向的位置
/**
*
* @param {*} A 数组
* @param {*} p 起始下标
* @param {*} r 结束下标 + 1
*/
function dvide(A, p, r){
// 基准点
const pivot = A[r-1];
// i初始化是-1,也就是起始下标的前一个
let i = p - 1;
// 循环
for(let j = p; j < r-1; j++){
// 如果比基准点小就i++,然后交换元素位置
if(A[j] <= pivot){
i++;
swap(A, i, j);
}
}
// 最后将基准点插入到i+1的位置
swap(A, i+1, r-1);
// 返回最终指针i的位置
return i+1;
}
主程序主要是通过递归去重复的调用进行拆分,一直拆分到只有一个数字。
/**
*
* @param {*} A 数组
* @param {*} p 起始下标
* @param {*} r 结束下标 + 1
*/
function qsort(A, p, r){
r = r || A.length;
if(p < r - 1){
const q = divide(A, p, r);
qsort(A, p, q);
qsort(A, q + 1, r);
}
return A;
}
完整代码
function swap(A, i, j) {
const t = A[i];
A[i] = A[j];
A[j] = t;
}
/**
*
* @param {*} A 数组
* @param {*} p 起始下标
* @param {*} r 结束下标 + 1
*/
function divide(A, p, r) {
const x = A[r - 1];
let i = p - 1;
for (let j = p; j < r - 1; j++) {
if (A[j] <= x) {
i++;
swap(A, i, j);
}
}
swap(A, i + 1, r - 1);
return i + 1;
}
/**
*
* @param {*} A 数组
* @param {*} p 起始下标
* @param {*} r 结束下标 + 1
*/
function qsort(A, p = 0, r) {
r = r || A.length;
if (p < r - 1) {
const q = divide(A, p, r);
qsort(A, p, q);
qsort(A, q + 1, r);
}
return A;
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。