用shell语言实现插入排序，希尔排序，冒泡排序，堆排序，选择排序，快速排序，归并排序算法并注释说明时间复杂度及原理

插入排序：
# 时间复杂度：O(n^2)
# 原理：插入排序是一种简单的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
#!/bin/bash
# 插入排序
insertion_sort() {
    arr=($@)
    for ((i=1; i<${#arr[@]}; i++))
    do
        tmp=${arr[$i]}
        j=$(($i-1))
        while [ $j -ge 0 -a ${arr[$j]} -gt $tmp ]
        do
            arr[$(($j+1))]=${arr[$j]}
            j=$(($j-1))
        done
        arr[$(($j+1))]=$tmp
    done
    echo ${arr[@]}
}
arr=(5 4 3 2 1)
echo "排序前：${arr[@]}"
echo "排序后：$(insertion_sort ${arr[@]})"
希尔排序：
# 时间复杂度：O(n^1.3)
# 原理：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
#!/bin/bash
# 希尔排序
shell_sort() {
    arr=($@)
    gap=${#arr[@]}
    while [ $((gap/=2)) -gt 0 ]
    do
        for ((i=$gap; i<${#arr[@]}; i++))
        do
            tmp=${arr[$i]}
            j=$(($i-$gap))
            while [ $j -ge 0 -a ${arr[$j]} -gt $tmp ]
            do
                arr[$(($j+$gap))]=${arr[$j]}
                j=$(($j-$gap))
            done
            arr[$(($j+$gap))]=$tmp
        done
    done
    echo ${arr[@]}
}
arr=(5 4 3 2 1)
echo "排序前：${arr[@]}"
echo "排序后：$(shell_sort ${arr[@]})"
冒泡排序：
# 时间复杂度：O(n^2)
# 原理：冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
#!/bin/bash
# 冒泡排序
bubble_sort() {
    arr=($@)
    for ((i=0; i<${#arr[@]}; i++))
    do
        for ((j=0; j<$((${#arr[@]}-i-1)); j++))
        do
            if [ ${arr[$j]} -gt ${arr[$(($j+1))]} ]
            then
                tmp=${arr[$j]}
                arr[$j]=${arr[$(($j+1))]}
                arr[$(($j+1))]=$tmp
            fi
        done
    done
    echo ${arr[@]}
}
arr=(5 4 3 2 1)
echo "排序前：${arr[@]}"
echo "排序后：$(bubble_sort ${arr[@]})"
堆排序：
# 时间复杂度：O(nlogn)
# 原理：堆排序是一种树形选择排序，是对直接选择排序的有效改进。堆的定义如下：具有n个元素的序列（h1,h2,…,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,…,n/2)时称之为堆。
#!/bin/bash
# 堆排序
heap_sort() {
    arr=($@)
    # 建堆
    for ((i=${#arr[@]}/2-1; i>=0; i--))
    do
        heapify $i ${#arr[@]}
    done
    # 堆排序
    for ((i=${#arr[@]}-1; i>=0; i--))
    do
        tmp=${arr[0]}
        arr[0]=${arr[$i]}
        arr[$i]=$tmp
        heapify 0 $i
    done
    echo ${arr[@]}
}
# 堆调整
heapify() {
    start=$1
    end=$2
    root=${arr[$start]}
    while [ $(($start*2+1)) -lt $end ]
    do
        child=$(($start*2+1))
        if [ $child -lt $(($end-1)) -a ${arr[$child]} -lt ${arr[$(($child+1))]} ]
        then
            child=$(($child+1))
        fi
        if [ $root -lt ${arr[$child]} ]
        then
            arr[$start]=${arr[$child]}
            start=$child
        else
            break
        fi
    done
    arr[$start]=$root
}
arr=(5 4 3 2 1)
echo "排序前：${arr[@]}"
echo "排序后：$(heap_sort ${arr[@]})"
选择排序：
# 时间复杂度：O(n^2)
# 原理：选择排序是一种简单直观的排序算法，它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
#!/bin/bash
# 选择排序
selection_sort() {
    arr=($@)
    for ((i=0; i<${#arr[@]}; i++))
    do
        min=$i
        for ((j=$(($i+1)); j<${#arr[@]}; j++))
        do
            if [ ${arr[$j]} -lt ${arr[$min]} ]
            then
                min=$j
            fi
        done
        tmp=${arr[$i]}
        arr[$i]=${arr[$min]}
        arr[$min]=$tmp
    done
    echo ${arr[@]}
}
arr=(5 4 3 2 1)
echo "排序前：${arr[@]}"
echo "排序后：$(selection_sort ${arr[@]})"
快速排序：
# 时间复杂度：O(nlogn)
# 原理：快速排序是对冒泡排序的一种改进，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
#!/bin/bash
# 快速排序
quick_sort() {
    arr=($@)
    __quick_sort 0 $((${#arr[@]}-1))
    echo ${arr[@]}
}
# 快速排序递归函数
__quick_sort() {
    start=$1
    end=$2
    if [ $start -lt $end ]
    then
        i=$start
        j=$end
        base=${arr[$i]}
        while [ $i -lt $j ]
        do
            while [ $i -lt $j -a ${arr[$j]} -ge $base ]
            do
                j=$(($j-1))
            done
            arr[$i]=${arr[$j]}
            while [ $i -lt $j -a ${arr[$i]} -le $base ]
            do
                i=$(($i+1))
            done
            arr[$j]=${arr[$i]}
        done
        arr[$i]=$base
        __quick_sort $start $(($i-1))
        __quick_sort $(($i+1)) $end
    fi
}
arr=(5 4 3 2 1)
echo "排序前：${arr[@]}"
echo "排序后：$(quick_sort ${arr[@]})"
归并排序：
# 时间复杂度：O(nlogn)
# 原理：归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
#!/bin/bash
# 归并排序
merge_sort() {
    arr=($@)
    __merge_sort 0 $((${#arr[@]}-1))
    echo ${arr[@]}
}
# 归并排序递归函数
__merge_sort() {
    start=$1
    end=$2
    if [ $start -lt $end ]
    then
        mid=$((($start+$end)/2))
        __merge_sort $start $mid
        __merge_sort $(($mid+1)) $end
        __merge $start $mid $end
    fi
}
# 合并函数
__merge() {
    start=$1
    mid=$2
    end=$3
    i=$start
    j=$(($mid+1))
    k=0
    tmp=()
    while [ $i -le $mid -a $j -le $end ]
    do
        if [ ${arr[$i]} -lt ${arr[$j]} ]
        then
            tmp[$k]=${arr[$i]}
            i=$(($i+1))
        else
            tmp[$k]=${arr[$j]}
            j=$(($j+1))
        fi
        k=$(($k+1))
    done
    while [ $i -le $mid ]
    do
        tmp[$k]=${arr[$i]}
        i=$(($i+1))
        k=$(($k+1))
    done
    while [ $j -le $end ]
    do
        tmp[$k]=${arr[$j]}
        j=$(($j+1))
        k=$(($k+1))
    done
    for ((i=$start; i<=$end; i++))
    do
        arr[$i]=${tmp[$(($i-$start))]}
    done
}
arr=(5 4 3 2 1)
echo "排序前：${arr[@]}"
echo "排序后：$(merge_sort ${arr[@]})"