文档章节

快速排序

Demens
 Demens
发布于 2017/05/18 21:18
字数 1312
阅读 12
收藏 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

暂无文章

php 使用redis锁限制并发访问类

1.并发访问限制问题 对于一些需要限制同一个用户并发访问的场景,如果用户并发请求多次,而服务器处理没有加锁限制,用户则可以多次请求成功。 例如换领优惠券,如果用户同一时间并发提交换领...

豆花饭烧土豆
9分钟前
0
0
Linux环境搭建 | 手把手教你配置Linux虚拟机

在上一节 「手把你教你安装Linux虚拟机」 里,我们已经安装好了Linux虚拟机,在这一节里,我们将配置安装好的Linux虚拟机,使其达到可以开发的程度。 Ubuntu刚安装完毕之后,还无法进行开发,...

良许Linux
10分钟前
0
0
Nginix开启SSL支持HTTPS访问(自签名方法)

Nginix开启SSL支持HTTPS访问(自签名方法) 超文本传输安全协议(缩写:HTTPS,英语:Hypertext Transfer Protocol Secure)是超文本传输协议和SSL/TLS的组合,用以提供加密通讯及对网络服务器...

openthings
26分钟前
0
0
(三)Nginx配置·续

概述 前文写了关于Nginx环境配置,但是还没有完,接下来将会继续讲三个相关的配置 主要是以下三个 1.Nginx访问日志 2.Nginx日志切割 3.静态文件不记录日志和过期时间 Nginx访问日志 1.先看看...

杉下
今天
1
0
jquery创建类似于java的map

var map = {}; // Map map = new HashMap(); map[key] = value; // map.put(key, value); var value = map[key]; // Object value = map.get(key); var has = key in map; // boolean has = ......

SuperDabai
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部