算法之排序:第一节

计算机算法中排序经常使用到的有:
1、插入(比较)排序
2、选择排序
3、冒泡排序
4、快速排序
6、归并排序
不经常用到的有:
1、计数排序
2、桶排序
3、堆排序
4、基数排序
本节对常用排序进行分析。

插入排序

插入排序是一种原地稳定(In place)排序,Pesudocode(ascend version):
INSERTION-SORT(A)

  1.  for i = 2 to A.length
  2.      c = A[i]
  3.      for j = i-1 to 1 #[m,n],前闭后闭区间
  4.          if A[j]>c
  5.          A[j+1] = A[j]
  6.     a[j+1] = c

可以看得出来,这是一种典型可归纳证明的算法,归纳中的不变性质也称循环不变量(loop invariation)
Initialize:初始时,i=2, 即A[1]作为已经排序序列成立。
Maitenance:保持时,i=k,即A[1:k]作为已经排序序列成立,那么A[1:k+1]是否仍然成立?
由于A[1:k]已经有序。也就是将A[k+1]插入到一个升序序列中,即从A[1:k]的右侧中找到第一个比A[k+1]小的值,然后将A[k+1]插入其后面即可。即经过2-6步后,A[1:k+1] 仍然有序
Termination:结束时,i=A.length,即A[1:A.length]也是有序序列,证明此算法正确

特点:
1、插入排序的时间消耗会因序列是否有序而变化较大。若原序列已经有序,那么时间消耗为O(n);若原序列为逆序,那么时间消耗为O(n^2)
2、插入排序的I/O次数也会因为原序列是否有序而变化较大
3、插入排序的序列有序化是逐渐展开,若在序列中间某个位置中断后其无法保证序列的最大\小值序列已经出现,像冒泡与选择则从一开始即进行全局最值排序。

选择排序

选择排序同样是一种原地稳定(In place)排序,其Pesudocode(ascend version):
SELECT-SORT(A)

  1. for i = 1 to A.length-1
  2.     min_i=i
  3.     for j = i+1 to A.length
  4.         if A[min_i] < A[j]
  5.             min_i = j
  6.     A[min_i] <> A[i]  # swap A[min_i] and A[i]

特点:
1、选择排序的时间不会因为序列是否有序而发生变化。其时间消耗永远为O(n^2)
2、选择排序的I/O次数也不会因为原序列是否有序而发生变化,其I/O次数是三者中最少的
3、选择排序的有序化,是从全局展开的,即其为最值排序

冒泡排序

冒泡排序同样是一种原地稳定(In place)排序,其Pesudocode(ascend version):
BUBBLE-SORT(A)

  1. for i = A.length to 2
  2.     for j = 1 to i-1
  3.         if A[j] > A[j+1]
  4.              A[j]<>A[j+1] #swap A[j] and A[j+1]

特点:
1、冒泡排序可以随序列是否有序,而降低其时间消耗
2、冒泡排序的I/O次数会因为原序列是否有序,而发生变化
3、冒泡排序同样是全局展开的,为最值排序。

快速排序

快速排序是一种原地不稳定的(In place)排序,其Pesudocode(ascend version):
QUICK-SORT(A,i,j) # [i,j]

  1. if i < j
  2.     m = PARTITION(A,i,j)
  3.     QUICK-SORT(A,i,m-1)
  4.     QUICK-SORT(A,m+1,j)

PARTITION(A,b,e)  #[b,e],b<e

  1. i = b-1
  2. for j = b to e-1
  3.      if A[j] < A[e]
  4.          A[++i]<>A[j]
  5. A[e]<>A[i+1]
  6. return i+1

上面PARTITION的loop invariation为{x<y| A[b:i]∋x,A(i,j]∋y},其证明过程为:
Initialization:i=b-1,此时A[b:i]=∅,A(i,j]=A[b],满足循环不变量
Maintenance:j=k时满足,那么j=k+1,设A[k+1]为y,若y<A[e],那么i=i+1并交换A[i]与A[j]后,仍然满足循环不变量,若y>=A[e],那么只是对j进行+1,即A(i,j]扩大一个元素,那么仍然满足循环不变量
Termination:最后将A[e]加入到A[b:j]中,由于存在A[i+1]>=A[e],所以交换A[e]与A[i+1]不响应循环不变量,仍然能够保证为{x<y| A[b:i]∋x,A(i,j]∋y}

归并排序

归并排序是一种非原地稳定的(not in place)排序,其Pesudocode(ascend version):
MERG_SORT(A,i,j) # [i,j]

  1. if i<j
  2.     m = (i+j)/2
  3.     MERG_SORT(A,i,m)
  4.     MERG_SORT(A,m+1,j)
  5.     MERG(A,i,m,j)

MERG(A,i,m,j)  # A[i,m] + A(m,j] -> A[i,j]

  1. X1= A[i,m]
  2.  X1[m-i+1] = MAX_INT  #set a sentinel value
  3. X2= A(m,j]
  4. X2[j-m] = MAX_INT      #set a sentinel value
  5. s = i
  6. s1 = 0
  7. s2 = 0
  8. while s <= j
  9.     if X1[s1] < X2[s2]
  10.         A[s++] = X1[s1++]
  11.     else
  12.         A[s++] = X2[s2++]

归并排序在《算法导论》中作为“分治”算法的典型代表,即将问题分解为子问题,将子问题的解收集起来组合为整体解,即divide-conquer-combine 。其中,“哨兵”的设置减少了MERG算法中的分支跳转(减少流水线断流),又一个空间换时间的例子。

分治算法的时间复杂度分析公式为:
T(n) = O(1)                             n = 1
T(n) = aT(n/b) + D(n) + C(n)  n > 1
其中,
参数a、b含义:问题分解为a个子问题,其中每个子问题的规模为n/b,则所有子问题的求解时间复杂度为aT(n/b)
D(n)的含义: 将一个规模为n的问题分解的时间复杂度为D(n)
C(n)的含义: 将n/b个子问题的解合并为一个解的时间复杂度为C(n)

算法之排序:第一节》上有1条评论

  1. yangxiaowei 文章作者

    选择排序与冒泡排序属于最值排序,即在一个固定的集合中选出其最值,然后缩小集合,直至集合只剩下一个元素,也就是说这两种排序,从本质上讲并不是要完成排序,而是在找最值,只是其像堆排序一样,在完成找最值的过程中,顺带着完成了排序,换句话说:排序是这种类型算法的副产品。
    而对于插入排序,其本身就是在维护一个集合的有序态,每当进入一个元素后,其算法都是在保持这个集合的有序。
    而对于快速排序,与插入排序相同,其也是在维持一种集合有序,只是这种有序非常规意义的元素间线性有序,而是一种集合间线性有序:快排要求保持集合内两个子集合之间的“有序”。
    对于归并排序,个人认为是插入排序的一种延伸,即在插入排序中扩大集合从一个元素为粒度变为一个数据集为粒度。同时归并排序采用了分治策略来实现问题的分解,总而言之,这种方式目前还没打到一种日常生活中可见的模型来形像化。
    这里面唯一可以做流式排序的算法,也就只有插入排序,因为其并不需要事先知道整个排序集合是什么,其总是在维持一个现有集合的有序。
    个人观点:有元素间线性有序的插入、选择、冒泡、归并是稳定排序;而对于非元素间线性有序的快排是不稳定排序。

发表评论