首页 > 代码库 > 普林斯顿大学算法课 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。