IDL编程学习之插入排序

15195775117

插入排序思路，就是把后面的数依次与前面的数对比，顺序反了就调换次序，最终小的“沉淀”到最左。
案例：[5,2,4,6,1,3]
从第二位开始，
2与5对比，调换位置！结果：254613
第三位数与之前的数对比：
4与5对比，调换位置！245613
4与2对比，位置不变！245613
第四位数与之前的数对比：
6与5对比，位置不变！
6与4对比，位置不变！（1）
6与2对比，位置不变！（2）
第五位数与之前的数对比：
1与6对比，调换位置！245163
1与5对比，调换位置！241563
1与4对比，调换位置！214563
1与2对比，调换位置！124563
第六位数与之前的数对比：
3与6对比，调换位置！124536
3与5对比，调换位置！124356
3与4对比，调换位置！123456
3与2对比，位置不变！
3与1对比，位置不变！（3）
因为插入算法用来比较的第N位数之前的都是排好的，所以（1）（2）（3）是不需要的。
IDL的插入排序程序：
function f,x
n=n_elements(x)
for i=1,n-1 do begin
  a=x
j=i-1
while j ge 0 and x[j] gt a do begin
  x[j+1]=x[j]
  x[j]=a
  j--
endwhile
endfor
return,x
end
pro paixu
print,f([5,2,4,6,1,3,16,7.3,-4])
end
输出：
     -4.00000      1.00000      2.00000      3.00000      4.00000
      5.00000      6.00000      7.30000      16.0000
总结：
1.插入排序是用“两两比较”这种基本操作来排序的，工具原始就更显技术；
2.之所以倒着比较，是因为“第N位数”的位置被空出来了，这个位置可以覆盖；顺序比较的话，前面的数没法覆盖后面的数，所以这个空出的位置在哪，也影响排序的方法；这也说明了这个算法看着简单，其实有讲究。

15195775117

插入排序步骤的另一种理解可以是：比第N位大的数都向前走一格，然后把第N位数赋给不走的那个数字之后的位置，这比交换次序省些步子。
程序：
function f,x
n=n_elements(x)
for i=1,n-1 do begin
  a=x[i]
j=i-1
while j ge 0 and x[j] gt a do begin
  x[j+1]=x[j]
  j--
endwhile
x[j+1]=a
endfor
return,x
end
pro paixu
print,f([5,2,4,6,1,3,16,7.3,-4])
end