您现在的位置是:首页 >技术教程 >Linux shell编程 数组排序算法网站首页技术教程

Linux shell编程 数组排序算法

低温热源 2024-06-17 06:01:02
简介Linux shell编程 数组排序算法

 冒泡排序

循环对比相邻的元素,交换较大元素到后面的位置

  • 大循环根据列表中存在的元素数量循环n-1次,保证所有元素都能被排序完成
    • 小循环从前向后遍历,循环一次循环范围减少一位(由于后面的已经排列完成无需再比较)
    • 小循环每次循环向后移一位并进行比较,当遇到比自己小的数交换位置,保证每轮都能获取到最大的数排列到队尾

#!/bin/bash
MAOPAO() {
arr=($@)
#获取数组的长度
length=${#arr[@]}

#外层循环用来定义比较轮数,比较轮数为数组长度减1,且从1开始
for ((a=1; a<length; a++))
do
    #内层循环用来确定比较元素的位置,较比相邻两个元素,较大的元素往后移,并且比较次数会随着比较轮数的增加而减少
    for ((b=0; b<length-a; b++))
    do
        #获取相邻两个元素的前面元素的值
        first=${arr[$b]}
        #获取相邻两个元素的后面元素的值
        second=${arr[$b+1]}
        #比较两个相邻元素的值大小,如果前面元素的值较大,则与后面元素交换位置
        if [ $first -gt $second ];then
            #使用临时变量保存前面元素的值,实现两个相邻元素交换位置
            tmp=$first
            arr[$b]=$second
            arr[$b+1]=$tmp
            fi
    done
done

echo "冒泡排序后的数组的值为: ${arr[@]}"
}

##### main #####
read -p "请输入一组列表:" num
array=($num)
echo "旧数组的值为: ${array[@]}"

MAOPAO ${array[@]}
[xue@xue ~]$ sh maopao.sh
请输入一组列表:10 5 9 41 62 4 2 84 6 42 66
旧数组的值为: 10 5 9 41 62 4 2 84 6 42 66
冒泡排序后的数组的值为: 2 4 5 6 9 10 41 42 62 66 84

直接选择排序

与冒泡排序对比,直接选择排序的交换次数更少,速度更快

每轮选择一个最大的元素交换至队尾排列完成的数字之前   

        或是   

每轮选取一个最小的元素交换至队首排列完成的数字之后

  • 大循环根据列表中存在的元素数量循环n-1次,保证所有元素都能被排序完成
    • 小循环从前向后遍历,循环一次循环范围减少一位(由于后面的已经排列完成无需再比较)
    • 小循环遍历数组,初始最大元素变量下标为0,当遇到的数字比当前变量数字大时更新变量(保证变量中一直为最大值下标),当循环到范围结束(未被排序完成的数字最后一位)根据最大元素变量下标该轮选取的最大元素未被排序的最后一位交换

 

 

#!/bin/bash
XUANZHE(){
arr=($@)

#获取数组的长度
length=${#arr[@]}

#定义外层循环的轮数,为数组长度减1,且从1开始
for ((a=1;a<$length;a++))
do
    #初始最大元素下标
    index=0

    #内层循环定义未被排序完成需要排序的元素范围
    #每轮循环后由于排序完成一位,下标范围-1
    for ((b=1;b<=$length-$a;b++)) #第二个到最后一个元素
    do
        #通过比较,获取当前轮数中最大元素的下标
        if [ ${arr[$index]} -lt ${arr[$b]} ]
        then
            index=$b
        fi
    done

    #本轮选取的最大元素本轮 交换 本轮未被排序完成的最后一位
    last=$[length - a] #(最后一个元素下标每轮向前)
    tmp=${arr[$last]}
    arr[$last]=${arr[$index]}
    arr[$index]=$tmp
done
echo "排序后的数组的值为: ${arr[@]}"
}


##### main #####
read -p "请输入一组列表: " num
array=$num

echo "排序前的数组值为: ${array[@]}"

XUANZHE ${array[@]}
[xue@xue ~]$ sh xuanze.sh
请输入一组列表: 10 5 9 41 62 4 2 84 6 42 66
排序前的数组值为: 10 5 9 41 62 4 2 84 6 42 66
排序后的数组的值为: 2 4 5 6 9 10 41 42 62 66 84

直接插入排序

依次选择未被排序的元素,与已排序元素对比

若比当前对比的已排序元素小,插入到该元素之前,保证已排序元素有序排序

 

#!/bin/bash
CHARU(){
arr=($@)

#获取数组的长度
length=${#arr[@]}
#外层循环定义待排序的元素下标位置 
for  ((a=1; a<length; a++))
do
   #内层定义已排好的序列的元素下标位置范围
   for ((b=0; b<a; b++))
   do
     #将待排序的元素和前面已经排序好的元素依次比较,较小的数交换到已排好序的元素位置,较大的数放到待排序的元素位置
     if [ ${arr[$a]} -lt ${arr[$b]} ]
     then
          tmp=${arr[$a]}
          arr[$a]=${arr[$b]}
          arr[$b]=$tmp
     fi
  done
done

echo "排序后数组的值为: ${arr[@]}"
}

##### main #####
read -p "请输入一组列表: " num
array=$num

echo "排序前的数组值为: ${array[@]}"

CHARU ${array[@]}

反向排序

数组为 1 2 3 4 5 6 7 8 9 0 

过程大致为

10交换 29交换 38交换 47交换 56交换

#!/bin/bash

arr=(1 2 3 4 5 6 7 8 9)
echo "排序前数组的值为: ${arr[@]}"

length=${#arr[@]}

for ((a=0; a<length/2; a++))
do
   tmp=${arr[$a]}

   #获取当前轮数的最后一个元素下标,会随着轮数的增加而减少
   last=$[length-1-a]
   arr[$a]=${arr[$last]}
   arr[$last]=$tmp

done

echo "排序后数组的值为: ${arr[@]}"

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。