文档章节

快速排序

AllenOR灵感
 AllenOR灵感
发布于 2017/09/10 01:00
字数 703
阅读 1
收藏 0

快速排序是一种分治的排序算法,它将一个数组分解成两个子数组,将两部分独立的排序。快速排序与归并排序是互补的:归并排序将数组分成两个子数组分别排序,并将有序的数组归并,已将整个数组排序;而快速排序将数组排序的方式是当两个数组都有序时整个数组自然就有序了。第一种情况递归调用发生在整个数组之前,第二种情况递归发生在处理数组之后。在归并排序中一个数组被等分成两半,而在快排中这取决于切分的位置

1.jpg
1.jpg
    public void sort(Comparable[] a) {
        //StdRandom.shuffle(a);
        shuffle(a);    //将数组随机打乱,这一步很重要,会影响性能
        sort(a, 0, a.length - 1);
    }

    public void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo)
            return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    private int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        Comparable v = a[lo];
        while (true) {
            while (less(a[++i], v))
                if (i == hi) break;

            while (less(v, a[--j]))
                if (j == lo) break;

            if (i >= j) break;

            exch(a, i, j);
        }
        exch(a, lo, j);

        return j;
    }

    private boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
    
    private void shuffle(Object[] a) {
        if (a == null) throw new IllegalArgumentException("argument array is null");
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int randomNum = i + uniform(n-i);
            Object temp = a[randomNum];
            a[randomNum] = a[i];
            a[i] = temp;
        }
    }
    
    //[0,n)
    private int uniform(int n) {
        if (n <= 0) throw new IllegalArgumentException("argument must be positive");
        return new Random(System.currentTimeMillis()).nextInt(n);
    }

来看看快速排序的切分轨迹,大小16的数组:

2.jpg
2.jpg

快速排序最理想的情况就是切分正好将数组等分,复杂度为nlgn。最坏情况是一边数组为空,复杂度为N^2/2,我们将数组在开始时打乱就是为了预防这种情况

算法改进

  1. 对于小数组,快速排序比插入排序慢,所以确定一个阀值M,推荐在5~15之间。将if (hi <= lo) return;改为if(hi <= lo + M) {InsertionSort(a, lo, hi); return;}
  2. 对于有大量重复元素的数组,将数组三分,指针lt,gt,i:规定[lo, lt-1]小于切分元素v,[lt, i-1]等于v,[i, gt]为未确定元素,[gt+1, hi]大于v;该方法对于包含大量重复元素的数组,能将排序时间从线性对数级降低到线性级别。
    public void sort(Comparable[] a) {
        shuffle(a);
        sort(a,0,a.length-1);
        assert isSorted(a);
    }
    
    private void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, gt = hi;
        Comparable v = a[lo];
        int i = lo;
        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if (cmp < 0)        exch(a, lt++, i++);
            else if (cmp > 0)   exch(a, i, gt--);
            else                i++;
        }
        sort(a, lo, lt-1);
        sort(a, gt+1, hi);
        assert isSorted(a, lo, hi);
    }

本文转载自:http://www.jianshu.com/p/722a33ba425a

AllenOR灵感
粉丝 11
博文 2635
码字总数 83001
作品 0
程序员
私信 提问

暂无文章

OSChina 周四乱弹 —— 当你简历注水但还是找到了工作

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @花间小酌 :#今日歌曲推荐# 分享成龙的单曲《男儿当自强》。 《男儿当自强》- 成龙 手机党少年们想听歌,请使劲儿戳(这里) @hxg2016 :刚在...

小小编辑
今天
2.7K
22
靠写代码赚钱的一些门路

作者 @mezod 译者 @josephchang10 如今,通过自己的代码去赚钱变得越来越简单,不过对很多人来说依然还是很难,因为他们不知道有哪些门路。 今天给大家分享一个精彩的 GitHub 库,这个库整理...

高级农民工
昨天
4
0
用好项目管理工具,人人都可以成为项目经理

现在市面上的项目管理工具越来越多了,但是大多数都是一些协同工具或轻量项目管理工具。如果是多团队、跨部门使用或者企业级的项目管理,从管理思想到工具运用,需要适应企业的业务流程体系,...

cs平台
昨天
12
0
只需一步,在Spring Boot中统一Restful API返回值格式与统一处理异常

统一返回值 在前后端分离大行其道的今天,有一个统一的返回值格式不仅能使我们的接口看起来更漂亮,而且还可以使前端可以统一处理很多东西,避免很多问题的产生。 比较通用的返回值格式如下:...

晓月寒丶
昨天
69
0
区块链应用到供应链上的好处和实际案例

区块链可以解决供应链中的很多问题,例如记录以及追踪产品。那么使用区块链应用到各产品供应链上到底有什么好处?猎头悬赏平台解优人才网小编给大家做个简单的分享: 使用区块链的最突出的优...

猎头悬赏平台
昨天
32
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部