算法系统学习首篇之排序

算法系统学习首篇之排序

排序在商业数据处理和现代科学计算中的重要性不言而喻。它能够应用于日常事物处理、组合优化、天体物理学、分子动力学、语言学、基因组学、天气预报和其他相关领域。 20世纪科学与工程领域的十大算法之一就是一种排序算法——快速排序。

在标准库中已经实现排序函数，再学习排序算法仍有重要实际意义。再重温排序算法之前，我并没有意识到。

对排序算法的分析将有助于全面理解比较算法性能的方法。

类似的算法思想也能有效解决其他类型问题。

排序算法常常是解决其他问题的第一步。

初级排序（选择排序，冒泡排序，插入排序）

选择排序

这是一种最简单的排序算法： 首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置。其次，在除去第一个元素剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，知道整个数组排序。该方法不断地选择剩余元素中的最小者。

排序算法类模板的基本API接口包括：排序函数sort()，比较函数less(), 交换函数exch(),判断有序性函数isSorted()以及打印输出函数print().

结论： 对于长度为N的数组，选择排序大约需要N^2/2次比较和N次交换。

冒泡排序

不同于选择排序，冒泡排序每次比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。

结论： 对于长度为N的数组，冒泡排序大约需要N^2/2次比较，最坏情况下，同样需要N^2/2次交换。

插入排序

在玩扑克牌的时候，我们一般都是使用的插入排序思想。即将每一张牌插入到其他已经有序的牌中的适当位置。在计算机实现中，为了要给新插入的元素腾出位置，需要将比待插入元素大的其他所有元素都向右移动一位。

结论： 对于随机排列的长度为N的不重复数组，平均情况下插入排序需要~N^2/4次比较以及~N^2/4次的交换。最坏情况下与冒泡法相同。

希尔排序

希尔排序是一种基于插入排序的快速的排序算法。对于大规模的乱序数组插入排序很慢，因为它只会交换相邻的元素。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，最最终用插入排序将局部有序的数组排序。希尔排序的思想是是数组中任意间隔为h的元素都是有序的。这样的数组成为h有序数组。比如说，h=3, 则 0 3 6 ... 3n 等位置的元素是有序的， 1 4 7 ... 3n+1 位置元素是有序的， 2 5 8 ... 3*n+2等位置的元素同样也是有序的。一个h有序数组实际上是有h个有序的子数组组成的数组。希尔排序更高效的原因是它权衡了子数组的规模和有序性。透彻理解希尔排序的性能至今任然是一项挑战。我们先看算法实现，再来讨论。

在这里，1，4，13，40，121，364，1093，.... 称为递增数列。为什么这里选择这样的递增数列？如何选择更好的递增序列？ 回答这个问题并不简单。 有很多论文研究了各种不同的递增序列，但都无法证明某个序列是“最好的”。其不仅取决于h的值，还取决于h之间的数学性质，如公因子等。一般情况下也选择递增数列如 N/2 N/4 N/8 ... 1 ( 逆序排列 )。 在实际应用中，这两种递增数列基本够用。

希尔排序的重要意义是突破了排序算法复杂度为$O(N^2)$的限制，迈出了寻找更高效排序算法的重要一步。

结论： 使用递增数列1，4，13，40，121，364... ( h = 3*h + 1) 的希尔排序所需要的比较次数不会超过N的若干倍乘以递增序列的长度（即while 循环次数）。

算法性能比较

这里给出比较两种算法性能的具体实现，科学方法就是要通过实践来检验真理。理论上的算法效率是否在实际使用中得到确认?

运行结果：

For 10000 random Ints shell cost :826 ms and insert costs :112280 ms.请按任意键继续. . .

初级排序结束。