说明：该系列博客整理自《算法导论(原书第二版)》，但更偏重于实用，所以晦涩偏理论的内容未整理，请见谅。另外本人能力有限，如有问题，恳请指正！
在第一部分--第2章中，介绍了两种对n个实数进行排序的算法。插入排序 的最坏情况运行时间为Θ ( n2)，但其算法的内循环是紧密的，对小规模输入来说是一个快速的原地排序算法(在排序输入数组时，只有常数个元素被存放到数组以外的空间中去)。合并排序 有着较好的渐近运行时间Θ( nlgn)，但其中的MERGE程序不在原地操作。
在本部分中我们要介绍另外两种对任意实数进行排序的方法：第6章的堆排序、第7章的快速排序。
第6章介绍堆排序，它可以在Θ( nlgn)时间内对n个数进行原地排序。这种算法用到一种重要的称为堆的数据结构，还要用它实现优先级队列。
第7章介绍快速排序，他是另一种对n个数进行原地排序的算法，但是它的最坏情况运行时间为Θ( n2)。它的平均运行时间是Θ( nlgn)，在实际中常常优于堆排序算法。就像插入排序算法一样，快速排序的代码也比较紧凑，所以它的运行时间中隐含的常数因子就很小。对于大输入数组的排序来说，这是一个很常用的算法。
通过第8章的决策树模型，证明了任何对n个输入进行排序的比较排序算法，其最坏情况运行时间的下界为Ω ( nlgn)，说明合并排序和堆排序都是渐近最优的比较排序算法。
第8章，介绍非比较类排序算法，其运行时间可以突破Ω ( nlgn)的下界，不过计数排序、基数排序、桶排序都有使用的前提条件。例如，计数排序算法假定输入数取自集合{0,1,2,...,k}。通过利用数组下标来确定元素的相对次序，该算法可以在Θ( k+n)时间内完成对n个数的排序，这样当k=O(n)时，计数排序的运行时间就与输入数组的规模呈线性关系。基数排序算法可以用来扩大计数排序的使用范围。如果有n个整数要排序，每个整数都有d位，且每位都可以取到k个可能值，则基数排序就可以在Θ(d* (k+n))时间内完成排序。当d是个常数，k=O(n)时，基数排序就以线性时间运行。桶排序要求了解各个数在输入数组中的概率分布，如果是绝对的均匀分布，则桶排序的效果最好。它可以对均匀分布在半开区间[0,1)上的n个实数以平均情况时间O(n)进行排序。
第9章，中位数和顺序统计学。在一个由n个数构成的集合上，第i个顺序统计是集合中第i小的数。如果未学过本章，我们可能先排序，再查找，采用比较类排序的话，其时间复杂度为Θ( nlgn)，采用非比较排序的话，其时间复杂度为Θ(n)。在本章中读者将会看到，即使输入数组中的各元素为任意实数，我们仍能在Θ(n)时间内找到第i小元素。我们将给出一个算法，伪代码很紧凑，最坏情况运行时间为Θ( n2)，但平均情况下为线性时间。另外，还将给出一个更复杂的算法，其最坏情况运行时间为Θ( n)。
本部分需要的数学背景知识说明：对快速排序、桶排序和顺序统计量算法进行平均情况分析时，用到了概率论方面的知识(相关内容可参见附录C和第5章中的概率分析和随机算法的材料)。顺序统计学的最坏情况线性时间算法的分析，包含了比本部分其他最坏情况分析更复杂的数学内容。
排序分类
1、比较排序
1）、插入排序：原地对任意实数进行排序
2）、合并排序：非原地对任意实数进行排序
3）、堆排序：非原地对任意实数进行排序。以堆排序为基础，还了解了优先级队列。
4）、快速排序：原地对任意实数进行排序
2、非比较排序
1）、计数排序
2）、基数排序
3）、桶排序
3、中位数和顺序统计
1）、中位数和顺序统计
2）、动态顺序统计
网友评论