• 欢迎光临~

Shell脚本之数组排序

开发技术 开发技术 2022-10-29 次浏览

数组排序(使用tr、sort、for)

操作步骤;

  1. 使用tr命令将数组内每个元素之间的空格替换为换行符;
  2. 之后使用sort命令按从小到大重新排序;
  3. 最后使用for循环遍历排序后的元素值。

Shell脚本之数组排序

 

 

冒泡排序

类似气泡上涌的动作,会将数据在数组中从小到大或者从大到小不断的向前移动。

基本思想:

  • 冒泡排序的基本思想是对比相邻的两个元素值,如果满足条件就交换元素值,把较小的元素移动到数组前面,把大的元素移动到数组后面(也就是交换两个元素的位置),这样较小的元素就像气泡一样从底部上升到顶部。

算法思路:

  • 冒泡算法由双层循环实现,其中外部循环用于控制排序轮数,一 般为要排序的数组长度减1次,因为最后一 次循环只剩下一-个数组元素,不需要对比,同时数组已经完成排序了。而内部循环主要用于对比数组中每个相邻元素的大小,以确定是否交换位置,对比和交换次数随排序轮数而减少。

冒泡排序的算法逻辑:


Shell脚本之数组排序

 

 

 第一轮比较5次(数组长度减1),可以确定最后1个元素(元素下标值:数组长度减1)。
 ​
 第二轮比较4次(数组长度减2),可以确定倒数第2个元素(元素下标值:数组长度减2)。
 ​
 第三轮比较3次(数组长度减3),可以确定倒数第3个元素(元素下标值:数组长度减3)。
 ​
 第四轮比较2次(数组长度减4),可以确定倒数第4个元素(元素下标值:数组长度减4)。
 ​
 第五轮比较1次(数组长度减5),可以确定倒数第5个元素(元素下标值:数组长度减5)。
 ​
 #排序的轮数=数组长度减1
 #每轮比较的次数=数组长度减轮数
 #每轮确定的元素,其下标值=数组长度减轮数
 ​
 #外层循环:比较的轮数。一共比较几轮。
 #内层循环:比较的方法。

示例1:将指定数组重新排序

 #!/bin/bash
 ​
 arr=(63 4 24 1 3 15)
 echo "原数组顺序为:${arr[@]}"
 #获取数组的长度
 length=${#arr[@]}
 ​
 #使用冒泡排序
 #定义比较的轮数,比较轮数为数组长度减1,从1开始。
 for ((i=1;i<$length;i++))
 do
 #对比相邻元素,确定元素的位置,较大的值往右放,每轮的比较次数会随着比较轮数的增加而减少。每轮比较次数=数组长度-轮数
 #变量以左边元素为参数
     for ((j=0;j<$length-i;j++))
     do
         #定义左边元素的值
         left=${arr[$j]}
         #定义右边元素的值
         k=$[$j+1]
         right=${arr[$k]}
         #比较两边元素的值,如果左边的值大于右边的值,两个元素就互换
         if [ $left -gt $right ]
         then
             #使用临时变量temp保存左边元素的值
             tmp=$left
             #将右边元素的值赋给左边元素
             arr[$j]=$right
             #将原来的左边元素的值(保存在临时变量temp中)赋给右边元素
             arr[$k]=$tmp
         fi
     done
 done
 echo "排序后数组的顺序为:${arr[@]}"

Shell脚本之数组排序

 

 Shell脚本之数组排序

 

 

示例2:写一个函数,输入任何数组都可以进行排序

 #!/bin/bash
 #写一个冒泡排序的函数,输入任何数组都可以进行排序
 ​
 maopao2 () {
 #将外面的数组值传入函数内,组成新的数组
   newarr=($@)
 #获取数组的长度
   len=${#newarr[@]}
   
 #使用冒泡排序
 #定义比较的轮数,比较的轮数=数组长度-1,从1开始
   for ((i=1;i<$len;i++))
   do
     #比较相邻元素,较大的值向右边移动。每轮比较次数=数组长度-轮数
      for ((j=0;j<$len-i;j++))
      do
         #定义左边元素的值
         left=${newarr[$j]}
         #定义右边元素的值
         k=$[$j+1]
         right=${newarr[$k]}
         #比较两边元素的值,如果左边的值大于右边的值,两个元素就互换
         if [ $left -gt $right ]
         then
             #使用临时变量temp保存左边元素的值
             tmp=$left
             #将右边元素的值赋给左边元素
             newarr[$j]=$right
             #将原来的左边元素的值(保存在临时变量temp中)赋给右边元素
             newarr[$k]=$tmp
         fi
      done
   done
   echo "排序后数组的顺序为:${newarr[@]}"
 }
 ​
 ##### main ########
 ​
 read -p "请输入数组的值,每个值用空格隔开:" arr
 echo "原数组顺序为:${arr[@]}"
 #获取数组的数据列表,作为函数的参数
 maopao2 ${arr[@]}

Shell脚本之数组排序

 

 

直接选择排序

与冒泡排序相比,直接选择排序的交换次数更少,所以速度会快些。

基本思想:

  • 将指定排序位置与其它数组元素分别对比,如果满足条件就交换元素值,注意这里区别冒泡排序,不是交换相邻元素,而是把满足条件的元素与指定的排序位置交换(如从最后一个元素开始排序),这样排序好的位置逐渐扩大,最后整个数组都成为已排序好的格式。

直接选择排序的算法逻辑:

Shell脚本之数组排序

 

 

第一轮:假设当前下标为0的元素值是最大的,依次和右边对比,哪个值更大就继续往后面对比,最后将最大的值放在最后一个元素的位置。

第二轮:假设当前下标为0的元素值是第二大的(即应该放到倒数第二的位置),依次和右边对比,哪个值更大就继续往后面对比,最后将最大的值放在倒数第二个元素的位置。

第三轮:以此类推。

 #如果元素有6个,只需要比较5轮:
 ​
 第一轮:确定下标值为数组长度减1的元素。length-1
 ​
 第二轮:确定下标值为数组长度减2的元素。length-2
 ​
 第三轮:确定下标值为数组长度减3的元素。length-3
 ​
 第四轮:确定下标值为数组长度减4的元素。length-4
 ​
 第五轮:确定下标值为数组长度减4的元素。length-5
 ​
 ​
 #排序的轮数=数组长度减1。
 #每一轮的最后一个元素位置下标=数组长度 - 轮数。

示例:将指定数组重新排序

 #!/bin/bash 
 ​
 arr=(63 4 24 1 3 15)  #定义数组并赋值
 echo "排序前数组的顺序为:${arr[@]}"
 length=${#arr[@]}    #定义一个变量length,将数组长度赋值给它
  
 #使用直接选择排序
 #定义排序的轮数。一般为数组长度减1
 for ((i=1;i<length;i++))
 do
    #先假设第一个元素的值是最大的,第一个元素的下标为0
    index=0
    #用后续元素和假设的最大元素比较,如果比假设的元素值大,则记录这个元素的下标,后续元素就和这个元素比较,最终可以确定当前轮数的最大元素的下标位置
    for ((j=1;j<=length-i;j++))
    do
        if [ ${arr[$j]} -gt ${arr[$index]} ];then
        #当所有元素比较完后,index的值就是当前轮次的最大元素的下标位置
        index=$j
        fi
    done
    #确定完当前轮次的最大元素位置后,就拿这个最大元素和当前轮次的最后一个元素交换位置
    #定义每轮的最后一个元素的下标
    last=$[length - i]
    #先把每轮的最后一个元素的值赋给临时变量temp 
    temp=${arr[$last]}
    #把最大元素的值赋给最后一个元素
    arr[$last]=${arr[$index]}
    #把原来最后一个元素的值赋给原来最大元素,从而实现最大元素和当前轮次的最后一个元素的值交换
    arr[$index]=$temp
 done
 echo "排序后数组的顺序为:${arr[@]}"

Shell脚本之数组排序

 

 

反转排序

以相反的顺序把原有数组的内容重新排序。

基本思想:

  • 把数组最后一个元素与第一个元素进行交换,倒数第二个元素与第二个元素进行交换,以此类推,直到把所有数组元素反转替换。
 #!/bin/bash
 #使用反转排序
 ​
 arr=(63 2 24 1 3 15)
 echo "原数组的排列顺序为:${arr[@]}"  
 #获取数组的长度
 length=${#arr[@]} 
 ​
 #将前面元素的值和倒数元素的值进行交换,倒数的元素的下标会随着前面的元素的下标增加而减少
 #元素的下标从0开始;折半对换,所以是长度除以2;下标值每次加1
 for ((i=0;i<length/2;i++))
 do
    #将第一个下标对应的元素值赋值给临时变量temp
    temp=${arr[$i]}   
    #将最后一个下标对应的元素值赋值给第一个下标对应的元素
    arr[$i]=${arr[$length-1-$i]}
    #再将第一个下标对应的元素值赋值给最后一个下标对应的元素,完成反转
    arr[$length-1-i]=$temp     
 done
 echo "反转排序后的数组顺序为:${arr[@]}"

Shell脚本之数组排序

 

 Shell脚本之数组排序

 

 



程序员灯塔
转载请注明原文链接:Shell脚本之数组排序
喜欢 (0)