排序演算法
- 一、冒泡排序
- 1.1 基本思想
- 1.2 演算法思路
- 1.3 示例
- 二、直接選擇排序
- 2.1 基本思想
- 2.2 示例
- 三、反轉排序
- 3.1 基本思想
- 3.2 示例
一、冒泡排序
類似氣泡上涌的動作，會將資料在陣列中從小到大或者從大到小不斷的向前移動
1.1 基本思想
冒泡排序的基本思想是對比相鄰的兩個元素值，如果滿足條件就交換元素值，把較小的元素移動到陣列前面，把大的元素移動到陣列后面(也就是交換兩個元素的位置) ，這樣較小的元素就像氣泡一樣從底部上升到頂部，
1.2 演算法思路
冒泡演算法由雙層回圈實作，其中外部回圈用于控制排序輪數，一般為要排序的陣列長度減1次，因為最后一次回圈只剩下一個陣列元素，不需要對比，同時陣列已經完成排序了，而內部回圈主要用于對比陣列中每個相鄰元素的大小，以確定是否交換位置，對比和交換次數隨排序輪數而減少，
1.3 示例
arr=(54 3 1233 -4 135 31 1)
echo "原陣列為：${arr[*]}"
length=${#arr[*]}
for ((a=1;a<$length;a++))
do
for ((b=0;b<$length-a;b++))
do
if [ ${arr[$b]} -gt ${arr[$[$b+1]]} ]
then
temp=${arr[$b]}
arr[$b]=${arr[$[$b+1]]}
arr[$[$b+1]]=$temp
fi
done
done
echo "新陣列為：${arr[*]}"
二、直接選擇排序
與冒泡排序相比，直接選擇排序的交換次數更少，所以速度更快
2.1 基本思想
將指定排序位置與其他陣列元素分別對比，如果滿足條件就交換元素值，注意這里區別冒泡排序，不是交換相鄰元素，而是把滿足條件的元素與指定的排序位置交換（如從最后一個元素開始排序），這樣排序好的位置逐漸擴大，最后整個陣列都成為已排序好的格式，
2.2 示例
arr=(25 31 2 45 123 312 4)
echo "原陣列為：${arr[*]}"
length=${#arr[*]}
for ((a=1;a<$length;a++))
do
index=0
for ((b=1;b<=$length-a;b++))
do
if [ ${arr[$b]} -gt ${arr[$index]} ];then
index=$b
fi
done
temp=${arr[$length-$a]}
arr[$length-$a]=${arr[$index]}
arr[$index]=$temp
done
echo "新陣列為：${arr[*]}"
三、反轉排序
以相反的順序把原有陣列的內容重新排序
3.1 基本思想
把陣列最后一個元素與第一個元素替換，倒數第二個元素與第二個元素替換，以此類推，直到把所有的陣列元素反轉替換完
3.2 示例
arr=(10 20 30 40 50 60)
echo "原陣列為：${arr[*]}"
length=${#arr[*]}
for ((a=0; a<$length/2; a++))
do
temp=${arr[$a]}
arr[$a]=${arr[$lenqth-$a-1]}
arr[$length-$a-1]=$temp
done
echo "新陣列為：${arr[*]}"
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/240565.html
標籤：其他