发布日期: 2020-04-15

更新日期: 2023-09-05

文章字数: 1.4k

阅读时长: 7 分

阅读次数:

希尔排序的核心也是交换,是在插入排序的基础上演进的,目的是期望快速消除更多的逆序对儿。

nums=(1 3 5 7 2 3 6 8 22 11 33 22 11 1 34 56)

size=${#nums[*]}
for((D=size/2;D>0;D/=2)){ #希尔排序就是在插入排序的基础上加上一个跳跃序列，可以说插入是临近比较，希尔则是跳跃着比较。
  for((i=D;i<size;i++)){ #先找一个下标指向第一个元素,因为默认第0个元素是排好的,所以从第1个下标的元素开始往前面插,i代表要取出的数
    local tmp=${nums[i]} #先记录下当前位置的元素,从他前面一个元素开始比较,直到找到自己合适位置就直接插入
    for(( j=i;j>=D && ${nums[j-D]} > tmp;j-=D));do
      nums[j]=${nums[j-D]}
    done
    nums[j]=${tmp}
    echo "插入nums[${i}]=${tmp}到nums[${j}]: ${nums[*]}"
  }
}

我们执行以下看一下输出结果

插入nums[8]=22到nums[8]: 1 3 5 7 2 3 6 8 22 11 33 22 11 1 34 56
插入nums[9]=11到nums[9]: 1 3 5 7 2 3 6 8 22 11 33 22 11 1 34 56
插入nums[10]=33到nums[10]: 1 3 5 7 2 3 6 8 22 11 33 22 11 1 34 56
插入nums[11]=22到nums[11]: 1 3 5 7 2 3 6 8 22 11 33 22 11 1 34 56
插入nums[12]=11到nums[12]: 1 3 5 7 2 3 6 8 22 11 33 22 11 1 34 56
插入nums[13]=1到nums[5]: 1 3 5 7 2 1 6 8 22 11 33 22 11 3 34 56
插入nums[14]=34到nums[14]: 1 3 5 7 2 1 6 8 22 11 33 22 11 3 34 56
插入nums[15]=56到nums[15]: 1 3 5 7 2 1 6 8 22 11 33 22 11 3 34 56
插入nums[4]=2到nums[4]: 1 3 5 7 2 1 6 8 22 11 33 22 11 3 34 56
插入nums[5]=1到nums[1]: 1 1 5 7 2 3 6 8 22 11 33 22 11 3 34 56
插入nums[6]=6到nums[6]: 1 1 5 7 2 3 6 8 22 11 33 22 11 3 34 56
插入nums[7]=8到nums[7]: 1 1 5 7 2 3 6 8 22 11 33 22 11 3 34 56
插入nums[8]=22到nums[8]: 1 1 5 7 2 3 6 8 22 11 33 22 11 3 34 56
插入nums[9]=11到nums[9]: 1 1 5 7 2 3 6 8 22 11 33 22 11 3 34 56
插入nums[10]=33到nums[10]: 1 1 5 7 2 3 6 8 22 11 33 22 11 3 34 56
插入nums[11]=22到nums[11]: 1 1 5 7 2 3 6 8 22 11 33 22 11 3 34 56
插入nums[12]=11到nums[8]: 1 1 5 7 2 3 6 8 11 11 33 22 22 3 34 56
插入nums[13]=3到nums[9]: 1 1 5 7 2 3 6 8 11 3 33 22 22 11 34 56
插入nums[14]=34到nums[14]: 1 1 5 7 2 3 6 8 11 3 33 22 22 11 34 56
插入nums[15]=56到nums[15]: 1 1 5 7 2 3 6 8 11 3 33 22 22 11 34 56
插入nums[2]=5到nums[2]: 1 1 5 7 2 3 6 8 11 3 33 22 22 11 34 56
插入nums[3]=7到nums[3]: 1 1 5 7 2 3 6 8 11 3 33 22 22 11 34 56
插入nums[4]=2到nums[2]: 1 1 2 7 5 3 6 8 11 3 33 22 22 11 34 56
插入nums[5]=3到nums[3]: 1 1 2 3 5 7 6 8 11 3 33 22 22 11 34 56
插入nums[6]=6到nums[6]: 1 1 2 3 5 7 6 8 11 3 33 22 22 11 34 56
插入nums[7]=8到nums[7]: 1 1 2 3 5 7 6 8 11 3 33 22 22 11 34 56
插入nums[8]=11到nums[8]: 1 1 2 3 5 7 6 8 11 3 33 22 22 11 34 56
插入nums[9]=3到nums[5]: 1 1 2 3 5 3 6 7 11 8 33 22 22 11 34 56
插入nums[10]=33到nums[10]: 1 1 2 3 5 3 6 7 11 8 33 22 22 11 34 56
插入nums[11]=22到nums[11]: 1 1 2 3 5 3 6 7 11 8 33 22 22 11 34 56
插入nums[12]=22到nums[10]: 1 1 2 3 5 3 6 7 11 8 22 22 33 11 34 56
插入nums[13]=11到nums[11]: 1 1 2 3 5 3 6 7 11 8 22 11 33 22 34 56
插入nums[14]=34到nums[14]: 1 1 2 3 5 3 6 7 11 8 22 11 33 22 34 56
插入nums[15]=56到nums[15]: 1 1 2 3 5 3 6 7 11 8 22 11 33 22 34 56
插入nums[1]=1到nums[1]: 1 1 2 3 5 3 6 7 11 8 22 11 33 22 34 56
插入nums[2]=2到nums[2]: 1 1 2 3 5 3 6 7 11 8 22 11 33 22 34 56
插入nums[3]=3到nums[3]: 1 1 2 3 5 3 6 7 11 8 22 11 33 22 34 56
插入nums[4]=5到nums[4]: 1 1 2 3 5 3 6 7 11 8 22 11 33 22 34 56
插入nums[5]=3到nums[4]: 1 1 2 3 3 5 6 7 11 8 22 11 33 22 34 56
插入nums[6]=6到nums[6]: 1 1 2 3 3 5 6 7 11 8 22 11 33 22 34 56
插入nums[7]=7到nums[7]: 1 1 2 3 3 5 6 7 11 8 22 11 33 22 34 56
插入nums[8]=11到nums[8]: 1 1 2 3 3 5 6 7 11 8 22 11 33 22 34 56
插入nums[9]=8到nums[8]: 1 1 2 3 3 5 6 7 8 11 22 11 33 22 34 56
插入nums[10]=22到nums[10]: 1 1 2 3 3 5 6 7 8 11 22 11 33 22 34 56
插入nums[11]=11到nums[10]: 1 1 2 3 3 5 6 7 8 11 11 22 33 22 34 56
插入nums[12]=33到nums[12]: 1 1 2 3 3 5 6 7 8 11 11 22 33 22 34 56
插入nums[13]=22到nums[12]: 1 1 2 3 3 5 6 7 8 11 11 22 22 33 34 56
插入nums[14]=34到nums[14]: 1 1 2 3 3 5 6 7 8 11 11 22 22 33 34 56
插入nums[15]=56到nums[15]: 1 1 2 3 3 5 6 7 8 11 11 22 22 33 34 56