深入浅出数据结构C语言版(17)——有关排序算法的分析

时间:2021-07-16 10:31:22

  这一篇博文我们将讨论一些与排序算法有关的定理,这些定理将解释插入排序博文中提出的疑问(为什么冒泡排序与插入排序总是执行同样数量的交换操作,而选择排序不一定),同时为讲述高级排序算法做铺垫(高级排序为什么会更快)。

 

  在讨论相关定理之前,我们必须先掌握一个与顺序有关的概念:逆序数

  所谓逆序数,就是“逆序组合的个数”,假设我们希望的顺序为从小到大(反之同理):

  设有元素互异数列X0,X1,X2……Xn-1(元素互异即数列中任取两数均不相等)从中任取两数作为组合(Xa,Xb),若a<b(即Xa在数列中位于Xb之前)且Xa>Xb,则(Xa,Xb)逆序,若a<b且Xa<Xb,则(Xa,Xb)不是逆序。整个数列的逆序数即数列中所有逆序组合(Xa,Xb)的个数。(不难发现,若数列有n个数,则任取两数的组合(Xa,Xb)共有n(n-1)/2个,n为元素个数。)

  

  下面我们来举几个计算逆序数的例子(依然假设我们希望的顺序为从小到大):

  1.设有数列1,2,3,4,5,因为从中任取两数(Xa,Xb)且a<b,均有Xa<Xb,即任一组合(Xa,Xb)均非逆序,所以数列1,2,3,4,5的逆序数为:逆序组合的个数=0

  2.设有数列5,4,3,2,1,因为从中任取两数(Xa,Xb)且a<b,均有Xa>Xb,即任一组合(Xa,Xb)均为逆序,所以数列1,2,3,4,5的逆序数为:逆序组合的个数=n(n-1)/2=5*4/2=10

  2.设有数列2,3,4,5,1,从中任取两数(Xa,Xb),a<b且Xa>Xb的组合有(2,1),(3,1),(4,1),(5,1)共4个,即逆序组合共4个,所以数列2,3,4,5,1的逆序数为:逆序组合的个数=4

  从例1我们可以推出定理1:若数列为有序,则其逆序数为0。例1的计算过程即本定理的证明。

  而从定理1我们又可以得出定理2:若数列非有序,则其逆序数必大于0。证明过程类似于定理1,略

  从定理1和定理2我们又可以得出定理3:将数列从非有序转换为有序(即排序)的过程,就是减少数列逆序数的过程。

 

 

  明白了什么是逆序数,以及排序算法的“本质”之后,我们开始讨论定理4:

  设有元素互异数列X0,X1,X2……Xn-1,其反数列为Xn-1,Xn-2,……X0,则这两个数列的逆序数之和必为n*(n-1)/2

  因为数列元素互异,所以任取两数Xa,Xb且a<b,要么Xa>Xb,要么Xa<Xb。也就是说组合(Xa,Xb)若在原数列中非逆序,则必在反数列中逆序,反之则反。而元素个数为n的数列中组合(Xa,Xb)的个数共为n*(n-1)/2个,任一组合要么在原数列逆序,要么在反数列逆序,所以原数列与反数列的逆序数之和即组合(Xa,Xb)的个数:n*(n-1)/2

  有了定理4,我们就可以给出定理5:

  有n个互异元素的数列,其平均逆序数为n*(n-1)/4

  从定理4可知,给定的数列与其反数列的逆序数之和为n*(n-1)/2,所以该数列的平均逆序数即两者之和的一半n*(n-1)/2。

 

 

  接下来是简单的定理6:

  对于元素互异数列,交换其中相邻的两个数Xn,Xn+1的位置,则数列的逆序数要么+1,要么-1。

  假设(Xn,Xn+1)为逆序,则交换两者将使该组合变为非逆序,但不会影响其他组合如(Xa,Xn)(Xn,Xb)的顺序,从而数列逆序数-1

  假设(Xn,Xn+1)为非逆序,则交换两者将使该组合变为逆序,但不会影响其他组合如(Xa,Xn)(Xn,Xb)的顺序,从而数列逆序数+1

 

  根据

  定理3:将数列从非有序转换为有序(即排序)的过程,就是减少数列逆序数直至0的过程。

  定理5:有n个互异元素的数列,其平均逆序数为n*(n-1)/4

  定理6:对于元素互异数列,交换其中相邻的两个数Xn,Xn+1的位置,则数列的逆序数要么+1,要么-1。

  我们可以得出定理7:

  通过交换相邻元素来完成排序的算法,其平均时间复杂度为Ω(n2

  对于n元素互异的数列,其平均逆序数为n*(n-1)/4,而排序即减少逆序数至0的过程,因为交换相邻元素最多使逆序数-1,所以必须有n*(n-1)/4次交换才能使数列逆序数为0,即交换相邻元素的排序算法平均需要执行n*(n-1)/4次交换操作,也就是说平均时间复杂度为Ω(n*(n-1)/4),即Ω(n2)。虽然我们一直强调元素互异看起来有所不妥,但排序算法必然要可以处理元素互异情况,而且Ω(n)也只是平均时间复杂度,没有考虑任何具体情形。

   

  至此,本篇博文对于排序算法的定理就算是介绍完毕了。但有关排序算法的分析尚未结束。

  我们先来回答插入排序博文中的问题:为什么冒泡排序和插入排序执行的交换操作总是一样多。其原因如下:

  这两个算法都是通过交换相邻元素来排序的,而且它们都不会执行使数列逆序数+1的交换,也就是说它们每执行一次交换就会且只会使数列的逆序数-1。所以对于给定数列,若其逆序数为n,则两者都将执行n次交换操作。

  那么,选择排序有时候只需要更少的交换次数的原因也就出来了,因为选择排序并不是通过交换相邻元素来排序的算法,比如数列5,4,3,2,1,选择排序第一次“实质交换”后,数列变为了1,4,3,2,5,也就是说它这一次交换就使得数列的逆序数-7。所以选择排序可以使用更少的“实质交换”来完成排序,当然这并不意味着选择排序就会很快,原因不再赘述。

 

  接下来,根据前面的定理(3、5、6)。我们可以推出本文最后一个定理,也就是定理7的推理,也是所有高级排序算法的根本:

  要令排序算法的时间复杂度低于O(n2),必须令算法执行“远距离的元素交换”,使得平均每次交换减少不止1逆序数。

  

  下一篇博文我们将讨论希尔排序,它是插入排序的升级版,升级之处显然就是“令元素远距离的交换”,而且升级的思想非常直白,具体的实现我们将在下一篇博文介绍。