Bash : 冒泡排序 - 好文

冒泡排序是非常基础的排序算法，本文我们看看在 Bash 脚本中如何写冒泡排序。本文的演示环境为 ubuntu 16.04。

冒泡排序的简要描述如下：

* 通过连续的比较对数组中的元素进行排序
* 比较两个相邻的元素，如果顺序不对，就交换这两个元素的位置
* 当第一轮比较结束之后，最 "重" 的元素就会被移动到最底部
* 当第二轮比较结束之后，第二 "重" 的元素就会被移动到次底部的位置
* 这意味着每轮比较不需要比较之前已经 "沉淀" 好的数据
* 如果有 n 个元素，则一共执行 n-1 轮比较
用 for 循环实现冒泡

准备一个数组(Bash 数组相关的内容请参考《Bash : 索引数组
<https://www.cnblogs.com/sparkdev/p/7152164.html>》一文)：
declare -a myArr=(10 1 30 13 2 22)
然后来主备一个交换数组元素的函数：
# 定义函数 exchangeEle() 交换数组中两个元素的位置 exchangeEle() { # 使用临时变量保存数组元素 local temp
=${myArr[$1]} # 交换元素的位置 myArr[$1]=${myArr[$2]} myArr[$2]=$temp return }
下面通过一个经典的两层循环来完成排序：
# 获取数组的长度 arrlen=${#myArr[@]} # 通过 for 循环对数组排序，注意此时是以字符串来比较的 for (( last =
$arrlen ;last > 1 ; last-- )) do for (( i = 0 ; i < last - 1 ; i++ )) do [[ "
${myArr[$i]}" > "${myArr[$((i+1))]}" ]] && exchangeEle $i $((i+1)) done done
这就 OK 了，跑跑看：

好吧，数字被作为字符串来比较了。修正这个问题非常简单，把比较的代码换成下面的就可以了：
[[ "${myArr[$i]}" -gt "${myArr[$((i+1))]}" ]] && exchangeEle $i $((i+1))
关于 Bash 中的比较操作，请参考《Bash : test 命令
<https://www.cnblogs.com/sparkdev/p/7666889.html>》一文。
再运行一次，就能看到正确结果了：

用 while 循序实现冒泡

下面我们来介绍使用 while 循序的版本。这次我们按字母序来排列数组中存放的国家名称：
myArr=(Netherlands Ukraine Zaire Turkey Russia Yemen Syria \ Brazil Argentina
Nicaragua Japan Mexico Venezuela Greece England)
这里我们使用了转义符 \ 将数组元素的值放在不同的行上，这样可以避免行中的内容过长。具体的代码如下：
# 从索引 0 开始列出整个数 echo "The order of the original data in the array:" echo "
${myArr[*]}" # 获取数组的长度，并用来控制循环的次数。 n=${#myArr[@]} echo "Start bubbling sort:"
while [ "$n" -gt 1 ] # 执行 n-1 轮外部循环。 do index=0 # 内部循环时的数组元素索引，在每轮循环开始之前需要重置。
while [ "$index" -lt $(expr $n - 1) ] # 开始内部循环。 do if [[ ${myArr[$index]} >
${myArr[$(expr $index + 1)]} ]] then exchangeEle $index $(expr $index + 1) #
交换数组元素位置。fi let "index += 1" done # 内部循环结束。 let "n -= 1" # 外部循环计数减 1。 #
输出每轮排序后的结果。echo "${myArr[*]}" done # 外部循环结束。 echo "Sorted data order:" echo "
${myArr[*]}"
同样是两层循环，算法完全一样，只不过是写法有一点点不同。为了显示排序的过程，这次输出了每轮排序后的中间结果：

demo 代码

下面是本文中 demo 的完整代码：
#!/bin/bash # bubble.sh, 本例主要用来演示索引数组的排序 # 冒泡排序的简要描述如下: # 通过连续的比较对数组中的元素进行排序 #
比较两个相邻的元素，如果顺序不对，就交换这两个元素的位置 # 当第一轮比较结束之后，最"重" 的元素就会被移动到最底部 # 当第二轮比较结束之后，第二 "重"
的元素就会被移动到次底部的位置 # 这意味着每轮比较不需要比较之前已经"沉淀" 好的数据 # 一共执行 n-1 轮比较 # 定义函数
exchangeEle() 交换数组中两个元素的位置 exchangeEle() { # 使用临时变量保存数组元素 local temp=${myArr[$1
]} # 交换元素的位置 myArr[$1]=${myArr[$2]} myArr[$2]=$temp return } declare -a myArr=(
10 1 30 13 2 22) # 从索引 0 开始列出整个数组 echo "The order of the original data in the
array:" echo "${myArr[*]}" # 获取数组的长度 arrlen=${#myArr[@]} # 通过 for
循环对数组排序，注意此时是以字符串来比较的for (( last = $arrlen ; last > 1 ; last-- )) do for (( i =
0 ; i < last - 1 ; i++ )) do [[ "${myArr[$i]}" > "${myArr[$((i+1))]}" ]] &&
exchangeEle $i $((i+1)) done done echo "Sorted data order as string:" echo "
${myArr[*]}" # 通过 for 循环对数组排序，这次是作为整数来比较 for (( last = $arrlen ; last > 1 ; last
-- )) do for (( i = 0 ; i < last - 1 ; i++ )) do [[ "${myArr[$i]}" -gt "
${myArr[$((i+1))]}" ]] && exchangeEle $i $((i+1)) done done echo "Sorted data
order as number:" echo "${myArr[*]}" myArr=(Ukraine Zaire Russia Yemen Syria \
Argentina Japan Mexico Greece) #这里我们还使用转义符 \ 将数组元素的值放在不同的行上，这样可以避免行中的内容过长。 # 从索引
0 开始列出整个数 echo "The order of the original data in the array:" echo "${myArr[*]}"
# 获取数组的长度，并用来控制循环的次数。 n=${#myArr[@]} echo "Start bubbling sort:" while [ "$n"
-gt1 ] # 执行 n-1 轮外部循环。 do index=0 # 内部循环时的数组元素索引，在每轮循环开始之前需要重置。 while [ "$index"
-lt $(expr $n - 1) ] # 开始内部循环。 do if [[ ${myArr[$index]} > ${myArr[$(expr
$index +1)]} ]] then exchangeEle $index $(expr $index + 1) # 交换数组元素位置。 fi let "
index += 1" done # 内部循环结束。 let "n -= 1" # 外部循环计数减 1。 # 输出每轮排序后的结果。 echo "
${myArr[*]}" done # 外部循环结束。 echo "Sorted data order:" echo "${myArr[*]}"
参考：
《高级 Bash 脚本编程指南》

热门工具换一换