用shell教你搞定各种排序算法-插入排序

发布日期: 2020-04-15

更新日期: 2023-09-05

文章字数: 877

阅读时长: 4 分

阅读次数:

插入排序的核心也是交换，注意和冒泡排序一样，都是相邻交换

# 定义一个数组
nums=(1 3 5 7 2 3 6 8 22 11 33 22 11 1 34 56)

size=${#nums[*]}
for((i=1;i<size;i++)){ #先找一个下标指向第一个元素,因为默认第0个元素是排好的,所以从第1个下标的元素开始往前面插,i代表要取出的数
  local tmp=${nums[i]} #先记录下当前位置的元素,从他前面一个元素开始比较,直到找到自己合适位置就直接插入
  for((j=i;j>=0;j--)){ #找一个下标先指向当前要插入的对象，然后一次和前面的元素进行比较，直到找到一个比自己小的元素，那这个元素后边位置就是要插入的元素所占的位置，否则就把前面的元素奔后移，来给要出入的元素腾空
    if [[ ${nums[j-1]} -gt ${tmp} ]];then #如果前面的元素比要出入的元素值大，就把前一个元素向后移动
         nums[j]=${nums[j-1]}
    else
        nums[j]=${tmp}
        echo "插入nums[${i}]=${tmp}到nums[${j}]: ${nums[*]}"
        break 1 # 这里只跳出一层循环
    fi
  }
}

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

插入nums[1]=3到nums[1]: 1 3 5 7 2 3 6 8 22 11 33 22 11 1 34 56
插入nums[2]=5到nums[2]: 1 3 5 7 2 3 6 8 22 11 33 22 11 1 34 56
插入nums[3]=7到nums[3]: 1 3 5 7 2 3 6 8 22 11 33 22 11 1 34 56
插入nums[4]=2到nums[1]: 1 2 3 5 7 3 6 8 22 11 33 22 11 1 34 56
插入nums[5]=3到nums[3]: 1 2 3 3 5 7 6 8 22 11 33 22 11 1 34 56
插入nums[6]=6到nums[5]: 1 2 3 3 5 6 7 8 22 11 33 22 11 1 34 56
插入nums[7]=8到nums[7]: 1 2 3 3 5 6 7 8 22 11 33 22 11 1 34 56
插入nums[8]=22到nums[8]: 1 2 3 3 5 6 7 8 22 11 33 22 11 1 34 56
插入nums[9]=11到nums[8]: 1 2 3 3 5 6 7 8 11 22 33 22 11 1 34 56
插入nums[10]=33到nums[10]: 1 2 3 3 5 6 7 8 11 22 33 22 11 1 34 56
插入nums[11]=22到nums[10]: 1 2 3 3 5 6 7 8 11 22 22 33 11 1 34 56
插入nums[12]=11到nums[9]: 1 2 3 3 5 6 7 8 11 11 22 22 33 1 34 56
插入nums[13]=1到nums[1]: 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

当然我们还可以简化

# 定义一个数组
nums=(1 3 5 7 2 3 6 8 22 11 33 22 11 1 34 56)

size=${#nums[@]}
for((i=1;i<size;i++)){ #先找一个下标指向第一个元素,因为默认第0个元素是排好的,所以从第1个下标的元素开始往前面插,i代表要取出的数
  local tmp=${nums[i]} #先记录下当前位置的元素,从他前面一个元素开始比较,直到找到自己合适位置就直接插入
  local j;for((j = i; j>=0 && nums[j-1]>tmp; j--)); do # 这里不用if判断，直接在for里面进行判断，不满足条件的直接跳出
    nums[j]=${nums[j-1]}
  done
  nums[j]=${tmp}
  echo "插入nums[${i}]=${tmp}到nums[${j}]: ${nums[*]}"
}