在Bash中使用冒泡排序对数组进行排序

先决条件： 气泡排序

给定一个数组，arr使用bash脚本按升序对数组进行排序。

例如：

Input : 9 7 2 5Output :Array in sorted order :2 5 7 9

方法：

对于排序，数组气泡排序是最简单的技术。气泡排序的工作原理是，如果相邻元素的顺序错误，则交换它们。

例子：

Given array - (9, 7, 2, 5)After first iteration - (7, 2, 5, 9)After second iteration - (2, 5, 7, 9)and so on...

这样，通过将较大的元素放在数组的末尾来对数组进行排序。

# Sorting the array in Bash # using Bubble sort# Static input of Arrayarr=(10 8 20 100 12)echo "Array in original order"echo ${arr[*]}# Performing Bubble sort for ((i = 0; i<5; i++))do        for((j = 0; j<5-i-1; j++))    do            if [ ${arr[j]} -gt ${arr[$((j+1))]} ]        then            # swap            temp=${arr[j]}            arr[$j]=${arr[$((j+1))]}              arr[$((j+1))]=$temp        fi    donedoneecho "Array in sorted order :"echo ${arr[*]}

输出：

Array in sorted order :8 10 12 20 100

优化实施： 即使数组已排序，上述函数也始终运行O（n^2）次。如果内部循环没有引起任何交换，可以通过停止算法来优化。

n=5arr=(10 8 20 100 12) echo "Original array is: ${arr[*]}";flag=1;for (( i = 0; i < $n-1; i++ ))do    flag=0;    for ((j = 0; j < $n-1-$i; j++ ))    do        if [[ ${arr[$j]} -gt ${arr[$j+1]} ]]        then            temp=${arr[$j]};            arr[$j]=${arr[$j+1]};            arr[$j+1]=$temp;            flag=1;        fi    done    if [[ $flag -eq 0 ]]; then          break;    fi

输出：

Original array is: 10 8 20 100 12Final sorted Array is 8 10 12 20 100

最差和平均情况时间复杂度： O（n*n）。最坏的情况发生在数组被反向排序时。

最佳情况时间复杂度 ：O（n）。最好的情况发生在数组已排序时。

辅助空间： O（1）

边界情况： 当元素已经排序时，冒泡排序所需的时间最短（n的顺序）。

分类到位： 对

稳定的： 对