冒泡排序法

类似旗袍上涌的动作，会将数据在数组中从小大大或者从大到小不断的向前移动。

基本思想:

冒泡排序的基本思想是对比相邻的两个元素值，如果满足条件就交换元素值，把较小的元素移动到数组前面，把大的元素移动到数组后面(也就是交换两个元素的位置)，这样较小的元素就像气泡一样从底部上升到顶部。

算法思路

冒泡算法由双层循环实现，其中外部循环用于控制排序轮数，一般为要排序的数组长度减1次，因为最后一次循环只剩下一个数组元素，不需要对比，同时数组已经完成排序了。而内部循环主要用于对比数组中每个相邻元素的大小，以确定是否交换位置，对比和交换次数随排序轮数而减少。

#!/bin/bash
array=(112 221 33 55 66 11 25 68)
length="${#array[@]}"
for ((i=1; i<=$length; i++))
do
  for ((j=1; j<=$length-$i; j++))
  do
    first=${array[$j]}
    k=$[$j+1]
    second=${array[$k]}
    if [ $first -gt $second ]
      then
        temp=$first
        array[$j]=$second
        array[$k]=$temp
    fi
  done
done

echo "new_array: ${array[@]}"

直接选择排序

与冒泡排序相比，直接选择排序的交换次数更少，所以速度会快些。

基本思想:

将指定排序位置与其它数组元素分别对比，如果满足条件就交换元素值，注意这里区别冒泡排序，不是交换相邻元素，而是把满足条件的元素与指定的排序位置交换（如从最后一个元素开始排序），这样排序好的位置逐渐扩大，最后整个数组都成为已排序好的格式。

#!/bin/bash
array=(77 22 99 1 23 55 11)
echo "老数组顺序为 ${array[@]}"
length=${#array[@]}

for ((i=1; i<=length; i++))
do
  index=0
  for ((j=1; j<=length-i; j++))
  do
    CURR=${array[$j]}
    MAX=${array[$index]}
    if [ $CURR -gt $MAX ]
      then
        index=$j
    fi
  done
  last=$[ $length - $i ]
  temp=${array[$last]}
  array[$last]=${array[$index]}
  array[$index]=$temp

done

echo "新数组的顺序为 ${array[@]}"

反转排序

以相反的顺序把原有数组的内容重新排序。

基本思想:

把数组最后一个元素与第一个元素替换，倒数第二个元素与第二个元素替换，以此类推，直到把所有数组元素反转替换。

#!/bin/bash
array=(1 2 3 4 5 6 7 8 9)
length=${#array[@]}
for ((i=0; i<=length/2; i++))
do
  first=${array[$i]}
  last=${array[$length-$i-1]}
  temp=$first
  array[$i]=$last
  array[$length-$i-1]=$temp
done
echo "${array[*]}"

直接插入算法

插入排序，又叫直接插入排序。实际中，我们玩扑克牌的时候，就用了插入排序的思想。

基本思想:

在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。

#!/bin/bash
array=(8 2 9 44 6 28 10)
echo "原数组为 ${array[*]}"
length=${#array[@]}
for ((i=1; i<=$length; i++))
do
  for ((j=0; j<=$i; j++))
    do
      if [[ ${array[$i]} -lt ${array[$j]} ]]
        then
           temp=${array[$i]}
           array[$i]=${array[$j]}
           array[$j]=$temp
      fi
    done
done

echo "新数组为 ${array[@]}"
~
~

希尔算法

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序 。

基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…

2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

gap越大，数据挪动得越快；gap越小，数据挪动得越慢。前期让gap较大，可以让数据更快得移动到自己对应的位置附近，减少挪动次数。

#!/bin/bash
array=(8 9 1 7 2 3 5 4)
length=${#array[@]}
echo "原数组为 ${array[@]}"
#设长度的一半为gap初始间隔，每次循环gap都除以2，直至gap为1结束循环
for ((gap=$length/2; gap>0; gap/=2))
do
#因为gap为整个长度的一半，所以gap到length结尾包含的元素数刚好为需要进行直接插入算法的个数
  for ((i=gap; i<$length; i++))
    do
    #设一个第三变量方便直接插入进行交换
      temp=${array[$i]}
       #对距离为gap的元素组进行排序，每一轮比较拿当前轮次最后一个元素与组内其他元素比较，将数组大的往后放
      for((j=i-gap; j>=0&&temp<${array[$j]}; j-=gap))
        do
          array[$j+$gap]=${array[$j]}
        done
      array[$j+$gap]=$temp
    done
done

echo "新的数组为 ${array[*]}"