您现在的位置是:首页 >技术教程 >Linux shell编程 数组排序算法网站首页技术教程
Linux shell编程 数组排序算法
简介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[@]}"
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。