阅读:6290回复:2
【排序】快排算法 — 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 |
|
沙发#
发布于:2021-02-03 09:43
15252658462:B站而来,蛮好(鼓掌。。。。)回到原帖哈哈,欢迎欢迎 |
|
|
板凳#
发布于:2021-02-02 22:06
B站而来,蛮好(鼓掌。。。。)
|
|