元素排序(6)——重头戏:快速排序

2016-05-10   |     |     |  

本系列文章主要介绍常用的算法和数据结构的知识,记录的是《Algorithms I/II》课程的内容,采用的是“算法(第4版)”这本红宝书作为学习教材的,语言是java。这本书的名气我不用多说吧?豆瓣评分9.4,我自己也认为是极好的学习算法的书籍。
通过这系列文章,可以加深对数据结构和基本算法的理解(个人认为比学校讲的清晰多了),并加深对java的理解

1.快速排序介绍

快速排序是20世纪Top10算法之一。足以看出它的重要性。并且它不需要额外的空间,这是它比MergeSort厉害的地方。

1.1 基本步骤

  • 随机对数组进行洗牌操作(重要,直接影响性能),参考洗牌算法
  • 对数组进行分组,保证对于元素a[i]
    • a[i]左边的元素全都小于a[i]
    • a[i]右边的元素全都大于a[i]
  • 对子数组循环操作,只到完全有序

2.1 划分操作

  • i从左到右扫描直到发现一个a[i] > a[lo]
  • j从右到左扫描,直到发现一个a[j] < a[lo]
  • 然后交换a[i]和a[j]

image-20190302124030890

  • 直到i和j交叉
  • 交换a[lo]和a[j]

private static int partition(Comparable[] a, int lo, int hi)
{
    int i = lo, j = hi;
    while(true)
    {
        while(less(a[++i],a[lo]) && i < hi)
            if(i == hi)    break;
        while(less(a[lo],a[--j]))
            if(j == lo)    break;  //可以省略
        if(i > j)
            break;
        exch(a,i,j);
    }
    exch(a,lo,j);
    return j;
}

注意这里的代码看上去很简单,但是实际上很多trick

  • 第一是在if(j == lo)那里 判断可以省略,因为a[lo]不可能小于本身
  • 第二个是把循环的退出条件写在循环内部

下面是我一开始写的代码。这里明显有一个问题,就是当j < i之后,这里应该立马退出循环,不然exch发生后,就出bug了。

while(i < j)
{
        while(less(a[i],a[lo]) && i < hi)
            i++;
        while(less(a[lo],a[j]))  //这里不用做边界判断因为a[lo]不会小于本身
            j--;
        exch(a[i],a[j]);
  }

然后是完整的快排算法:

public class Quick
{
  private static int partition(Comparable[] a, int lo, int hi)
  {
/* see previous slide */
  }
  public static void sort(Comparable[] a)
  {
      StdRandom.shuffle(a);  //Important
      sort(a, 0, a.length - 1);
  }
  private static 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);
  }
}

注意:算法开始的随机洗牌是非常重要的,可以保证算法性能最佳(很多算法书中都没提这一点)

1.3 快排性能分析

  • 平均比较次数 CN=(N+1)+(C0+CN−1N)+(C1+CN−2N)+…+(CN−1+C0N)

其中N2
表示划分概率,C0=C1=0

(下面的计算大家看看就行了,不用推……)

计算得出来CN=1.39NlgN

实际是比MergeSort的平均比较次数多39%的,但是,快排依然快于Mergesort,因为他很多时候都是比较,但是Mergesort每一次比较都移动了元素,浪费了时间。

注意:快排的代码很容易写错,而且目前很多工具书或者网上的代码都是O(N2)的性能:

  • 当数组有序或逆序的时候(没随机洗牌)
  • 如果有很多重复键的时候(即使很随机)

1.4 快排的特性

  • 快排是就地排序算法(没有额外空间费用)
  • 快排是不稳定算法

1.5 快排改进

1.5.1 用插入排序提高在小数组中排序性能

即使是快排,在小数组的时候,开销也是很大的,依然可以用MergeSort中的改进方案,在小数组的时候,采用InsertionSort来提高排序速度。通常取10个元素

1.5.2 选择支点(pivot)

通常pivot我们选的是数组的第一个元素,但是理论上最好的piovt是刚好中间的元素,这样可以将数组二分(但是实际上对与大数据量来说,不值得在这里开销),所以一般采用 Median-of-3

2 快速选择算法

快速选择算法的目标就是给定一组数,找其中大的元素,这个在实际生活中运用广泛,比如

2.1首先可以估计下这个算法的大致性能

  • 性能上界:NlgN,这个很容易想到,只要排序好,取第几个元素都是简单的
  • 性能下界:N 至少要循环一遍

所以问题就在于能不能找到一个算法是线性时间的。

2.2 快速选择算法

快速选择算法用了快排的划分思想。

  • 首先找个元素作为pivot
  • 然后使得它左边元素全小于它
  • 右边元素全大于它
  • 然后对其中一个划分继续找(取决于j是第几个元素),直到j = k

image-20190302124443910

2.3 快速选择算法性能分析

快速选择算法是线性的

首先,如果每次划分的刚好是差不多一半的话,比较次数是线性的。如果每次不是一般的话,可以通过等概率求出来,也是平均线性的

3.重复值问题

快速排序有个问题,就是当它遇到重复键值的时候,性能会退化到,MergeSort没这个问题,这个问题直到1990年c的标准库中的qsort使用的快排都还有这个缺陷,而且基本所有工具书中的实现都有这个问题。

3.1 问题出现原因

把所有相等的元素都放在一边了,这样,当数组中有很多重复元素的时候,划分算法基本就失灵了。

我们的代码解决方案是不管i和j只要碰到了相同元素就停下来(为什么?还记得我们代码里面全是用的less吗?相等的话不就不满足了嘛)这样基本可以保证哪怕在重复值很多的情况下,也基本是对半划分。

能不能有一个理想的算法,把所有相同的元素直接放一起呢?

3.2 三路划分

思想很简单,原来是划分成两个部分,现在改成三个部分了,是不是很像荷兰国旗? 直到1990年中叶,传统观点都认为荷兰国旗问题不值得去做,不过现在的c的qsort和java的sort都加入了这种改进

三路划分的步骤比传统的快排划分会稍微麻烦一点点,它多了2个变量lt和gt,用来维持中间的边界。

  • 元素大于gt边界的,都是大于V的值,
  • 元素小于lt边界的,都是小于V的值
  • 元素在lt和gt中间的,都是等于V的值

3.2.1算法步骤

  • 设v = a[lo]
  • i 从左到右扫描,遇到hi停止
    • 当a[i] < v 时,交换a[i]和a[lo],然后lo和i同时+1 (放左边,lo还是指向v)
    • 当a[i] > v 时,交换a[i]和a[hi],然后hi-1 (放右边,lo还是指向v,i不动,因为这个时候i指向的元素变了,还要判断呢)
    • 当a[i] = v 时,i+1 (拉大i和lt的距离,扩大lt和hi的空间)

3.2.2代码

你可以发现其实这个代码很精巧

private static 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);
}

3.3.3 三路划分的快排性能

总而言之一句话,它在实际应用中性能很棒,效率很高,是熵最优的。

系统排序

排序在实际的应用中十分广泛

java中使用的主要是快排处理基础类型mergesort处理对象类型

我们之前说过了,快排有一定的缺陷,所以有人花了大功夫改进了快排算法,也是现在C,C++, java中广泛使用的

但是尽管这样,快排还是有缺陷

目前在不同领域有不同的适用的算法

但是没有一种算法能覆盖所有应用,也许快排在大多数排序应用中都是很好的选择,但是它毕竟是不稳定的,而且在一些特殊情况下,性能不会特别好,还可能会出现一些致命的错误。

所以要学会去评价一个算法的优劣和是否适合自己的应用,以及如何能够改进算法使得它更好的适应自己的应用。