IDL编程学习之归并排序算法

15195775117

[1.归并排序法的优越性]
归并排序算法思路：

案例流程图：

与插入排序算法相比，归并排序算法的格局更高，插入排序在一条线上犹如交通堵塞般进行艰难的调整（冒泡也是这种），简直是画地为牢，而归并排序则构建了一个立体的理解空间，高下立判。

15195775117

2.把2个已排好序的序列合并：
将已排序的a[p:q]和a[q+1:r]合并为一个顺序序列：
function f,a,p,q,r
M=[a[p:q],!values.f_infinity]
N=[a[q+1:r],!values.f_infinity]
I=0
J=0
for K=P,r do begin
  IF(M[I] LE N[J])THEN BEGIN
    A[K]=M[I]
    I++
    ENDIF ELSE BEGIN
      A[K]=N[J]
      J++
    ENDELSE
endfor
RETURN,A
END
这里，设置哨兵牌是一个技巧，避免了检查：

15195775117

[Θ的粗略推导法]
求插入排序和归并排序的“最坏情况运行时间”Θ(n)其实只需要考虑哪些最耗时的步骤，常量时间的步骤全都不用管：
插入排序：87654321，需要1+2+3+4+5+6+7次比较，n个数需要比较n(n-1)/2次；
归并排序：87654321，需要8*3次比较，n个数需要nln(n)/ln(2)次比较。
比较的次数正好是其Θ函数，所以这种粗略的方法可能是有效的。
[两种排序算法的评测]
比较两种排序方法，插入排序的“最好情况运行时间”是Θ(n)，最坏是Θ(n^2);归并排序无论好坏，比较次数一样，运行时间介于插入排序的最好和最坏时间之间，所以，如果排序算法受序列混乱程度影响，不同情况的运行时间方差较大的就吃亏，毕竟是比较最坏情况。就平均来看，插入排序真的比归并排序差吗？未必。

15195775117

计算归并排序算法的Θ时，通常假设n是2的整数次幂，这样方便分组，比较起来整齐，其实是任意数都行。

15195775117

问题：
不使用“哨兵”，而是一旦一个数组比较完了，就把另一个数组剩余部分复制过去。
代码：
pro linshi,a,b
na=n_elements(a)
nb=n_elements(b)
c=fltarr(na+nb)
i=0
j=0
k=0
while i lt na and j lt nb do begin
  if(a lt b[j])then begin
    c[k]=a
    i++
    endif else begin
      c[k]=b[j]
      j++
    endelse
        k++;反正c数组序号都要进一位，就不在两种情况下分别进位了
endwhile
if(i eq na)then begin
  c[k:-1]=b[j:-1];c数组空余的位置正好容纳没有参与比较的元素
  endif else begin
    c[k:-1]=a[i:-1]
  endelse
  print,c
end
运行与输出：
IDL> x
       1       2       4       5       6
IDL> y
       0       2       5       7       7
IDL> linshi,x,y
     0.000000      1.00000      2.00000      2.00000      4.00000
      5.00000      5.00000      6.00000      7.00000      7.00000
关于这种算法的Θ：
最坏情况是最大数单独构成一个数组，两个数组比较，需要n-1次(两个数组总共n个元素)，与设置哨兵一样是Θ(n)，但估计略慢，毕竟多了步骤。