用shell教你搞定各种排序算法-归并排序

归并排序采用的是分治的思想。归就是归纳,并就是合并。

main(){
  local array=(1 3 5 7 9 2 4 6 8 0 7 9 2 4)
  sort "0" "${#array[@]}"
}

function sort(){
    local low=$1
    local high=$2

    if [[ ${low} -ge  ${high} ]] ; then
      return
    fi


    local mid=$(($((low+high))/2))

    sort ${low} ${mid}
    sort $((mid+1)) ${high}
    merge ${low} ${mid} ${high}
}


function merge(){
  local low=$1
  local mid=$2
  local high=$3

  local i=${low}
  local j=$((mid+1))
  local tmp=();

  local k=0;
  while [[ ${i} -le ${mid} ]] && [[ ${j} -le ${high} ]];do
    if [[ ${array[i]} -lt ${array[j]} ]];then
        tmp[k]=${array[i]}
        let k++;
        let i++;
    else
       tmp[k]=${array[j]}
       let k++;
       let j++;
    fi
  done


  while [[ ${i} -le ${mid} ]];do
        tmp[k]=${array[i]}
        let k++;
        let i++;
  done

  while [[ ${j} -le ${high} ]];do
        tmp[k]=${array[j]}
        let k++;
        let j++;
  done

  for((l=0;l<k;l++));do
        index=$((low + l))
        array[$index]=${tmp[$l]}
  done

  echo ${array[*]}
}
main

运行最后结果如下

1 3 5 7 9 2 4 6 8 0 7 9 2 4
1 3 5 7 9 2 4 6 8 0 7 9 2 4
1 3 5 7 9 2 4 6 8 0 7 9 2 4
1 3 5 7 2 9 4 6 8 0 7 9 2 4
1 3 5 7 2 9 4 6 8 0 7 9 2 4
1 3 5 7 2 4 6 9 8 0 7 9 2 4
1 2 3 4 5 6 7 9 8 0 7 9 2 4
1 2 3 4 5 6 7 9 0 8 7 9 2 4
1 2 3 4 5 6 7 9 0 8 7 9 2 4
1 2 3 4 5 6 7 9 0 7 8 9 2 4
1 2 3 4 5 6 7 9 0 7 8 9 2 4
1 2 3 4 5 6 7 9 0 7 8 9 2 4
1 2 3 4 5 6 7 9 0 2 4 7 8 9
0 1 2 2 3 4 4 5 6 7 7 8 9 9