算法系统学习首篇之排序
排序在商业数据处理和现代科学计算中的重要性不言而喻。它能够应用于日常事物处理、组合优化、天体物理学、分子动力学、语言学、基因组学、天气预报和其他相关领域。 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.请按任意键继续. . .
初级排序结束。
领取专属 10元无门槛券
私享最新 技术干货