【排序】快排算法 — js实现

快排算法原理：
1.找基数
2.比较基数大的放右数，比较基数小的放左边
3.将基数左边的数据，右边的数据，在重复1,2操作（递归方法）
视频说明：https://www.bilibili.com/video/av87754035?from=search&seid=17566016923196250679

以下方法，实现思路：

1、通过下表取排序区间的第0个数为基数
2、排序区间基数以后，从右往左，寻找比基数小的，从左往右，寻找比基数大的，原地交换；
3、重复步骤2直到 i >= j；
4、将基数与下标为 i 的元素原地交换，从而实现划分；
5、递归排序基数左边的数，递归排序基数右边的数，返回数组。

/**
题目：快速排序算法
思路：两个哨兵，i,j,j从右边找比基数小的，i从左边找比基数大的，然后交换两个目标元素的位置，直到i=j,然后交换i和基数的位置，递归处理。 
**/
function quick_sort(arr,from,to){
    var i = from; //哨兵i， 相当于left
    var j = to; //哨兵j, 相当于right
    var key = arr[from]; //标准值
    if(from >= to){ //如果数组只有一个元素
       return;
    }
    while(i < j){
        while(arr[j] > key && i < j){ //从右边向左找第一个比key小的数，找到或者两个哨兵相碰，跳出循环
            j--;
        }
        while(arr<i> <= key && i < j){  //从左边向右找第一个比key大的数，找到或者两个哨兵相碰，跳出循环,这里的=号保证在本轮循环结束前，key的位置不变，否则的话跳出循环，交换i和from的位置的时候，from位置的上元素有可能不是key
            i++;
        }
        /**
          代码执行道这里，1、两个哨兵到找到了目标值。2、j哨兵找到了目标值。3、两个哨兵都没找到(key是当前数组最小值)
        **/
        if(i < j){ //交换两个元素的位置
            var temp = arr<i>;
            arr<i> = arr[j];
            arr[j] = temp;
        }
    }
    arr[from] = arr<i> //
    arr<i> = key;
        quick_sort(arr,from,i-1);
    quick_sort(arr,i+1,to);
}
var arr = [3,3,-5,6,0,2,-1,-1,3];
console.log(arr);
quick_sort(arr,0,arr.length-1);
console.log(arr);</i></i></i></i></i>

参考：https://blog.csdn.net/zhao529670074/article/details/80776253
更多方法，可以参考：https://www.cnblogs.com/hjx-blog/articles/9183453.html

15252658462：B站而来，蛮好(鼓掌。。。。)回到原帖

哈哈，欢迎欢迎

B站而来，蛮好(鼓掌。。。。)