Java实现快速排序方法-演道网

本网站用的阿里云ECS,推荐大家用。自己搞个学习研究也不错
快速排序

算法思想:基于分治的思想,是冒泡排序的改进型。首先在数组中选择一个基准点(该基准点的选取可能影响快速排序的效率,后面讲解选取的方法),然后分别从数组的两端扫描数组,设两个指示标志(lo指向起始位置,hi指向末尾),首先从后半部分开始,如果发现有元素比该基准点的值小,就交换lo和hi位置的值,然后从前半部分开始扫秒,发现有元素大于基准点的值,就交换lo和hi位置的值,如此往复循环,直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序,当前半部分和后半部分均有序时该数组就自然有序了。

排序过程:

再通过动图看看:

算法实现:

public static int partition(int []array,int lo,int hi){
        //固定的切分方式
        int key=array[lo];
        while(lo<hi){
            while(array[hi]>=key&&hi>lo){//从后半部分向前扫描
                hi–;
            }
            array[lo]=array[hi];
            while(array[lo]lo){从前半部分向后扫描
                lo++;
            }
            array[hi]=array[lo];
        }
        array[hi]=key;
        return hi;
    }
   
    public static void sort(int[] array,int lo ,int hi){
        if(lo>=hi){
            return ;
        }
        int index=partition(array,lo,hi);
        sort(array,lo,index-1);
        sort(array,index+1,hi);
    }

快速排序的时间复杂度为O(NlogN).

快速排序的优化

对于基准位置的选取一般有三种方法:固定切分,随机切分和三取样切分。固定切分的效率并不是太好,随机切分是常用的一种切分,效率比较高,最坏情况下时间复杂度有可能为O(N2).对于三数取中选择基准点是最理想的一种。

三数取中切分:

public static int partition(int []array,int lo,int hi){
        //三数取中
        int mid=lo+(hi-lo)/2;
        if(array[mid]>array[hi]){
            swap(array[mid],array[hi]);
        }
        if(array[lo]>array[hi]){
            swap(array[lo],array[hi]);
        }
        if(array[mid]>array[lo]){
            swap(array[mid],array[lo]);
        }
        int key=array[lo];
       
        while(lo<hi){
            while(array[hi]>=key&&hi>lo){
                hi–;
            }
            array[lo]=array[hi];
            while(array[lo]lo){
                lo++;
            }
            array[hi]=array[lo];
        }
        array[hi]=key;
        return hi;
    }
   
    public static void swap(int a,int b){
        int temp=a;
        a=b;
        b=temp;
    }
    public static void sort(int[] array,int lo ,int hi){
        if(lo>=hi){
            return ;
        }
        int index=partition(array,lo,hi);
        sort(array,lo,index-1);
        sort(array,index+1,hi);
    }

快速排序在序列中元素很少时,效率将比较低,不然插入排序,因此一般在序列中元素很少时使用插入排序,这样可以提高整体效率。

 public static void quick(int []array ,int lo,int hi){
        if(hi-lo+1<10){
            insertSort(array);
        }else{
            quickSort(array,lo,hi);
        }
    }

转载自演道,想查看更及时的互联网产品技术热点文章请点击http://go2live.cn

未经允许不得转载:演道网 » Java实现快速排序方法-演道网

赞 (0)
分享到:更多 ()

评论 0

评论前必须登录!

登陆 注册