首页 > 代码库 > 普林斯顿大学算法课 Algorithm Part I Week 3 快速排序 Quicksort

普林斯顿大学算法课 Algorithm Part I Week 3 快速排序 Quicksort

发明者:Sir Charles Antony Richard Hoare

基本思想:

  • 先对数据进行洗牌(Shuffle the array)
  • 以数据a[j]为中心进行分区(Partition),使得a[j]左侧的数据都小于等于a[j],a[j]右侧的数据都大于等于a[j]

  • 分区完后递归排序

 

演示(Quicksort partitioning demo)

重复操作指导i和j指针相遇

  • 当a[i] < a[lo]时,令i从左往右扫描
  • 当a[j] > a[lo]时,令j从右往左扫描
  • 交换a[i]和a[j]

当指针相遇时

  • 交换a[lo]和a[j] 

Java实现

public class Quick{    private static int partition(Comparable[] a, int lo, int hi)    {        int i = lo, j = hi + 1;        while (true)        {            while (less(a[++i], a[lo]))                if (i == hi) break;           // 从左向右找到不小于a[lo]的元素            while (less(a[lo], a[--j]))                if (j == lo) break;           // 从右向左找到不大于a[lo]的元素            if (i >= j) break;                // 指针相遇            exch(a, i , j);                   // 交换        }        exch(a, lo, j);                       // 和比较元素交换         return j;                             // 返回比较元素所在的下标    }        public static void sort(Comparable[] a)    {        StdRandom.shuffle(a);                 // 先对数组进行洗牌,复杂度是N        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);    }}

 实现细节(implementation details)

  • 原地分区(Partitioning in-place):不用开辟额外的辅助数组
  • 终止循环:检查两个指针是否相遇
  • 边界:(j == lo)的检查是多余的,但(i == hi)的检查是必要的
  • 保留随机性(Preserving randomness):需要洗牌(Shuffling)来保证运动(Performance guarantee)
  • 相同的值(Equal keys):当存在重复的元素,最好将指针停在和比较元素相同的位置上(When duplicates are present, it is (counter-intuitively) better to stop on keys equal to the partitioning item‘s key.)

复杂度平均情况分析(average-case analysis):平均复杂度为 1.39NlgN,比归并排序还快

运行特征(Performance characteristic)

  • 最坏情况(Worst case):1/2*N^2
    • 几乎不会出现
  • 平均情况(Average case):比较次数约等于1.39NlgN
    • 比归并排序多出39%的比较次数
    • 但是由于更少的数据交换,实际中比归并排序更快
  • 随机洗牌(Random shuffle):  
    • 对最坏情况的概率性保证(Probabilistic guarantee)
    • 经过实验验证的数学模型的基础(Basic for math model that can be validated with experiments.)
  • 留心:出现以下情况时,运算是平方级的(quadratic)
    • 当数组逆序排列
    • 当存在多个重复元素   

特性(Properties):

  • 快速排序是一种原地排序算法(in-place sorting algorithm)
  • 不具有稳定性

实践上的改善(practical improvements)

改善1:使用插入排序对小的子序列进行排序

  • 即使是快速排序,也对小数组有不少的开销
  • 当数组大小达到10时,停止(Cutoff)插入排序
  • 大概有20%的改善
private static void sort(Comparable[] a, int lo, int hi){    if (hi <= lo + CUFOFF -1)    {        Insertion.sort(a, lo, hi);        return;    }    int j = partition(a, lo, hi);    sort(a, lo, j-1);    sort(a, j+1, hi);}

 

改善2:使用平均数作为比较元素

  • 最好的选择是比较元素刚好是中值
  • 通过取样估计中值(Estimate true median by taking median of sample.)
  • 对三个取样元素取平均值
  • 大概有10%的改善
private static void sort(Comparable[] a, int lo, int hi){    if (hi <= lo) return;        int m = medianOF3(a, lo, lo + (hi - lo)/2, hi);    swap(a, lo, m);        int j = partition(a, lo, hi);    sort(a, lo, j-1);    sort(a, j+1, hi);}

 

普林斯顿大学算法课 Algorithm Part I Week 3 快速排序 Quicksort