快速排序(Quick Sort)

1. 简介

快速排序是由C.A.R.Hoare在1960年发明的。快速排序可能是应用最广泛的排序算法了,快速排序的实现简单,平均时间复杂度是O(NlgN),而且它是原地排序。其实在快排的实现有一些坑,如果不仔细一点,快排也许就变成慢排了。
接下来所讲的排序都是从小到大排序的,代码也是java描述的:

与归并排序一样,快速排序也采用了分而治之的思想。

  1. 在数组中选取一个元素作为主元
  2. 将数组切分成左右两半,左边一半的元素小于等于主元,右边一半的元素大于等于主元
  3. 将左边排序
  4. 将右边排序
  5. 因为左边已经小于等于右边了,所以当左右两边都排完序,整体也就有序了

2. 代码实现

public class QuickSort {

    //交换数组中两个元素的位置
    private static void swap(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    //切分数组的函数
    private static int partition(Comparable[] a, int left, int right){
        swap(a, (left + right) / 2, left);
        Comparable v = a[left];  //v是主元
        int i = left, j = right + 1;
        
        while (true) {
            while (a[++i].compareTo(v) < 0)
                if (i == right)
                    break;

            while (a[--j].compareTo(v) > 0)
                if (j == left)
                    break;

            if (i < j)
                swap(a, i, j);
            else
                break;
        }
        swap(a, j, left);
        return j;
    }

    private static void sort(Comparable[] a, int left, int right){
        if (left >= right) 
            return;
        int i = partition(a, left, right);  //切分数组,返回切分的位置,也就是主元的位置
        sort(a, left, i - 1);   //对数组的左半边排序
        sort(a, i + 1, right);  //对数组的右半边排序
    }

    public static void sort(Comparable[] a){
        sort(a, 0, a.length - 1);
    }


    //测试
    public static void main(String[] args) {
        Integer[] a = new Integer[]{1, 3, 4, 7, 9, 2};
        sort(a);
    }
}

辅助函数
这一段是快速排序的简单实现,还有一些可以优化的地方。先来介绍一下实现过程需要用的辅助函数:

  • 因为排序过程中需要与主元进行比较且参与排序的元素是类变量,所以要求排序的元素需要实现Comparable接口重写compareTo()函数。
  • 在与主元比较后可能需要交换位置所以用一个swap()函数交换两个元素的位置。

3. 快速排序性能与复杂度分析

快速排序的运行时间取决于切分是否平衡,而是否平衡又依赖于切分的元素,也就是主元的选择。

  • 最坏情况
    假设我们每次选择的主元恰好是待排数组中的极值且元素都不重复时,例如最小值:根据切分函数,指针i在遇到第一个元素就停下来,而j却一直向左遍历直到遇到主元才停下来。最终切分的位置变成了left,切分出一个大小为0的数组和一个大小为n - 1的数组,不烦假设每次都出现这种不平等的切分,切分的操作时间复杂度为O(n),对一个大小为0的数组递归调用排序会直接返回,因此T(0) = O(1)。于是算法的运行时间的递归式可表达为:T(n) = T(0) + T(n - 1) + O(n) = T(n - 1) + O(n),T(n)的解是O(n^2)
  • 最好情况
    最好的情况是每次切分后的两个数组大小都不大于n / 2时,这时一个的数组的大小为[n / 2 - 1],另一个为[n / 2],此时算法运行时间的递归式为:T(n) = 2T(n / 2) + O(n),T(n)的解是O(nlgn)
  • 平均情况
    快速排序的平均运行时间其实更接近与最好情况,而非最坏情况。

4. 算法优化

1. 切换到插入排序

  • 对于小数组,快速排序比插入排序慢
  • 因为递归,快速排序的sort()方法在小数组中也会调用自己

所以可以当数组在大小在M以内时调用插入排序,M的取值可以是5 ~ 15。

2. 选择合适的主元
如我上面所说,假设我们每次选择的主元恰好是待排数组中的极值时,那就是最坏的情况,如果要避免这种情况的发生,那就是要选择合适的主元。我们可以在待排数组取左,中,右3个数,取其中位数作为主元。这样就可以在一定程度上避免最坏情况。

3. 重复的元素不必排序
当数组中存在大量的重复元素时,如果我们用上面所实现的快排,时间复杂度还是要O(nlgn),这开销是在太大相对于插入排序来说。这时我们可以采用三向切分来实现快排。如下所示:

            left part           center part                   right part
        * +--------------------------------------------------------------+
        * |  < pivot   |          ==pivot         |    ?    |  > pivot  |
        * +--------------------------------------------------------------+
        *              ^                          ^         ^
        *              |                          |         |
        *              lt                         i        gt

通过维持三个指针来控制[left, lt )小于主元(pivot),[lt, i)等于主元,[i, gt]未知,(gt, right]大于主元。
一开始,lt指向主元的位置leftgt指向right,而ileft右边接下来的第一个索引开始遍历,每当遇到一个数,就判断它与主元之间的大小关系,有三种情况

  • 小于主元就把这个数与lt指向的数交换,然后lt,i都自增1,然后继续遍历
  • 大于主元就把这个数与gt指向的数交换,gt自减1,此时i还得不能自增,因为它不知道gt用一个什么样的元素跟它交换,所以留到下一次循环判断交换过来的这个元素的去留
  • 等于主元就不用跟谁进行交换,直接自增1就可以

三向切分快速排序如下:

public class Quick {

    //获取中位数
    private static int getMedian(Comparable[] a, int i, int j, int k){
        return a[i].compareTo(a[j]) > 0
                ? (a[i].compareTo(a[k]) < 0 ? i : a[j].compareTo(a[k]) > 0 ? j : k)
                : (a[i].compareTo(a[k]) > 0 ? i : a[j].compareTo(a[k]) < 0 ? j : k);
    }

    private static void swap(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

  //插入排序
    private static void insertSort(Comparable[] a, int left, int right) {
        for (int i = left; i <= right; ++i) {
            int j;
            Comparable value = a[i];
            for (j = i - 1; j >= left && value.compareTo(a[j]) < 0; --j)
                a[j + 1] = a[j];
            a[j + 1] = value;
        }
    }

    private static void sort(Comparable[] a, int left, int right){
        if (right - left < 15) {
            insertSort(a, left, right);
            return;
        }
        swap(a, getMedian(a, left, (left + right) / 2, right), left);
        Comparable v = a[left];
        int lt = left, i = left + 1, gt = right;

        while (i <= gt){
            int cmp = a[i].compareTo(v);
            if (cmp < 0)
                swap(a, lt++, i++);
            else if (cmp > 0)
                swap(a, i, gt--);
            else
                i++;
        }

        sort(a, left, lt - 1);
        sort(a, gt + 1, right);
    }
  
   public static void sort(Comparable[] a){
        sort(a, 0, a.length - 1);
    }

//测试
    public static void main(String[] args) {
        int size = 10000000;
        Integer[] a = new Integer[size];
        for (int i = 0; i < 10000000; ++i)
            a[i] = 88;
        sort(a);  
    }
}

5. 注意:

目前所实现的三向切分并不完美,虽然它解决了大量重复元素的不必要排序,将排序时间从线性对数级别降到线性级别,但它在数组元素重复不多的情况下,它的交换次数比标准的二分法多很多。不过在90年代J.BentlyD.Mcllroy找到一个聪明的办法解决了这个问题。接下来的快速三向切分就是解决办法。

快速的三向切分

            *   left part         center part                  right part
            * +----------------------------------------------------------+
            * | == pivot |  < pivot  |    ?    |  > pivot    | == pivot |
            * +----------------------------------------------------------+
            *            ^           ^         ^             ^
            *            |           |         |             |  
            *            p           i         j             q

在这个算法中,[p, i)里面的元素小于主元,(j, q]里面的元素大于主元,而左右两端[left, p)(q, right]等于主元。在算法一开始,pi都指向left后面的第一个元素, jq都指向right,先把i从左到右遍历时每遇到一个元素都会有三种情况:

  • 等于主元,这时只要与p指向的元素交换然后各自自增1即可
  • 小于主元,这就是指针pi所要维护的元素,直接把i自增1跳过就可以
  • 大于主元,这时就是jq所要维护的元素,先退出循环等待与他们交换

同理,对于jright向左遍历也是一样。当 i > j 时,切分也就结束,最后还要把数组调整为左边小右边大,中间等于主元的形式,再依次排序左边和右边。在这个算法中,既解决了重复元素排序的问题,又解决了少量元素重复时,交换次数过多的问题。接下来是我的实现,不过我觉得我有些地方实现的不太好,凑合着用吧。

快速的三向切分的实现

public class Quick3WayPartitionSort {
    //获取中位数
    private static int getMedian(Comparable[] a, int i, int j, int k){
        return a[i].compareTo(a[j]) > 0
                ? (a[i].compareTo(a[k]) < 0 ? i : a[j].compareTo(a[k]) > 0 ? j : k)
                : (a[i].compareTo(a[k]) > 0 ? i : a[j].compareTo(a[k]) < 0 ? j : k);
    }

    private static void swap(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void insertSort(Comparable[] a, int left, int right) {
        for (int i = left; i <= right; ++i) {
            int j;
            Comparable value = a[i];
            for (j = i - 1; j >= left && value.compareTo(a[j]) < 0; --j)
                a[j + 1] = a[j];
            a[j + 1] = value;
        }
    }
    
    //调整数组
    private static void adjust(Comparable[] a, int start, int end, int toStart){
        for (int i = start; i <= end; ++i)
            swap(a, i, toStart++);
    }

    public static void sort(Comparable[] a){
        temps = new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int left, int right){
        if (right - left < 10) {
            insertSort(a, left, right);
            return;
        }
        swap(a, getMedian(a, left, (left + right) / 2, right), left);
        Comparable v = a[left];
        int p = left + 1, i = p, j = right, q = j;

        while (true){
            while (i <= j){
                int cmp = a[i].compareTo(v);
                if (cmp == 0)
                    swap(a, i++, p++);
                else if (cmp < 0)
                    i++;
                else
                    break;
            }

            while (i <= j){
                int cmp = a[j].compareTo(v);
                if (cmp == 0)
                    swap(a, j--, q--);
                else if (cmp > 0)
                    j--;
                else
                    break;
            }

            if (i < j)
                swap(a, i++, j--);
            else
                break;
        }

        if (p - left > i - p)
            adjust(a, p, i - 1, left);
        else
            adjust(a, left, p - 1, left + i - p);

        if (right - q > q - j)
            adjust(a, j + 1, q, right - q + j);
        else
            adjust(a, q + 1, right, j + 1);

        sort(a, left, left + i - p - 1);
        sort(a, right + j - q - 1, right);
        }


    public static void main(String[] args) {
        
    }
}

6. 最后

快速排序不是稳定的排序算法,所谓稳定就是当待排数组中存在重复元素的时候,排序后重复元素的相对顺序不会改变。在多关键字排序时,稳定的排序算法就很有用处。比如当一个学生按照学号先排序,然后再根据成绩进行排序,因为成绩存在重复的值,此时稳定的排序算法就会导致排序后具有相同成绩的学生按照学号排序,不会混乱。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,968评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,601评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,220评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,416评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,425评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,144评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,432评论 3 401
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,088评论 0 261
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,586评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,028评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,137评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,783评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,343评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,333评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,559评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,595评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,901评论 2 345

推荐阅读更多精彩内容