排序和顺序统计量
这一部分介绍了几种解决如下排序问题的算法。
输入：一个n个数的序列<a1, a2, . . . . An>
输出: 输入序列的一个排列(重排) <a1’, a2’, .... An’> , 使得a1’ < a2’ < ... < an’
输入序列通常是一个n元数组,尽管它可以用链表等其他方式描述.

数据结构:
在实际中, 待排序的数很少是单独的数值, 他们通常是称为记录(record)的数据集的一部分.每个记录包含一个关键字(key),就是排序问题中要重排的值.记录的剩余部分由卫星数据(satelite data)组成,通常与关键字是一同存取的.在实际中,当一个排序算法重排关键字时, 也必须要重排卫星数据.如果每个记录包含大量的卫星数据, 我们通常重排记录指针的数组,二不是记录本身,这样可以降低数据的移动量.
在某种意义上,正是这些实现细节将一个算法与成熟的程序区分开来.一个排序算法描述确定有序次序的方法(method), 而不管我们是在排序单独的数还是包含很多卫星数据的大记录.因此,当面对排序问题时, 我们通常假定输入只是由数组成.将一个对数进行排序的算法转换成一个对记录进行排序的程序在概念上是很直接的.当然在具体的工作情景下,其他一些细节问题可能会使实际的编程工作遇到很多挑战.
为什么要排序
很多计算机科学家认为排序是算法研究中最基础的问题.其原因有很多
有时应用本身就需要对信息进行排序.
很多算法通常把排序作为关键子程序..例如在一个渲染图形对象的程序中,图形对象是分层叠在一起的,这个程序可能就需要按上层关系来排序对象.一遍能按自底向上的次序绘制对象..
插入排序由于内层循环非常紧凑,对于小规模输入,插入排序是一种非常快的原址排序算法.(回忆一下,如果输入数组中仅有常数个元素需要在排序过程中存储在数组之外,则称排序算法是原址的(in place)))
插入排序，归并排序，堆排序以及快速排序都是比较排序算法：他们都是通过对元素进行比较操作来确定输入数组的有序次序
堆排序不同归并排序的是，堆排序同样具有控件原址性:任何时候都只需要常数个额外的元素空间存储临时数据
对应堆排序，给定一个结点的下标i， 我们很容易计算得到它的上节点，左结点和右结点的下标。
任意i， parent： return i/2Left ： return 2*i Right：return 2*i+1；
MAX-HEAPIFY（A， i）
l = LEFT(i)
R = RIGHT(i)
If l <= A.heap.size and A[i] > A[l]
Largest = l;
Else largest = i;
If r <= A.heap.size and A[r] > A[largest]
Largest = r;
If largest ≠ i
Exchange A[i] with A[largest]
MAX-HEAPIFY(A, largest);
MAX-HEAPIFY的执行过程即是：自顶向下的对无序堆进行调整。在程序的每一步中，从A[i]、A[LEFT], A[Right]中选出最大的，并将其下标存储在largest中。如果A[i]是最大的，那么以i为节点的子树已经是最大值，程序结束。否则，最大元素是i的某个子节点，则交换A[i]和A[largest]的值。从而使i以及子节点满足最大堆的性质，在交换后，下标为largest结点的值是原来的A[i], 于是以该点为根的子树又有可能会违反最大堆的性质，因此，需要对该子树递归调用MAX-HEAPIFY.
对于一颗以i为根节点，大小为n的子树，MAX-HEAPIFY的时间代价包括：调整A[i]和A[left(i)], A[Right(i)]的关系的时间代价o（1），加上在一颗以i的一个孩子为根节点的子树上运行MAX-HEAPIFY的时间代价，这里假设递归调用会发生。
建堆：
我们可以用自底向上的方法利用过程MAX-HEAPIFY把一个大小为n = A,length的数组A[1..n]转换为最大堆。通过基础可以知道，子数组A([n/2+1]... n)中的元素都是树的叶结点。每个叶结点都可以看作只包含一个元素的堆。过程BULID-MAX-HEAP对树中的其他节点都调用一次MAX-HEAPIFY。
BUILD-MAX-HEAP(A)
A.heap.size = A.length
For i = [A.length/2] downto 1
MAX-HEAPIFY(A, i)\\
类似的，我们也可以通过调用BUILD-MIN-HEAP构造一个最小堆。除了第三行的调用替换为MIN-HEAPIFY外，其他不变。
堆排序算法
初始时候，堆排序算法利用BUILD-MAX-HEAP将输入数组A[1....n]建成最大堆，其中n = A.length。因为数组中的最大元素总在根节点A[1]中， 通过把它与A[n]进行互换，我们可以让该元素放到正确的位置。这时候，如果我们从堆中去掉节点n（这一个操作可以通过减少A.heap.size的值来实现), 剩余的节点中，原来根的孩子节点仍然是最大堆，而新的根节点可能会违背最大堆的性质。为了维护最大堆的性质，我们要做的是调用MAX-HEAPIFY（A，1），从而在A[1......n-1]上构造一个新的最大堆。堆排序算法会不断重复这一个过程，直到堆的大小从n-1降到2.
HEAPSORT（A）
BUILD-MAX-HEAP（A）
For i = A.length downto 2
Exchange A[1] with A[i]
A.heap.size = A.heap.size - 1
MAX-HEAPIFY(A, 1)
堆排序算法大致流程： 构建最大堆， 逐渐减小堆大小并取出最大元素并同时维护最大堆

快速排序的描述
与归并排序一样，快速排序也使用了分治思想。下面是对一个典型的子数组A[p....r]进行快速排序的三步分治过程：
分解：数组A[p..r]被划分为两个（可能为空）子数组A[p...q-1]和A[q+1.....r]， 使得A[p....q-1]中的每一个元素都小于等于A[q]，而A[q]也小于等于A[q+1....r]中的每个元素。其中，计算下标q也是划分过程的一部分。
解决：通过递归调用快速排序，对子数组A[p...q-1]和A[q+1.....r]进行排序。
合并：因为子数组是原址排序的，所以不需要合并操作；数组A[p....r]已经有序。
下面程序实现快速排序：
QUICKSORT(A，p， r）
If p < r
Q = PARTITION(A, p, r)
QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)
为了排序一个数组A的全部元素，初始调用时QUICKSORT（A， 1， A.length）
数组的划分
算法的关键是PARTITION部分， 它实现了对子数组A[p....r]的原址重排。
PARTITION(A, p, r)
X = A[r]
I = p - 1
For j = p to r - 1
If A[j] <= x
I = i + 1;
Exchange A[i] with A[j]
Exchange A[i+1] with A[r]
Return i + 1
在此段算法中，i相当于一个指向小于等于A[r]尾端的一个指针(用下标i来表示）。同时，以A[r]作为划分，将所有小于等于A[r]的移向左边， 大于A[r]的移向右边，并且返回尾端指针。
PARTITION显示了如何在数组上进行操作的过程。
PARTITION总是选择一个x = A[r]作为主元(pivot element)，并围绕它来划分子数组A[p...r]，随着程序的执行，数组被划分为4个（可能有空的）区域。在第3-6行的每一轮迭代开始，每一个区域都满足一定 的性质。我们将这些性质作为循环不变量：
在第3-6行循环体的每一轮迭代开始，对于任意数组下标k，有：
1：若p <= k <= i, 则 A[k] <= x.
2：若i+1 <= k <= j - 1 ， 则 A[K] > x
3: 若k = r, 则 A[k] = x
在一个样例数组上的PARTITION操作过程。对于4个部分的解析
第一部分： 其值都不大于x。
第二部分：其值都大于x。
第三部分：未分入这两个部分中的任意一个。
最后一个部分：主元x。
即在子数组A[p...r]上， PARTITION维护了4个区域, A[p....i]区间内的所有值都小于等于x, A[i+1......j-1]区间内的所有值都大于x, A[r] = x， 子数组A[j....r-1]中的值则可能属于任意一种情况。

这类算法都有个有趣的性质，在排序的最终结果中，各个元素的次序依赖于他们之间的比较，我们把这类排序称为比较排序。
决策树模型
比较排序可以抽象为一颗决策树。决策树是一颗完全二叉树，它可以表示在给定输入规模情况下，某一特定排序算法对所有元素的比较操作情况下，某一特定排序算法对所有元素的比较操作。其中，控制，数据移动等其他操作都被忽略了。
最坏情况下的下界
在决策树中，从根节点到任意一个可达叶结点之间最长的简单路径的长度，表示的是对应排序算法中最坏情况下的比较次数。因此，一个排序算法中最坏的情况下的比较次数就等于决策树的高度。因此，在最坏情况下，任何比较排序算法都需要做nlgn次比较。

计数排序
计数排序假设n个输入元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。
计数排序的基本思想是：对每个输入元素x，确定小于x的元素个数，利用这一个信息，可以直接把x放到数组中的位置上了。例如，如果有17个元素小于x， 则x就应该在第18个输出位置上，当有几个元素相同时，这一方案就要略作修改。因为不能把他们放在同一个位置上。
在计数排序算法的代码中，假设输入是一个数组A[1....n]。 A.length = n, 我们还需要两个数组：B[1.....n]存放排序的输出， C[0...k]存放临时存储的空间
COUNTING-SORT(A,B, k）
Let C[0....k] be a new array
For i = 0 to k
C[i] = 0
For j = 1 to A.length
C[A[j]] = C[A[j]] + 1
For i = 1 to k
C[i] = C[i] + C[i+1]
For j = A.length downto 1
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] - 1
图示计数排序的运行过程，在第2-3行for循环的初始化操作之后，数组C的值全部被置为0； 第4-5行的for循环遍历每一个输入元素。如果一个输入元素的值为i，就将C[i]值加1.于是，在第5行执行完后，C[i]中保存的就是等于i的元素的个数，其中i = 0,1,2.....k.
第7,8行通过加总计算确定对每一个i = 0, 1....k,有多少输入元素是小于或者等于i的。
最后，在第10-12行的for循环部分，把每个元素A[j]放到它在输出数组B中的正确位置上。如果所有n个元素都是互异的，那么当第一次执行第10行时，对每一个A[j]来说，C[A[j]] 就是A[j]在输出数组中的最终正确位置。这是因为共有C[A[j]]个元素小于或者等于A[j]。因为所有的元素可能并不是都是互异的，所有，我们每将一个值A[j]放入数组B中以后，都要将C[A[j]]的值减一。这样，当遇到下一个值等于A[j]的输入元素（如果存在）时，该元素可以直接被放到输出数组A[j]的前一个位置上。
计数排序的一个重要性质就是它是稳定的：具有相同值的元素在输出数组中的相对次序与它们在输入数组中的相对次序相同。通常，这种稳定性只有当进行排序的数据还附带卫星数据时才比较重要。计数排序的稳定性很重要的另一个原因是：计数排序经常会被用作计数排序算法的一个子过程。我们在下一节中可以看到，为了使基数排序正确运行，计数排序必须是稳定的。

选自《算法导论》

slh