一，冒泡排序法

image.png

#!/bin/bash
# 功能描述：通过简单的数字比较演示冒泡算法

# 使用数组保存用户输入的9个随机数
for i in {1..9}
do
  read -p "请输入数字：" tmp
  if echo $tmp |grep -qP "\D"; then
    echo "您输入的不是数字"
    exit
  fi
  num[$i]=$tmp
done
echo "您输入的数字序列为：${num[@]}"

# 冒泡排序
# 使用i控制进行几轮比较，使用j控制每轮比较的次数
# 对于9个数字而言，需要进行8轮比较，每进行一轮后，下一轮就可以少比较1次
for ((i=1;i<=8;i++));do
  echo "第${i}轮前，数字序列为：${num[@]}"
  for ((j=1;j<=$[9-i];j++));do
    echo "第${i}轮第${j}次前，数字序列为：${num[@]}"
    if [ ${num[j]} -gt ${num[j+1]} ]; then
      echo "本轮产生了交换, ${num[j]} <-> ${num[j+1]}"
      tmp=${num[j]}
      num[j]=${num[j+1]}
      num[j+1]=$tmp
    fi
  done
done
echo "经过排序后的数字序列为：${num[@]}"

根据进程所占物理内存的大小对进程进行排序(使用冒泡法)

#!/bin/bash
#功能描述：根据进程所占物理内存的大小对进程进行排序

tmpfile="/tmp/procs_mem_$$.txt"
echo $tmpfile
ps --no-headers -eo comm,rss > $tmpfile

bubble() {
  local i j
  local len=$1
  for ((i=1;i<=$[len-1];i++));do
    for ((j=1;j<=$[len-i];j++));do
      if [ ${mem[j]} -gt ${mem[j+1]} ];then
        tmp=${mem[j]}
        mem[j]=${mem[j+1]}
        mem[j+1]=$tmp
        tmp=${name[j]}
        name[j]=${name[j+1]}
        name[j+1]=$tmp
      fi
    done
  done
  echo "排序后进程序列："
  echo "---------------------------------"
  echo "${name[@]}"
  echo "---------------------------------"
  echo "${mem[@]}"
  echo "---------------------------------"
}

i=1
while read proc_name proc_mem
do
  name[$i]=$proc_name
  mem[$i]=$proc_mem
  let i++
done < $tmpfile
rm -rf $tmpfile
bubble ${#mem[@]}

二，快速排序法

image.png

#!/bin/bash
#功能描述：采用分治思想改进快速排序算法

# 初始化一个数组
num=(15 66 897 27 105 698 1234)

# 定义一个可以递归调用的快速排序函数
quick_sort() {
  # 先判断需要进行比较的数字个数，$1是数组最左边的坐标，$2是数组最右边的坐标
  # 左边的坐标要小于右边的坐标，否则表示需要排序的数字只有一个，不需要排序
  if [ $1 -ge $2 ]; then
    return
  fi
  # 定义局部变量，base为基准数字，这里选择的是最左边的数字num[$1]
  # i表示左边的坐标，right表示右边的坐标(也可以使用i和j表示左右坐标)
  local base=${num[$1]}
  local left=$1
  local right=$2

  # 在要排序的数字序列中，比基准数大的数字放右边，比基准数字小的数字放左右
  while [ $left -lt $right ]; do
    # right向左移动，查找比基准数(base)小的元素
    while [[ ${num[right]} -ge $base && $left -lt $right ]]; do
      let right--
    done
    # left向右移动，查找比基准数(base)大的元素
    while [[ ${num[left]} -le $base && $left -lt $right ]]; do
      let left++
    done
    # 将left坐标元素和right坐标元素交换
    if [ $left -lt $right ]; then
      local tmp=${num[$left]}
      num[$left]=${num[right]}
      num[$right]=$tmp
    fi
  done

  # 将基准数字与left坐标元素交换
  num[$1]=${num[left]}
  num[left]=$base

  # 递归调用快速排序算法，对i左边的元素进行快速排序
  quick_sort $1 $[left-1]
  # 递归调用快速排序算法，对i右边的元素进行快速排序
  quick_sort $[left+1] $2
}

# 调用函数对数组进行排序，排序后输出数组的所有元素
quick_sort 0 ${#num[@]}
echo ${num[*]}

三，插入排序法

image.png

#!/bin/bash
# 功能描述： 插入排序算法演示，升序排序

for x in {1..5}; do
  read -p "请输入随机整数：" tmp
  num[$x]=$tmp
done

for ((i=1;i<=5;i++)); do
  tmp=${num[i]}
  j=$[i-1]
  while [[ $j -ge 0 && $tmp -lt ${num[j]} ]]; do
    num[j+1]=${num[j]}
    num[j]=$tmp
    let j--
  done
done
echo ${num[@]}

四，计数排序法

image.png

#!/bin/bash
# 功能描述： 计数排序算法，版本2

num=(2 6 983 678 345 23 99 23 124)

max=${num[0]}
for i in `seq $[${#num[@]}-1]`; do
  [ ${num[i]} -gt $max ] && max=${num[i]}
done
for i in `seq 0 $max`; do
  count[$i]=0
done

for i in `seq 0 $[${#num[@]}-1]`; do
  let count[${num[i]}]++
done

for i in `seq 0 $[${#count[@]}-1]`; do
  for j in `seq ${count[i]}`; do
    echo -n "$i "
  done
done
echo