文档章节

快速排序

Demens
 Demens
发布于 2017/05/18 21:18
字数 1312
阅读 13
收藏 0

一、基本概念

      找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置。递归快速排序,将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置,排序完成。所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

二、选择基准元

1、固定基准元

      如果输入序列是随机的,处理时间是可以接受的。如果数组已经有序时,此时的分割就是一个非常不好的分割。因为每次划分只能使待排序序列减一,此时为最坏情况,快速排序沦为冒泡排序,时间复杂度为Θ(n^2)。而且,输入的数据是有序或部分有序的情况是相当常见的。因此,使用第一个元素作为基准元是非常糟糕的,应该立即放弃这种想法。 

2、随机基准元

      这是一种相对安全的策略。由于基准元的位置是随机的,那么产生的分割也不会总是会出现劣质的分割。在整个数组数字全相等时,仍然是最坏情况,时间复杂度是O(n^2)。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(n×log(n))的期望时间复杂度。

3、三数取中

      最佳的划分是将待排序的序列分成等长的子序列,最佳的状态我们可以使用序列的中间的值,也就是第N/2个数。可是,这很难算出来,并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为基准元而得到。事实上,随机性并没有多大的帮助,因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为基准元。

三、partition算法

      partition算法是快速排序的核心,在学习快排之前,可以先学习一下这个算法。下面先贴代码:

    public int partition(int[] num,int left,int right){
        if(num==null || num.length<=0 || left<0 || right>=num.length){
            return 0;
        }
        int prio=num[left+(right-left)/2];   //获取数组中间元素的下标
        while (left<=right){                 //从两端交替向中间扫描
            while (num[left]<prio)
                left++;
            while (num[right]>prio)
                right--;
            if (left<=right){
                swap(num,left,right);        //最终将基准数归位  
                left++;
                right--;
            }
        }
        return left;
    }

      这个方法的思路是先找一个枢纽元(这个方法实现里面找的是第一个元素,具体其实大有文章不过这里先简化描述),再从数组的两边(具体从哪里到哪里由传进来额参数决定)生成两个指针left和right,每次发现左边的元素大于枢纽元则i停下来,右边的元素小于枢纽元j就停下来,并且交换这个两个数的位置。直到两个指针left,right相遇。再把枢纽元插入left的位置,也就是它应该在的位置。

      这么做最后的结果是让数组的[left,right]部分呈现出2部分,枢纽元最终位置以左都是小于等于枢纽元的,以右都是大于等于枢纽元的。而枢纽元则被插入到了一个绝对正确的位置。

四、排序算法实现

package sort;
/**
 * 快速排序
 * 快速排序采用了分治策略。就是在一个数组中取一个基准数字,把小的数放基准的左边,大的数放基准的右边。
 * 基准左边和右边分别是新的序列。在新的序列中再取一个基准数字,小的放左边,大的放右边。
 * 这个里面用到的递归。我们需要三个参数,一个是数组,另外两个是序列的边界
 * @author HJS
 */
public class QuickSort{

    void sort(int num[],int left,int right){
        if (left<right){
            int index=partition(num,left,right); //算出枢轴值 
            sort(num,left,index-1);       //对低子表递归排序
            sort(num,index+1,right);        //对高子表递归排序
        }
    }

    /**
     * 调用partition(num,left,right)时,对num[]做划分,
     * 并返回基准记录的位置
     * @param num
     * @param left
     * @param right
     * @return
     */
    public int partition(int[] num,int left,int right){
        if(num==null || num.length<=0 || left<0 || right>=num.length){
            return 0;
        }
        int prio=num[left+(right-left)/2];   //获取数组中间元素的下标
        while (left<=right){                 //从两端交替向中间扫描
            while (num[left]<prio)
                left++;
            while (num[right]>prio)
                right--;
            if (left<=right){
                swap(num,left,right);        //最终将基准数归位  
                left++;
                right--;
            }
        }
        return left;
    }


    public void swap(int[] num,int left,int right){
        int temp = num[left];
        num[left] = num[right];
        num[right] = temp;
    }
    public static void main(String args[]){
        int[] num={7,3,5,1,2,8,9,2,6};
        new QuickSort().sort(num,0,num.length-1);
        for(int n:num) {
            System.out.print(n+" ");
        }
    }
}

 

 

© 著作权归作者所有

共有 人打赏支持
Demens
粉丝 0
博文 11
码字总数 14760
作品 0
私信 提问

暂无文章

windows下让 jar 在后台运行的办法

windows下 运行 java jar 不出现 命令行 窗口 新建一个披处理 run.bat,内容如下 @echo off start javaw -jar xx.jar exit 双击运行即可。...

glen_xu
16分钟前
1
0
jdk1.8 lambda stream 指定的对象属性进行去重

原因:因为Stream提供的distinct()方法只能去除重复的对象,无法根据指定的对象属性进行去重,可以应付简单场景。 解决方案: //去重,共同信息保存到bizPledgeSupplierVOs里bizPledgeSupp...

INSISTQIAO
18分钟前
0
0
vue nextTick深入理解---vue性能优化、DOM更新时机、事件循环机制

定义[nextTick、事件循环] nextTick的由来: 由于vue的数据驱动视图更新是异步的,即修改数据的当下,视图不会立即更新,而是等同一事件循环中的所有数据变化完成之后再统一进行视图更新。...

JamesView
26分钟前
1
0
常用汉字编码

GB2312 仅包含大部分的常用简体汉字,但已经不能适应现在的需要; GB13000 由于GB2312的局限性,国家标准化委员会制定了GB13000编码; 但由于当时的硬件和软件都已经支持了GB2312,而GB13000...

晨猫
28分钟前
1
0
纳尼?我的Gradle build编译只要1s

https://juejin.im/post/5c00ec39e51d4555ec0394f6

SuShine
29分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部