C++实现各种排序以及快速排序的优化

注:本文中的代码为了适用于各种数据类型,都使用了模板。注意若应用于自定义的类,需要自行重载>运算符。
首先,编写一些辅助函数,用来简化一些操作。包括交换数组中两个元素的位置,比较两个元素的大小。

下面是三种基本的排序:插入排序,冒泡排序和选择排序。这三种排序算法在最坏情况下的时间复杂度都是n^2,但是值得注意的是,插入排序在待排序列“接近有序”的情况下其时间复杂度可以达到n,所以经常用来对一些高级算法进行优化。希尔排序也是针对这一点对其进行了改良的产物。

接下来,就是快速排序。就像它的名字一样,平均情况下,快速排序的时间复杂度可以达到nlogn的级别。快速排序主要采用的是分治的思想,首先寻找一个”尽量“位于排序后序列中间的”支点”(称为一次“划分”),这样,整个序列就被支点分成了两个子序列,将这两个子序列通过交换的方式进行调整,使得位于支点左边的数都小于支点,支点右边的数都大于等于支点,不断递归这个操作,就可以将整个序列进行排序了。
不难看出,影响快速排序效率的关键就在于支点的选择,在最坏情况下,即每次划分得到的支点都恰好是最大值或最小值,则快速排序的时间复杂度会退化为n^2。在最简单的实现中,直接取乱序列中位于中间的值为支点。
在进一步的优化中,可以取乱序列中位于开头、中间、尾端的三个值进行比较,选取这三个值的中间值作为支点。另外,就像上文所提到的,因为插入排序在序列接近有序的时候效率很高,所以可以在划分到每个子序列中元素的个数小于某个值的时候使用插入排序代替之后操作。最后,由于函数调用的开销较大,可以使用栈来模拟函数调用。这三种优化方法也可以结合使用。

吃桔子的攻城狮

修炼ing……

发表评论