Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

Bash : 冒泡排序

sparkdev 2019-02-01 13:20:00 阅读数:177 评论数:0 点赞数:0 收藏数:0

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

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

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

用 for 循环实现冒泡

准备一个数组(Bash 数组相关的内容请参考《Bash : 索引数组》一文):

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 命令》一文。
再运行一次,就能看到正确结果了:

用 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" -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[*]}"

参考:
《高级 Bash 脚本编程指南》

版权声明
本文为[sparkdev]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/sparkdev/p/10345498.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领