# heapify for i = n/2:1, sink(a,i,n) → invariant: a[1,n] in heap order # sortdown for i = 1:n, swap a[1,n-i+1] sink(a,1,n-i) → invariant: a[n-i+1,n] in final position end # sink from i in a[1..n] function sink(a,i,n): # {lc,rc,mc} = {left,right,max} child index lc = 2*i if lc > n, return # no children rc = lc + 1 mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc if a[i] >= a[mc], return # heap ordered swap a[i,mc] sink(a,mc,n)
堆排序实现起来很简单,执行O(n·lg(n))进行原位排序,但不能稳定下来。
第一循环中,Θ(n) 的“heapify”阶段,会将数组放到堆排列中。第二个循环,O(n·lg(n)) “sortdown”阶段,反复提取的最大值和恢复堆排列。
下沉功能清晰地写入递归。因此,如图所示,将码需要递归调用Θ(lg(n))的堆栈空间。然而,在 sink()时尾部递归很容易转化为迭代,产生的O(1) 空间约束。
这两个阶段是略微自适应的,虽然没有任何特别有用的方式。在接近排序完的情况下,heapify阶段破坏了原来的顺序。在相反的情况下,数组在堆排序开始,heapify阶段能够尽可能的快,但是,然后sortdown阶段是典型。在很少有不同键的情况下,有一定的加速,但并不像在希尔排序或三平均分区快速排序时那样快。
Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.
Programming Pearls by Jon Bentley. Addison Wesley, 1986.
Quicksort is Optimal by Robert Sedgewick and Jon Bentley, Knuthfest, Stanford University, January, 2002.
Dual Pivot Quicksort: Code and Discussion.
Bubble-sort with Hungarian ("Csángó") folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.
Select-sort with Gypsy folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.
Sorting Out Sorting, Ronald M. Baecker with the assistance of David Sherman, 30 minute color sound film, Dynamic Graphics Project, University of Toronto, 1981. Excerpted and reprinted in SIGGRAPH Video Review 7, 1983. Distributed by Morgan Kaufmann, Publishers. Excerpt.