【数组排序算法】

---

一、数组排序算法

1、冒泡排序算法

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

1.1、图形解释

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

1.2、冒泡算法的脚本写法

使用函数来进行对数组内部值的排序

#!/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 -gt $second ]then#使用临时变量保存前面元素的值，实现两个相邻元素交换位置tmp=$firstarr[$b]=$secondarr[$c]=$tmpfidone
doneecho "冒泡排序后的数组的值为: ${arr[@]}"
}##### main #####
read -p "请输入一组列表: " numarray=$num
echo "排序前的数组的值为: ${array[@]}"MAOPAO ${array[@]}

实现了自动调整数组的排序

二、直接选择排序

基本思想:
将指定排序位置与其它数组元素分别对比，如果满足条件就交换元素值，注意这里区别冒泡排序，不是交换相邻元素，而是把满足条件的元素与指定的排序位置交换(如从最后一个元素开始排序)，这样排序好的位置逐渐扩大，最后整个数组都成为已排序好的格式

解释:
假设第一个数字为最大的，让这个假设最大的数字与后面的数字挨个比较

1.1、动态图解

1.2、直接选择排序算法的脚本编写

使用函数来编写直接选择排序的脚本编写

#!/bin/bash
XUANZHE(){
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]} ]theni=$bfi
done#获取当前轮数的最后一个元素的下标last=$[length - a]#先用临时变量获取当前轮数的最后一个元素的值tmp=${arr[$last]}#将最大元素的值赋给当前轮数的最后一个元素arr[$last]=${arr[$i]}#将临时变量的值，即原最后一个元素的值作交换arr[$i]=$tmpdone
echo "排序后的数组的值为: ${arr[@]}"
}##### main #####
read -p "请输入一组列表: " num
array=$numecho "排序前的数组值为: ${array[@]}"XUANZHE ${array[@]}

三、直接插入排序

1.1、基本思想：

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

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

1.2、动态图解

依次与元素比较，如果后面的值大于小于前面的值就向前面插入，依次比较

1.3、直接插入排序的算法脚本编写

#!/bin/bash
CHARU(){
arr=($@)#获取数组的长度
#使用#命令来查看这个数组的所有下标
length=${#arr[@]}
#外层循环定义待排序的元素下标位置 
for  ((a=1; a<length; a++))
do#内层定义已排好的序列的元素下标位置范围for ((b=0; b<a; b++))do#将待排序的元素和前面已经排序好的元素依次比较，较小的数会交换到已排好序的元素位置，较大的数会放到待排序的元素位置if [ ${arr[$a]} -lt ${arr[$b]} ]thentmp=${arr[$a]}arr[$a]=${arr[$b]}arr[$b]=$tmpfidone
doneecho "排序后数组的值为: ${arr[@]}"
}##### main #####
read -p "请输入一组列表: " num
array=$numecho "排序前的数组值为: ${array[@]}"CHARU ${array[@]}

四、反向序列算法

1.1、反向序列算法的脚本编写

#!/bin/basharr=(1 2 3 4 5 6 7 8 9)
echo "排序前数组的值为: ${arr[@]}"length=${#arr[@]}for ((a=0; a<length/2; a++))
dotmp=${arr[$a]}#获取当前轮数的最后一个元素下标，会随着轮数的增加而减少last=$[length-1-a]arr[$a]=${arr[$last]}arr[$last]=$tmpdoneecho "排序后数组的值为: ${arr[@]}"