其实就两个函数,一个quickSort,一个partition。当然基础的函数应该是partition()
快速排序-小灰漫画
或者说,“荷兰国旗问题”
课本上说,在有大量重复元素的情况下,用三部分的话,性能会比较好,是熵最优的排序。
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 + 1; 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++; } // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. sort(a, lo, lt-1); sort(a, gt+1, hi); assert isSorted(a, lo, hi); }
课本上的java代码,直接从网站抓的。
补充一下,exch就是交换,和swap一样
assert,断言。当assert后面的bool为真时,继续正常运行;否则报错
配图如下:
还有一个优化的点是,当N比较小的时候,可以切换到插入排序
当 N再大一点,好像还用到了median3来进行优化,没有很看懂。
反正可以直接调API,没有动力写了,落泪。