Shell编程之排序

目录

一、冒泡排序

二、选择排序

三、插入排序

基本思想：

 四、反转排序

基本思想：

五、睡眠排序

六、希尔排序

基本思想：

举例

---

一、冒泡排序

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

#!/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]}
    #获取相邻两个元素的后面元素的值
    c=$[b + 1]
    second=${arr[$c]}
    #比较两个相邻元素的值大小，如果前面元素的值较大，则与后面元素交换位置
    if [ $first -lt $second ];then
      #使用临时变量保存前面元素的值，实现两个相邻元素交换位置
      tmp=$first
      arr[$b]=$second
      arr[$c]=$tmp
    fi
  done
done
 
echo "冒泡排序后的数组的值为：${arr[@]}"
 
}
 
#### main ####
read -p "请输入一组列表：" num
 
array=($num)
echo "旧数组的值为：${array[@]}"
 
MAOPAO ${array[@]}

二、选择排序

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

#!/bin/bash

arr=(63 4 24 1 3 15)
echo "排序前的数组的值为:${arr[@]}"
length=${#arr[@]}

#外层循环定义排序的轮数，为数组长度减1，且从1开始
for ((a=1; a<length; a++));do
  #每轮比较的初始最大元素的下标，从0开始，即第一个元素
  i=0
  #内层循环定义用于与当前最大元素作比较的元素下标范围，从1开始，且每轮比较的最后一个元素下标会随着轮数怎加而减少
  for ((b=1; b<=length-a; b++));do
    #通过比较，获取当前轮数中最大元素的下标
    if [ ${arr[$i])} -lt ${arr[$b]} ];then
      i=$b
    fi
  done
  #获取当前轮数的最后一个元素的下标
  last=$[length - a]
  #先用临时变量获取当前轮数的最后一个元素的值
  tmp=$(arr[$last])
  #将最大元素的值赋给当前轮数的最后一个元素
  arr[$last]=${arr[$i]}
  #将临时变量的值，即原最后一个元素的值交换
  arr[$i]=$tmp
done

三、插入排序

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

基本思想：

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

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

#!/bin/bash

arr=(63 4 24 1 3 15)
echo "排序前数组的值为:${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[@]}"

 四、反转排序

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

基本思想：

把数组最后一个元素与第一个元素替换，例数第二个元素与第二个元素替换，以此类推，直到把所有数组元素反转替换

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

五、睡眠排序

根据睡眠可以使输出按顺序排序

go () {
    sleep `echo $1*0.01 | bc`
    echo $1
}
a=(3 7 5 9 50 25 4 6 1 89)
echo "初始数组为【${a[@]}】"
for i in ${a[@]}; do
    go $i &
done
sleep 1

六、希尔排序

希尔排序，又称缩小增量法

基本思想：

1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…

2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成

answer：gap越大，数据挪动得越快；gap越小，数据挪动得越慢。前期让gap较大，可以让数据更快得移动到自己对应的位置附近，减少挪动次数

举例

#!/bin/bash
array=(7 6 8 3 1 5 2 4)
echo ${array[*]}
length=${#array[*]}

#把距离为gap的元素编为一个组，扫描所有组，每次循环减少增量
for ((gap=$length/2; gap>0; gap/=2))
do
    for ((i=gap; i<$length; i++))
    do

	  temp=${array[$i]}
	  #对距离为gap的元素组进行排序，每一轮比较拿当前轮次最后一个元素与组内其他元素比较，将数组大的往后放
	  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 ${array[*]}