博主之前刷过一遍《算法导论》(Introduction to Algorithms),但是看得多写得少,于是最近抽空动手写写下里面的算法。排序是经典问题了,于是决定将书中的排序算法一一使用C++实现。这篇博客一方面是对排序算法本身的总结(这个书上都有啦),另一方面是博主在使用C++实现算法时的一些体会,更多的是算法细节,希望有助于加深对算法的理解的。

排序算法总结

排序算法,介绍算法导论中的七种算法,它们的时间复杂度和空间复杂度如下表。插入排序代表了最坏的情况,归并排序,堆排序,快速排序基本都到达了使用内存排序算法的时间下界\(n\lg (n)\),而后面三种排序,是使用了内存寻址的方式,实现了线性时间排序,桶排序是较为一般的方法,而基数排序和计数排序则需要被排序数字为整数。具体的实现推荐参考算法导论,这篇博客主要提供代码解释。

算法最坏运行时间期望运行时间稳定性
插入排序theta(n^2)theta(n^2)稳定
归并排序theta(nlg(n))theta(nlg(n))稳定
堆排序O(nlg(n))-不稳定
快速排序theta(n^2)theta(nlg(n))不稳定
计数排序theta(k+n)theta(k+n)
基数排序theta(d(n+k))theta(d(n+k))
桶排序theta(n^2)theta(n)

插入排序归并排序冒泡排序鸡尾酒排序:冒牌排序改进
希尔排序选择排序堆排序快速排序

上面的gif摘自另一篇总结排序算法的博客。再简单介绍两种本博客不详细给出代码的算法。

鸡尾酒排序

鸡尾酒排序也叫作定向冒泡排序,与冒泡排序不同之处在于从低到高然后从高到低的比较每个元素,稍微提高了冒泡排序的性能。

希尔排序

希尔排序是插入排序的改进版本,但是希尔排序是不稳定的排序算法。改进之处在于将比较的全部元素分为几个区域来提升排序的性能。这样可以让一个元素一次性朝最终位置前进一大步,然后算法在取越来越小的步长进行排序,最后一步就是普通的插入排序。


插入排序

插入排序的核心就是维持一个循环不变式,在循环不变式内部的数组是已经排好序的,我们把后面的数组一个个的加进来。

 


归并排序

归并排序采用了分解、解决、合并的分治策略。最重要的是合并步骤,也就是下面的merge函数,在merge中需要使用额外的内存,这是归并排序的不足。


堆排序

堆排序算法通过一个大(小)顶堆的性质来实现排序。大顶堆的性质是父亲比儿子们都要大,所以第一个元素总是最大的,在排序时不断将最大的元素提取出来,提取出来的元素就形成了排序后的数组。

此外,堆排序算法还可以形成一个优先队列,参考算法导论。


快速排序

快速排序也是通过分治策略来实现的排序,每次将一个元素排到正确位置。快速排序是原址排序,所以合并过程省略了,原址排序也是快速排序最大的优势。

此外,下面还贴出了针对相同元素的快速排序算法。相当于原快速排序是二指针问题,因为增加了一个区间,所以变成了三指针问题。


基数排序

基数排序虽然贴着线性时间的标签,但是常数项还是比较大的,就是通过对每个位进行一次稳定排序,来实现整体的排序。下面的代码中使用的是最低有效位的方式进行排序。


计数排序&桶排序

这个就不多讲了,计数排序直接将数组下标作为地址,而计数排序就可以看做桶大小为1的桶排序。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注