冒泡排序

#Time Complexity O(n^2)
#Space Complexity O(1)
#neighbours change places until a pass makes no swaps:
#the largest element "bubbles up" to the end on every pass
bubbleSort() {
    local -n arr=$1
    local end j tmp swapped
    for ((end = ${#arr[@]}; end > 1; end--)); do
        swapped=false
        for ((j = 1; j < end; j++)); do
            if ((arr[j] < arr[j - 1])); then
                tmp=${arr[j]}
                arr[j]=${arr[j - 1]}
                arr[j - 1]=$tmp
                swapped=true
            fi
        done
        if [[ $swapped == false ]]; then
            break
        fi
    done
}

items=(4 1 5 3 2)

#the sort works in place: a copy keeps items as they are
sortItems=("${items[@]}")
bubbleSort sortItems
#sortItems is (1 2 3 4 5)

#in practice the lines are sorted by sort -n

echo "items is (${items[*]})"
echo "sortItems is (${sortItems[*]})"