首页 > 编程语言 > 详细

排序之快排(JS)

时间:2018-10-16 23:31:41      阅读:199      评论:0      收藏:0      [点我收藏+]

快速排序(Quicksort)是对冒泡排序的一种改进。

  它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

       详细描述:首先在要排序的序列 a 中选取一个中轴值,而后将序列分成两个部分,其中左边的部分 b 中的元素均小于或者等于 中轴值,右边的部分 c 的元素 均大于或者等于中轴值,而后通过递归调用快速排序的过程分别对两个部分进行排序,最后将两部分产生的结果合并即可得到最后的排序序列。

 

 

js实现

//交换数据
function swap(arr,i,j){
    arr[i]=arr[i]+arr[j];
    arr[j]=arr[i]-arr[j];
    arr[i]=arr[i]-arr[j];
    return arr;
}

//快排,一般index设置为0,从第一个数值开始
function fastSort( arr, left, right, index){
    let tmp = arr[index];
        //左边和右边是否相同,不同继续寻找
    while( right!=left){
                //从最右边找到一个比基准值小的数据,则进行交换
        while(arr[right] <= tmp ){
            right--;
            swap(arr,index,right);
            index = right;
        }
         //从最左边找到一个比基准值大的数据,则进行交换
        while(arr[left] >= tmp ){
            left++;
            swap(arr,index,left);
            index = left;
        }
    
                //以基准值索引为界,分别对其做序列以及有序列进行继续排序
        fastSort(arr, left, index-1);
        fastSort(arr, index+1, right);
    }
    return arr;
}  

 

排序之快排(JS)

原文:https://www.cnblogs.com/lidedong/p/9800946.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!