Bash : 氣泡排序
氣泡排序是非常基礎的排序演算法,本文我們看看在 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 指令碼程式設計指南》