谈插入排序与冒泡排序

这里讨论的主要是关于插入排序和冒泡排序这两种算法的复杂度以及背后的一些思想。

这两种排序算法的实现过程的比较简单,这里就不提了。并且也很容易证明这两种算法的平均时间复杂度和最坏时间复杂度都是\(O(n^2)\)量级的。

这两种算法背后一个思想,就是一次比较之至多能够消除一个逆序对,那么这种算法排序的时间复杂度的下限就是逆序对的数量。什么是逆序对,就是3个数,2,1,3进行排序(升序)时,逆序对有1对,就是2,1这一对,如果是3,2,1,就是有三个逆序对。

很容易想象,当n个数完全逆序的时候,逆序对的数量是最多的n(n-1)/2,这也就对应了最坏的时间复杂度是\(O(n^2)\),而平均情况下,假设各种序列出现的概率相同,平均一个序列的逆序对的个数是n(n-1)/4,因为一个序列和这个序列倒置过后的总共的逆序对是n(n-1)/2,平均下来一人一半。所以一次比较之至多能够消除一个逆序对的算法平均时间复杂度逃脱不了\(O(n^2)\),如果要突破,你只能从算法策略上下手了,比如快速排序一次比较之后交换元素可能会消灭多个逆序对,再比如归并排序,在merge的时候也可能消灭多个逆序对。这两种排序算法就有别与插入和冒泡了,突然想起来选择排序,也是一样的。

发表评论

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