9、 Bubble sort

Nine 、 Bubble sort

Array sorting algorithm : Bubble sort

It's like a bubble rising , Will move the data in the array from small to large or from large to small .

The basic idea :

The basic idea of bubble sorting is to compare the values of two adjacent elements , Exchange element values if conditions are met , Move the smaller elements to the front of the array , Move large elements to the back of the array ( That is, to exchange the positions of two elements ), So the smaller elements rise from the bottom to the top like bubbles .

Algorithm ideas

The bubble algorithm is implemented by a two-layer loop , The external loop is used to control the number of sorting rounds , Generally, the length of the array to be sorted minus 1 Time , Because there's only one array element left in the last loop , There's no need to compare , At the same time, the array has finished sorting . The inner loop is mainly used to compare the size of each adjacent element in the array , To determine whether to swap positions , The number of comparisons and exchanges decreases with the number of sorting rounds .

Define interactive shell, Prompt the user continuously for 3 A digital , then , Three numbers are bigger than size , Last but not least echo From large to small （ Tips ： Be careful if Statement and judgment ）

[[email protected] ~]# vim 13.sh
[[email protected] ~]# chmod +x 13.sh 
[[email protected] ~]# sh 13.sh 
 Please enter an integer ：34
 Please enter an integer ：65
 Please enter an integer ：78
 The sorted data is :34,65,78
================================================================================
[[email protected] ~]# cat 13.sh 
#! /bin/bash
read -p ' Please enter an integer ：' num1
read -p ' Please enter an integer ：' num2
read -p ' Please enter an integer ：' 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 " The sorted data is :$num1,$num2,$num3"

Swap places ：

[[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[*]}                      Array ：        1      2
                                    Subscript ：        0      1
# Swap places 
 tmp=`echo ${arr[0]}`              #tmp=1 ;tmp Assignment subscript 0 The element value of 
arr[0]=`echo ${arr[1]}`            # Subscript 0 Replace the element value of with the subscript 1 The element value of 
arr[1]=$tmp                        # Subscript 1 The element value of is tmp The element value of 
echo ${arr[*]}                     # The final output 

Array sorting ：

[[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 Assign the length of the array 

# Define the number of comparison rounds , The number of comparison rounds is the length of the array minus 1, from 1 Start 
for ((i=1;i<$it;i++))
do
# Determine the position of the comparison element , Compare two adjacent elements , Put the larger one back , The number of comparisons decreases with the number of rounds 
   for ((j=0;j<$it-i;j++))
	do   
# Define the value of the first element 
      first=${array[$j]}
# Define the value of the second element 
      k=$[$j+1]
      second=${array[$k]}
# Compare the value of the first element with that of the second element , If the first element is larger than the second element, it is interchangeable 
   if [ $first -gt $second ];then
# Save the first element value to a temporary variable 
       tmp=$first
# Assign a value to the first element 
       array[$j]=$second
# Put the temporary variable （ That is, the original value of the first element ） Assign to the second element 
       array[$k]=$tmp
   fi
   done
done
# Output sorted array 
echo "new_array:${array[*]}"

Let users define any number by themselves in an interactive way , Finally, sort from small to large

[[email protected] opt]# vim yspx.sh
[[email protected] opt]# sh yspx.sh 
 Whether to store elements [yes/no]:yes
 Please enter the first 1 Elements ：12
 Whether to store elements [yes/no]:yes
 Please enter the first 2 Elements ：45
 Whether to store elements [yes/no]:yes
 Please enter the first 3 Elements ：15
 Whether to store elements [yes/no]:yes    
 Please enter the first 4 Elements ：98
 Whether to store elements [yes/no]:yes
 Please enter the first 5 Elements ：56
 Whether to store elements [yes/no]:no
 Input element sorting ：12 15 45 56 98
=================================================================================
[[email protected] opt]# cat yspx.sh 
#!/bin/bash
k=0
while true
 do
read -p " Whether to store elements [yes/no]:" doing
	if [ $doing == no ];then
	break
        
	elif [ $doing == yes ];then
	read -p " Please enter the first $[$k+1] Elements ：" 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 " Input element sorting ：${array[*]}"