九、冒泡排序

九、冒泡排序

数组排序算法:冒泡排序

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

基本思想:

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

算法思路

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

定义交互式shell，连续提示用户输入3个数字，然后，三个数字比大小，最后要求echo 从大到小排列（提示：注意if语句及判断）

[[email protected] ~]# vim 13.sh
[[email protected] ~]# chmod +x 13.sh 
[[email protected] ~]# sh 13.sh 
请输入一个整数：34
请输入一个整数：65
请输入一个整数：78
排序后数据为:34,65,78
================================================================================
[[email protected] ~]# cat 13.sh 
#! /bin/bash
read -p '请输入一个整数：' num1
read -p '请输入一个整数：' num2
read -p '请输入一个整数：' num3

tmp=0

if [ $num1 -gt $num2 ];then
        tmp=$num1
        num1=$num2
        num2=$tmp
fi
if [ $num1 -gt $num3 ];then
        tmp=$num1
        num1=$num3
        num3=$tmp
fi
if [ $num2 -gt $num3 ];then
        tmp=$num2
        num2=$num3
        num3=$tmp
fi
echo "排序后数据为:$num1,$num2,$num3"

交换位置：

[[email protected] opt]# vim jhwz.sh
[[email protected] opt]# sh jhwz.sh
1 2
2 1
[[email protected] opt]# cat jhwz.sh
#!/bin/bash
arr=(1 2)
echo ${arr[*]}                     数组：        1      2
                                   下标：        0      1
#交换位置
 tmp=`echo ${arr[0]}`              #tmp=1 ；tmp赋值下标0的元素值
arr[0]=`echo ${arr[1]}`            #将下标0的元素值替换为下标为1的元素值
arr[1]=$tmp                        #将下标1的元素值为tmp的元素值
echo ${arr[*]}                     #最后输出

数组排序：

[[email protected] opt]# vim szpx.sh
[[email protected] opt]# sh szpx.sh 
old_array:90 70 60 40 50 30
new_array:30 40 50 60 70 90
================================================================================
[[email protected] opt]# cat szpx.sh 
#!/bin/bash
array=(90 70 60 40 50 30)
echo "old_array:${array[*]}"
it=${#array[*]}      #it赋值数组的长度

#定义比较轮数，比较轮数为数组长度减1，从1开始
for ((i=1;i<$it;i++))
do
#确定比较元素的位置，比较相邻两个元素，较大的往后放，比较次数随比较轮数而减少
   for ((j=0;j<$it-i;j++))
	do   
#定义第一个元素的值
      first=${array[$j]}
#定义第二个元素的值
      k=$[$j+1]
      second=${array[$k]}
#比较第一个元素与第二个元素的值，如果第一个元素比第二个元素大就互换
   if [ $first -gt $second ];then
#把第一个元素值保存到临时变量中
       tmp=$first
#把第二个元素值赋给第一个元素
       array[$j]=$second
#把临时变量（也就是第一个元素原值）赋给第二个元素
       array[$k]=$tmp
   fi
   done
done
#输出排序后的数组
echo "new_array:${array[*]}"

使用交互的方式让用户自行定义任意多个数字，最后从小到大进行排序

[[email protected] opt]# vim yspx.sh
[[email protected] opt]# sh yspx.sh 
是否存入元素[yes/no]:yes
请输入第1个元素：12
是否存入元素[yes/no]:yes
请输入第2个元素：45
是否存入元素[yes/no]:yes
请输入第3个元素：15
是否存入元素[yes/no]:yes    
请输入第4个元素：98
是否存入元素[yes/no]:yes
请输入第5个元素：56
是否存入元素[yes/no]:no
输入元素排序：12 15 45 56 98
=================================================================================
[[email protected] opt]# cat yspx.sh 
#!/bin/bash
k=0
while true
 do
read -p "是否存入元素[yes/no]:" doing
	if [ $doing == no ];then
	break
        
	elif [ $doing == yes ];then
	read -p "请输入第$[$k+1]个元素：" ys
	array[$k]=$ys
    let k++
    fi
done

cd=${#array[*]}
for ((i=1;i<$cd;i++))
do
	for ((j=0;j<$cd-i;j++))
	do
       first=${array[$j]}
       x=$[$j+1]
       second=${array[$x]}
		if [ $first -gt $second ];then
                 tmp=$first
                 array[$j]=$second
                 array[$x]=$tmp
		fi
done
done
echo "输入元素排序：${array[*]}"