关于高级快拍排的算法记录（将老师基础代码融合到一起）
来源：5-11 快速排序-高级算法
橙序猿哥哥
2019-06-09
优化：
解决基础快排占用内存过多问题，基础方法中每次都要生成新的left和right数组，很占内存
优化思路：
每次循环都是在arr上操作，代码思路仍是首先选定一个标志位，一般选被排序数组的第一位，也就是代码中的 left 位，“分水岭位”的起始位置为 index 位，每次循环都是从 left 下一位开始，与flag（ arr[left] ）对比，比标志位大的不动，比 flag 小的 和 index 交换位置，并且index分水岭位加一，如此循环到right，循环完成后还需要将index的前一位与left交换位置，满足index-1的前面值都小于flag，后面值都大等于flag，再将 index-1 左右两部分分别放入下一轮循环，如此往复，直到 left 和 right 重合，即排序段只剩一个数，完成排序，每次递归不用返回，因为arr已经被排序完成直接，直接调用arr就可也看到排序结果。
let quickSort = (arr) => {
/*
*目标：用一个数组完成所有排序 ，减少内存占用
*/
let sort = (arr , left , right) => {
if( right - left < 1 ){
//边界条件，只剩一个
return arr;
}
let flag = arr[left];
let index = left + 1;
let temp;
for( let i= left + 1 ; i <= right ; i++ ){
if( arr[i] < flag ){
//比标准值flag小，交换arr[i]和arr[index] ，
//最终要实现index向右的部分都是比flag大的
temp = arr[i]
arr[i] = arr[index]
arr[index] = temp
index++;
}
}
temp = arr[index-1]
arr[index-1] = arr[left]
arr[left] = temp;
//以flag为中心左边小于flag，右边大于等于flag，分别再循环排序
sort( arr , left , index-2 );
sort( arr , index , right );
}
sort(arr , 0 , arr.length-1);
return arr
}
let result = quickSort([2,34,43,2,1,5,5,6,3,4,1]);
console.log(result);
写回答
2回答
-
很赞，可否将代码提供到 git 的 issue
012019-06-10 -
pino宋
2019-06-20
/** ** 快速排序的高级写法 * * --- * 一第一轮 * 1先把一个数组中的一个数当作基准数一般会把最左边的数当作基准数 * 2然后从两边进行检索。先从右边向左-1检索比基准数小的。再去左边向右+1检索比基准数大的 * // 如果把最右当作基准数要从先从左边检索 * 如果检索到了就停下然后交换左边和右边检索出来的数这两个元素然后继续检索 * 3右边向左-1的检索与左边向右+1的检索相遇之后 停止检索。 * 4 把基准数与相遇的位置 交换 * 此时基准数在中间左边的数 都比它小右边的数都比他大 * 二第二轮 进行下一轮排序 * 先排<左边>排序规则跟上边的步骤一样 再排右边 排序规则跟上边的步骤一样 * */ export const fasterSort2 = (array) => { // left 基准数的左边的索引 // right 基准数右边的索引 let l = 0; let r = array.length - 1; let quickSort2 = (arr, left, right) => { // 如果<左边>的索引比右边的索引大 直接推出循环 if (left > right) { return; } // 定义基准数 let base = arr[left]; // 从哪里(开始)排就把那里当作基准数 let i = left; // 定义i指向最左边位置 let j = right; // 定义j指向最右边位置 // 检索 while (i !== j) { // 当 i 和 j 不相遇的时候在循环中进行检索 // 先由 j 从右检索比基准数小的如果检索到比基准数小的就停下 反过来大的相等的 就继续检索 while (arr[j] >= base && i < j) { // 数组j位置的元素 大于等基准数继续循环检索 // 如果这个条件不成立表示 arr[j]元素比基准数要小 j--; // j 从右往左移动一位 } // i 要从左往右检索 while (arr[i] <= base && i < j) { // while循环条件不成立 自动跳出 i++; // i 从左往右移动 } // 代码走到这里i 停下了j 也停下了都找到了符合条件的元素 // ---交换元素--- let tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // 相遇之后---交换基准数与相遇位置的元素)——-- arr[left] = arr[i]; // 把相遇位置的数赋值给基准数 arr[i] = base; // 再基准数赋值给相遇位置的数完成交换 // 交换完成之后基准数这里就归位了左边的都比他小右边的都比他大 // -----------第一轮完成------------ // 第二轮遍历 排基准数<左边的第一位数>基准数是i的位置 quickSort2(arr, left, i - 1); // 第二轮遍历 排基准数<右边的左边第一位数>基准数是的位置 quickSort2(arr, i + 1, right); // eslint-disable-next-line consistent-return return arr; }; return quickSort2(array, l, r); };00
相似问题