shell算法
数组排序冒泡算法:
冒泡排序
类似气泡上涌的动作,会将数据在数组中从小到大或者从大1到小不断的向前移动
基本思想:
冒泡排序的基本思想就是对比相邻的两个元素值。如果满足条件就交换元素值。把较小的元素移动到数组前面,把大的元素移动到数组后面。(也就是交换两个元素的位置),这样较小的元素就像气泡一样从底部上升到顶部
算法思路:(比较轮数=数组长度减去1)
冒泡算法由双层循环实现,其中外部循环由于控制排序轮数,一般为要排序的数组长度减一,因为最后一次循环只剩下一个数组元素,不需要对比,同时数组已经完成排序了。而内部循环主要用于对比数组中每个相邻元素的·1大小,以确定是否交换位置。对比和交换次数随着排序轮数而减少。 实验:正序汽包算法
!#/bin/bash
arr=(63 4 24 1 3 15)
echo "初始数组的顺序是: ${arr[*]}"
length=${#arr[@]}
#定义比较多的轮数,从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 -gt $second ]
then
temp=$first
arr[$b]=$second
arr[$c]=$temp
#这步用于采用第三个临时变量来交换$first 和$second
fi
done
done
echo "排序后的数组顺序是: ${arr[@]}"
实验:反序气泡算法
!#/bin/bash
arr=(63 4 24 1 3 15)
echo "初始数组的顺序是: ${arr[*]}"
length=${#arr[@]}
#定义比较多的轮数,从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
temp=$first
arr[$b]=$second
arr[$c]=$temp
#这步用于采用第三个临时变量来交换$first 和$second
fi
done
done
echo "排序后的数组顺序是: ${arr[@]}"
直接选择排序
与冒泡排序相比,直接选择排序的交换次数更少。所以速度会更快一些
基本思想:
将指定的排序位置与其他元素分别对比,如果满足交换条件就交换元素值,注意这里区别冒泡排序,不是交换相邻元素,而是把满足条件的元素与指定的排序位置交换(如从最后一个元素开始排序),这样排序好的位置逐渐扩大,最后整个数组都成为已排序好的格式。 实验:正序直接选择排序
#!/bin/bash
arr=(63 4 24 1 3 15)
echo "初始数组的序列是: ${arr[@]}"
length=${#arr[@]}
#定义比较的轮数,还是数组长度减1
for ((a=1; a<length; a++))
do
#定义当前比较轮种拥有最大值的元素下标的初始值为0
index=0
#定义当前比较轮的除了第一个元素的其他比较元素的下标的范围,会随着比较轮数的增加而减少,从1开始
for ((b=1; b<=length-a; b++))
do
#获取其他比较元素的值
other=${arr[$b]}
#获取当前比较轮中最大元素的值
max=${arr[$index]}
#通过拿其他比较元素的值与最大元素的值来做比较,获取当前比较轮的最大元素的下标
if [ $other -gt $max ]
then
index=$b
fi
done
#拿当前比较轮的最大元素的值与当前比较轮的最后一个元素·的值进行交换
#获取当前比较轮的最后一个元素的下标
last=$[$length - $a]
#使用临时变量temp获取当前轮最后一个元素的值
temp=${arr[$last]}
#把当前轮最大的元素的值赋给最后一个元素
arr[$last]=${arr[$index]}
#把原来最后一个元素的值赋给原来最大的元素
arr[$index]=$temp
done
echo "排序后的数组顺序是: ${arr[@]}"
实验:反序直接选择排序
#!/bin/bash
arr=(63 4 24 1 3 15)
echo "初始数组的序列是: ${arr[@]}"
length=${#arr[@]}
#定义比较的轮数,还是数组长度减1
for ((a=1; a<length; a++))
do
#定义当前比较轮种拥有最大值的元素下标的初始值为0
index=0
#定义当前比较轮的除了第一个元素的其他比较元素的下标的范围,会随着比较轮数的增加而减少,从1开始
for ((b=1; b<=length-a; b++))
do
#获取其他比较元素的值
other=${arr[$b]}
#获取当前比较轮中最大元素的值
max=${arr[$index]}
#通过拿其他比较元素的值与最大元素的值来做比较,获取当前比较轮的最大元素的下标
if [ $other -lt $max ]
then
index=$b
fi
done
#拿当前比较轮的最大元素的值与当前比较轮的最后一个元素·的值进行交换
#获取当前比较轮的最后一个元素的下标
last=$[$length - $a]
#使用临时变量temp获取当前轮最后一个元素的值
temp=${arr[$last]}
#把当前轮最大的元素的值赋给最后一个元素
arr[$last]=${arr[$index]}
#把原来最后一个元素的值赋给原来最大的元素
arr[$index]=$temp
done
echo "排序后的数组顺序是: ${arr[@]}"
反转排序
以相反的顺序把原油数组的内容重新排序
基本思想:
把数组租后一个元素与第一个元素替换。倒数第二个元素与第二个元素替换,一次以此类推,直到把所有数组元素反转替换。
#!/bin/bash
arr=(10 20 30 40 50 60 70 )
echo "原始的数据值顺序是: ${arr[@]}"
length=${#arr[@]}
#拿折半的前几个数作为参照物
for ((a=0; a<length/2; a++))
do
#获取折半前面的数值
front=${arr[$a]}
#获取折半后面的数值
backend=${arr[$length - $a - 1 ]}
#前后值进行交换
temp=$front
arr[$a]=$backend
arr[$length - $a - 1]=$temp
done
echo "排序后数组的顺序是: ${arr[@]}"
直接插入算法
插入排序:又叫直接插入排序。实际中,我们玩扑克牌的时候,就用了插入排序的思想
基本思想:在待排序的元素中,假设前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
waiter=${arr[$a]}
finish=${arr[$b]}
#升序排序,所以如果待排序的元素值小于全面已经排序好的元素的值,则进行交换,小的往前面放,大的往后放
if [ $waiter -lt $finish ]
then
temp=$waiter
arr[$a]=$finish
arr[$b]=$temp
fi
done
done
echo "排序后的数组顺序是 : ${arr[@]}"
实验:反序直接插入算法
#!/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
waiter=${arr[$a]}
finish=${arr[$b]}
#升序排序,所以如果待排序的元素值小于全面已经排序好的元素的值,则进行交换,小的往前面放,大的往后放
if [ $waiter -gt $finish ]
then
temp=$waiter
arr[$a]=$finish
arr[$b]=$temp
fi
done
done
echo "排序后的数组顺序是 : ${arr[@]}"