O(n2)排序算法的总结

发布于:2019-05-13   编辑:admin 浏览:

  学习了O(n2)时间复杂度的相关算法,总算是对这些算法的优缺点有了详细的特点。其实对于任何的算法,没有优点和缺点,而是有相应的特点。所以我们应该结合不同的排序环境来选择不同的排序算法,从而达到在实现时间和执行效率上的平衡。这是因为,越是简单的排序算法,实现起来肯定是越容易,而且出现BUG的概率也不会太大。相反,复杂算法可能效率更高,但是出现问题的可能性也会更大。下面,我就结合O(n2)时间复杂度的四个经典排序算法,为您详细讲解这四个算法的特点。

  定义:选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

  分析:通过选择排序的图示和源码我们可以看出来,选择排序要进行两次循环,而且最关键的是内层循环在每一次执行时都是全部执行完的。那我们有没有办法让内层循环不用每次都执行完呢?方法肯定是有的,这就是冒泡排序。

  定义:冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列,一次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素已经排序完成。

  分析:从图示和源码可以看出来,从执行次数上来说,冒泡排序是比选择排序的循环次数更少的。那是不是就可以说,如果待排序的数组中元素比较合适,冒泡排序在时间复杂度上是不是会比选择排序更好呢?真的是这样的吗?

  其实不是的,经过多次测试验证,冒泡排序基本上是比选择排序的时间复杂度要差的,这是为什么呢?从源码中我们可以很明显的看出来,虽然冒泡排序是比选择排序执行次数少了,但是交换的次数明显增多了,而如果你对计算机程序指令的实现原理只要有一个基本的认识,就应该知道交换动作比赋值动作是需要更多指令操作的。所以说,最终冒泡排序大部分情况下,比选择排序的时间复杂度都要高。

  既然交换动作这么消耗资源,那有没有一种方法,即能够减少内层循环的执行次数,又可以减少甚至是无需交换操作呢?这就要请出插入排序了。

  定义:插入排序(InsertionSort)的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,即每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

  分析:从图示和源码可以看出来,插入排序(优化后的)是没有交换操作的,而且对于内层循环来说,如果待排序的元素是比较大的值,那内层循环执行的次数会非常的少。因此,如果原始数据基本上是有序的,那使用插入排序的效率会非常的高。在O(n2)级别的排序算法还可以再优化吗?如果可以从哪里优化呢?下面我们来介绍希尔排序,正是这个排序算法的提出,使得排序算法打破了O(n2)时间复杂度的禁锢。

  定义:希尔排序(Shells Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。该算法的基本思想是:把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,排序算法便终止。

  对于希尔排序来说,最关键的就是增量该如何选取。这个增量该怎么确定,这还真是个数学难题,至今没有解答。但是通过大量的实验,还是有个经验值的。我们的例子给出的增量选取公式是:h = 3 *h + 1,下面请看图示说明。

  分析:从插入排序中我们知道,插入排在待排序数组基本有序时,插入排序的算法效率会非常高,所以我们可以这样认为,希尔排序的最终思想就是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,在对全体进行一次直接插入排序。

  而希尔排序的效率之所以很高,就是因为这个基本思想确实很有用:即当h值大的时候,数据项每一趟排序需要移动元素的个数很少,但数据项移动的距离很长。这是非常有效率的。而当h减小时,每一趟排序需要移动的元素的个数增多,但是此时数据项已经接近于它们排序后最终的位置,这对于插入排序可以更有效率。正是这两种情况的结合才使希尔排序效率那么高。

  对于增量的选取,可以称得上是一种魔法。在希尔的原稿中,他建议初始的间距为N/2,简单地把每一趟排序分成了两半。但是,这被证明并不是最好的数列。尽管对于大多数的数据来说这个方法还是比插入排序效果好,但是这种方法有时会使运行时间降到O(N2),这并不比插入排序的效率更高。间隔序列中的数字互质通常被认为很重要:也就是说,除了1之外它们没有公约数。这个约束条件使每一趟排序更有可能保持前一趟排序已排好的效果。希尔最初以N/2为间隔的低效性就是归咎于它没有遵守这个准则。

  总结:上面就是四种经典O(n2)级别排序算法的相关说明。其实在各种场合下选择排序和冒泡排序基本上是不会使用的,因为使用场景基本没有。而对于插入排序和希尔排序来说,在待排序数据基本有序的情况下,使用场景还是有的,比如一些日志文件中存储的日志,可能大部分的日志记录都是基于时间排序,只是在某些极端情况下导致一些日志晚存储了导致时间不一致。返回搜狐,查看更多