Shell各种排序方式

目录

冒泡排序

 插入排序

直接选择排序

 反转排序

冒泡排序

冒泡排序，该排序的命名非常形象，即一个个将气泡冒出。冒泡排序一趟冒出一个最大（或最小）值。

#!/bin/bash
#冒泡排序，升序

arr=(63 4 24 1 3 15)
echo "原始的数组列表顺序为: ${arr[@]} "
length=${#arr[@]}
#使用外部循环定义比较轮数，轮数为数组长度减1，且从1开始
for ((a=1;a<length;a++))
do 
   #使用内部循环比较相邻元素，确定元素位置，较大数放后面，且每轮比较次数会随着轮数递减
   #这里内部循环的变量用来表示两个相邻比较元素的前一个元素的下标
   for ((b=0;b<length-a;b++))
   do 
      #定义left变量获取两个相邻比较元素的前一个比较元素的值
      left=${arr[$b]} 
      #定义left变量获取两个相邻比较元素的后一个比较元素的值
      c=$[b+1]
      right=${arr[c]}
         #两个相邻元素的值比较，如果前一个元素的值较大则两个元素互换值
      if [ $left -gt $right ];then
         tmp=$left
         arr[$b]=$right
         arr[$c]=$tmp
      fi      
   done
   
done
echo "排序后的数组顺序为: ${arr[@]}"

1

 2.

 插入排序

插入排序，又叫直接插入排序。实际中，我们玩扑克牌的时候，就用了插入排序的思想。

基本思想：

在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。

但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。

#!/bin/bash
#插入排序，实现升序
arr=(63 4 24 1 5 3)
length=${#arr[@]}
#定义比较轮数，并且a的值用于作为待排序的元素下标
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[@]}"
 

直接选择排序

选择排序，即每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。

代码：

//选择排序(一次选一个数)voidSelectSort(int*a,intn){inti=0;for(i=0;i

时间复杂度：O(N2)O(N^2)O(N2)空间复杂度：O(1)O(1)O(1)

实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。

#直接选择排序，实现升序

arr=(63 4 24 1 3 15)
length=${#arr[@]}
#外部循环定义循环轮数为数组长度减1
for ((a=1;a<length;a++))
do
  #初始定义下标为0的元素的值最大    
  n=0
  #定义内循环变量为从第二个元素下标开始，用于比较当前假设的最大元素的值，并记录最大元素的下标
  for ((b=1;b<=length-a;b++))
  do
      if [ ${arr[$b]} -gt ${arr[$n]} ];then
         n=$b
      fi
  done
  #获取每轮最后一个比较元素的下标
  last=$[length - a]
  #拿最大的元素的值和当前轮数的最后一个比较元素交换值
  tmp=${arr[$last]}
  arr[$last]=${arr[$n]}
  arr[$n]=$tmp
done

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

 反转排序

#!/bin/bash
#反转排序
arr=(10 20 30 40 50 60 70 80)
length=${#arr[@]}
#设置前后两个替换元素中的前面的元素下标的取值范围，从0开始
for ((a=0;a<length/2;a++))
do
   tmp=${arr[$a]}
   arr[$a]=${arr[$length-1-$a]}
   arr[$length-1-$a]=$tmp
done

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