sunshine
管理员
管理员
  • 最后登录2023-10-30
  • 发帖数170
  • 社区居民
阅读:6290回复:2

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

楼主#
更多 发布于:2020-02-09 22:57
快排算法原理:
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

最新喜欢:

小达人小达人 15252658462152526...
doubleyong
管理员
管理员
  • 最后登录2024-11-22
  • 发帖数1195
  • 最爱沙发
  • 喜欢达人
  • 原创写手
  • 社区居民
  • 忠实会员
沙发#
发布于:2021-02-03 09:43
15252658462:B站而来,蛮好(鼓掌。。。。)回到原帖
哈哈,欢迎欢迎
知识需要管理,知识需要分享
15252658462
贫民
贫民
  • 最后登录2021-02-02
  • 发帖数1
板凳#
发布于:2021-02-02 22:06
B站而来,蛮好(鼓掌。。。。)
游客


返回顶部

公众号

公众号