快捷導(dǎo)航

shell中的排序算法示例代碼

更新時(shí)間：2021年12月24日 15:19:11 作者：即使不為人所道

本文主要介紹了shell中的排序算法示例代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

冒泡排序法

類似旗袍上涌的動(dòng)作，會(huì)將數(shù)據(jù)在數(shù)組中從小大大或者從大到小不斷的向前移動(dòng)。

基本思想:

冒泡排序的基本思想是對(duì)比相鄰的兩個(gè)元素值，如果滿足條件就交換元素值，把較小的元素移動(dòng)到數(shù)組前面，把大的元素移動(dòng)到數(shù)組后面(也就是交換兩個(gè)元素的位置)，這樣較小的元素就像氣泡一樣從底部上升到頂部。

算法思路

冒泡算法由雙層循環(huán)實(shí)現(xiàn)，其中外部循環(huán)用于控制排序輪數(shù)，一般為要排序的數(shù)組長(zhǎng)度減1次，因?yàn)樽詈笠淮窝h(huán)只剩下一個(gè)數(shù)組元素，不需要對(duì)比，同時(shí)數(shù)組已經(jīng)完成排序了。而內(nèi)部循環(huán)主要用于對(duì)比數(shù)組中每個(gè)相鄰元素的大小，以確定是否交換位置，對(duì)比和交換次數(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ù)更少，所以速度會(huì)快些。

基本思想:

將指定排序位置與其它數(shù)組元素分別對(duì)比，如果滿足條件就交換元素值，注意這里區(qū)別冒泡排序，不是交換相鄰元素，而是把滿足條件的元素與指定的排序位置交換（如從最后一個(gè)元素開(kāi)始排序），這樣排序好的位置逐漸擴(kuò)大，最后整個(gè)數(shù)組都成為已排序好的格式。

#!/bin/bash
array=(77 22 99 1 23 55 11)
echo "老數(shù)組順序?yàn)?${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ù)組的順序?yàn)?${array[@]}"

在這里插入圖片描述

反轉(zhuǎn)排序

以相反的順序把原有數(shù)組的內(nèi)容重新排序。

基本思想:

把數(shù)組最后一個(gè)元素與第一個(gè)元素替換，倒數(shù)第二個(gè)元素與第二個(gè)元素替換，以此類推，直到把所有數(shù)組元素反轉(zhuǎn)替換。

#!/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[*]}"

在這里插入圖片描述

直接插入算法

插入排序，又叫直接插入排序。實(shí)際中，我們玩撲克牌的時(shí)候，就用了插入排序的思想。

基本思想:

在待排序的元素中，假設(shè)前n-1個(gè)元素已有序，現(xiàn)將第n個(gè)元素插入到前面已經(jīng)排好的序列中，使得前n個(gè)元素有序。按照此法對(duì)所有元素進(jìn)行插入，直到整個(gè)序列有序。

#!/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[@]}"
~
~

在這里插入圖片描述

希爾算法

希爾排序也是一種插入排序，它是簡(jiǎn)單插入排序經(jīng)過(guò)改進(jìn)之后的一個(gè)更高效的版本，也稱為縮小增量排序。

基本思想

希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。

1.先選定一個(gè)小于N的整數(shù)gap作為第一增量，然后將所有距離為gap的元素分在同一組，并對(duì)每一組的元素進(jìn)行直接插入排序。然后再取一個(gè)比第一增量小的整數(shù)作為第二增量，重復(fù)上述操作…

2.當(dāng)增量的大小減到1時(shí)，就相當(dāng)于整個(gè)序列被分到一組，進(jìn)行一次直接插入排序，排序完成。

gap越大，數(shù)據(jù)挪動(dòng)得越快；gap越小，數(shù)據(jù)挪動(dòng)得越慢。前期讓gap較大，可以讓數(shù)據(jù)更快得移動(dòng)到自己對(duì)應(yīng)的位置附近，減少挪動(dòng)次數(shù)。

在這里插入圖片描述

#!/bin/bash
array=(8 9 1 7 2 3 5 4)
length=${#array[@]}
echo "原數(shù)組為 ${array[@]}"
#設(shè)長(zhǎng)度的一半為gap初始間隔，每次循環(huán)gap都除以2，直至gap為1結(jié)束循環(huán)
for ((gap=$length/2; gap>0; gap/=2))
do
#因?yàn)間ap為整個(gè)長(zhǎng)度的一半，所以gap到length結(jié)尾包含的元素?cái)?shù)剛好為需要進(jìn)行直接插入算法的個(gè)數(shù)
  for ((i=gap; i<$length; i++))
    do
    #設(shè)一個(gè)第三變量方便直接插入進(jìn)行交換
      temp=${array[$i]}
       #對(duì)距離為gap的元素組進(jìn)行排序，每一輪比較拿當(dāng)前輪次最后一個(gè)元素與組內(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[*]}"

在這里插入圖片描述