文档章节

快速排序

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

暂无文章

原型模式

1、原型模式-定义 用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象 克隆(浅度克隆->拷贝值类型或者引用,深度克隆->创建新的对象,开辟新的内存) 例如客户端知道抽象Pro...

阿元
今天
47
0
awk命令扩展使用操作

awk 中使用外部shell变量 示例1 [root@centos01 t1022]# A=888[root@centos01 t1022]# echo "" | awk -v GET_A=$A '{print GET_A}'888[root@centos01 t1022]# echo "aaaaaaaaaaaaa" | aw......

野雪球
今天
41
0
深入解析MySQL视图VIEW

Q:什么是视图?视图是干什么用的? A:视图(view)是一种虚拟存在的表,是一个逻辑表,本身并不包含数据。作为一个select语句保存在数据字典中的。   通过视图,可以展现基表的部分数据;...

IT--小哥
今天
45
0
虚拟机学习之二:垃圾收集器和内存分配策略

1.对象是否可回收 1.1引用计数算法 引用计数算法:给对象中添加一个引用计数器,每当有一个地方引用它时,计数器值就加1;当引用失效时,计数器值就减1;任何时候计数器值为0的对象就是不可能...

贾峰uk
今天
40
0
smart-doc功能使用介绍

smart-doc从8月份底开始开源发布到目前为止已经迭代了几个版本。在这里非常感谢那些敢于用smart-doc去做尝试并积极提出建议的社区用户。因此决定在本博客中重要说明下smart-doc的功能,包括使...

上官胡闹
昨天
47
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部