shell中的排序算法示例代碼
冒泡排序法
類似旗袍上涌的動作，會將數(shù)據(jù)在數(shù)組中從小大大或者從大到小不斷的向前移動。
基本思想:
冒泡排序的基本思想是對比相鄰的兩個元素值，如果滿足條件就交換元素值，把較小的元素移動到數(shù)組前面，把大的元素移動到數(shù)組后面(也就是交換兩個元素的位置)，這樣較小的元素就像氣泡一樣從底部上升到頂部。
算法思路
冒泡算法由雙層循環(huán)實現(xiàn)，其中外部循環(huán)用于控制排序輪數(shù)，一般為要排序的數(shù)組長度減1次，因為最后一次循環(huán)只剩下一個數(shù)組元素，不需要對比，同時數(shù)組已經(jīng)完成排序了。而內(nèi)部循環(huán)主要用于對比數(shù)組中每個相鄰元素的大小，以確定是否交換位置，對比和交換次數(shù)隨排序輪數(shù)而減少。
#!/bin/bash
array=(112 221 33 55 66 11 25 68)
length="${#array[@]}"
for ((i=1; i<=$length; i++))
do
for ((j=1; j<=$length-$i; j++))
do
first=${array[$j]}
k=$[$j+1]
second=${array[$k]}
if [ $first -gt $second ]
then
temp=$first
array[$j]=$second
array[$k]=$temp
fi
done
done
echo "new_array: ${array[@]}"
直接選擇排序
與冒泡排序相比，直接選擇排序的交換次數(shù)更少，所以速度會快些。
基本思想:
將指定排序位置與其它數(shù)組元素分別對比，如果滿足條件就交換元素值，注意這里區(qū)別冒泡排序，不是交換相鄰元素，而是把滿足條件的元素與指定的排序位置交換（如從最后一個元素開始排序），這樣排序好的位置逐漸擴大，最后整個數(shù)組都成為已排序好的格式。
#!/bin/bash
array=(77 22 99 1 23 55 11)
echo "老數(shù)組順序為 ${array[@]}"
length=${#array[@]}
for ((i=1; i<=length; i++))
do
index=0
for ((j=1; j<=length-i; j++))
do
CURR=${array[$j]}
MAX=${array[$index]}
if [ $CURR -gt $MAX ]
then
index=$j
fi
done
last=$[ $length - $i ]
temp=${array[$last]}
array[$last]=${array[$index]}
array[$index]=$temp
done
echo "新數(shù)組的順序為 ${array[@]}"
反轉排序
以相反的順序把原有數(shù)組的內(nèi)容重新排序。
基本思想:
把數(shù)組最后一個元素與第一個元素替換，倒數(shù)第二個元素與第二個元素替換，以此類推，直到把所有數(shù)組元素反轉替換。
#!/bin/bash
array=(1 2 3 4 5 6 7 8 9)
length=${#array[@]}
for ((i=0; i<=length/2; i++))
do
first=${array[$i]}
last=${array[$length-$i-1]}
temp=$first
array[$i]=$last
array[$length-$i-1]=$temp
done
echo "${array[*]}"
直接插入算法
插入排序，又叫直接插入排序。實際中，我們玩撲克牌的時候，就用了插入排序的思想。
基本思想:
在待排序的元素中，假設前n-1個元素已有序，現(xiàn)將第n個元素插入到前面已經(jīng)排好的序列中，使得前n個元素有序。按照此法對所有元素進行插入，直到整個序列有序。
#!/bin/bash
array=(8 2 9 44 6 28 10)
echo "原數(shù)組為 ${array[*]}"
length=${#array[@]}
for ((i=1; i<=$length; i++))
do
for ((j=0; j<=$i; j++))
do
if [[ ${array[$i]} -lt ${array[$j]} ]]
then
temp=${array[$i]}
array[$i]=${array[$j]}
array[$j]=$temp
fi
done
done
echo "新數(shù)組為 ${array[@]}"
~
~
希爾算法
希爾排序也是一種插入排序，它是簡單插入排序經(jīng)過改進之后的一個更高效的版本，也稱為縮小增量排序 。
基本思想
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。
1.先選定一個小于N的整數(shù)gap作為第一增量，然后將所有距離為gap的元素分在同一組，并對每一組的元素進行直接插入排序。然后再取一個比第一增量小的整數(shù)作為第二增量，重復上述操作…
2.當增量的大小減到1時，就相當于整個序列被分到一組，進行一次直接插入排序，排序完成。
gap越大，數(shù)據(jù)挪動得越快；gap越小，數(shù)據(jù)挪動得越慢。前期讓gap較大，可以讓數(shù)據(jù)更快得移動到自己對應的位置附近，減少挪動次數(shù)。
#!/bin/bash
array=(8 9 1 7 2 3 5 4)
length=${#array[@]}
echo "原數(shù)組為 ${array[@]}"
#設長度的一半為gap初始間隔，每次循環(huán)gap都除以2，直至gap為1結束循環(huán)
for ((gap=$length/2; gap>0; gap/=2))
do
#因為gap為整個長度的一半，所以gap到length結尾包含的元素數(shù)剛好為需要進行直接插入算法的個數(shù)
for ((i=gap; i<$length; i++))
do
#設一個第三變量方便直接插入進行交換
temp=${array[$i]}
#對距離為gap的元素組進行排序，每一輪比較拿當前輪次最后一個元素與組內(nèi)其他元素比較，將數(shù)組大的往后放
for((j=i-gap; j>=0&&temp<${array[$j]}; j-=gap))
do
array[$j+$gap]=${array[$j]}
done
array[$j+$gap]=$temp
done
done
echo "新的數(shù)組為 ${array[*]}"
到此這篇關于shell中的排序算法示例代碼的文章就介紹到這了,更多相關shell 排序算法 內(nèi)容請搜索本站以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持本站！
版權聲明：本站文章來源標注為YINGSOO的內(nèi)容版權均為本站所有，歡迎引用、轉載，請保持原文完整并注明來源及原文鏈接。禁止復制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務器上建立鏡像，否則將依法追究法律責任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學習參考，不代表本站立場，如有內(nèi)容涉嫌侵權，請聯(lián)系alex-e#qq.com處理。
關注官方微信