顾名思义 如同我们打扑克牌一样 按照顺序找到一张不合理的牌插入到合适的位置 直到全部有序。
代码实现如下
假设第一个数字是有序的 我们从第二个数字开始想左边找 找到正确的位置放入即可。
#!/usr/bin/awk -f
# insertion sort
BEGIN{
print 插入排序
print 输入示例 8 1 6 3 5 2 4 7
for( i 1; i NF; i )
A[i] $i ;
isort(A, NF)
function show(arr,n, j, i) {
for( i 1; i n; i )
printf( %d%s , arr[i], i j ? | : )
printf( %d%sn , arr[i], i j ? | : )
function nl() {
printf( ---------------------------------n )
function isort( arr, n, i, j,t) {
for( i 2; i n; i ) {
for( j i ; j 1 arr[j-1] arr[j] ; j--){
# 交换
t arr[j-1]; arr[j-1] arr[j] ; arr[j] t
show(arr, n, i)
nl()
执行脚本命令
$ chomd x ./sorti.awk $ ./sorti.awk
输入测试用例
8 1 6 3 5 2 4 7
我们看到输出结果(输出内容包括每次拿到新数字后排序结果,竖线前数是有序的)
1 8|6 3 5 2 4 7 1 6 8|3 5 2 4 7 1 3 6 8|5 2 4 7 1 3 5 6 8|2 4 7 1 2 3 5 6 8|4 7 1 2 3 4 5 6 8|7 1 2 3 4 5 6 7 8| ---------------------------------
