文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

shell中的排序算法示例代码

2022-06-04 23:56

关注
目录

冒泡排序法

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

基本思想:

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

算法思路

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


#!/bin/bash
array=(112 221 33 55 66 11 25 68)
length="${#array[@]}"
for ((i=1; i<=$length; i++))
do
  for ((j=1; j<=$length-$i; j++))
  do
    first=${array[$j]}
    k=$[$j+1]
    second=${array[$k]}
    if [ $first -gt $second ]
      then
        temp=$first
        array[$j]=$second
        array[$k]=$temp
    fi
  done
done

echo "new_array: ${array[@]}"

在这里插入图片描述

直接选择排序

与冒泡排序相比,直接选择排序的交换次数更少,所以速度会快些。

基本思想:

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


#!/bin/bash
array=(77 22 99 1 23 55 11)
echo "老数组顺序为 ${array[@]}"
length=${#array[@]}

for ((i=1; i<=length; i++))
do
  index=0
  for ((j=1; j<=length-i; j++))
  do
    CURR=${array[$j]}
    MAX=${array[$index]}
    if [ $CURR -gt $MAX ]
      then
        index=$j
    fi
  done
  last=$[ $length - $i ]
  temp=${array[$last]}
  array[$last]=${array[$index]}
  array[$index]=$temp

done

echo "新数组的顺序为 ${array[@]}"

在这里插入图片描述

在这里插入图片描述

反转排序

以相反的顺序把原有数组的内容重新排序。

基本思想:

把数组最后一个元素与第一个元素替换,倒数第二个元素与第二个元素替换,以此类推,直到把所有数组元素反转替换。


#!/bin/bash
array=(1 2 3 4 5 6 7 8 9)
length=${#array[@]}
for ((i=0; i<=length/2; i++))
do
  first=${array[$i]}
  last=${array[$length-$i-1]}
  temp=$first
  array[$i]=$last
  array[$length-$i-1]=$temp
done
echoHNkpd "${array[*]}"

在这里插入图片描述

在这里插入图片描述

直接插入算法

插入排序,又叫直接插入排序。实际中,我们玩扑克牌的时候,就用了插入排序的思想。

基本思想:

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


#!/bin/bash
array=(8 2 9 44 6 28 10)
echo "原数组为 ${array[*]}"
length=${#array[@]}
for ((i=1; i<=$length; i++))
do
  for ((j=0; j<=$i; j++))
    do
      if [[ ${array[$i]} -lt ${array[$j]} ]]
        then
           temp=${array[$i]}
           array[$i]=${array[$j]}
           array[$j]=$temp
      fi
    done
done

echo "新数组为 ${array[@]}"
~
~

在这里插入图片描述

在这里插入图片描述

希尔算法

希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序 。

基本思想

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

1.先选定一个小于N的整数gap作为第一增量,然后将所有距离为gap的元素分在同一组,并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量,重复上述操作…

2.当增量的大小减到1时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成。

gap越大,数据挪动得越快;gap越小,数据挪动得越慢。前期让gap较大,可以让数据更快得移动到自己对应的位置附近,减少挪动次数。

在这里插入图片描述

在这里插入图片描述


#!/bin/bash
array=(8 9 1 7 2 3 5 4)
length=${#array[@]}
echo "原数组为 ${array[@]}"
#设长度的一半为gap初始间隔,每次循环gap都除以2,直至gap为1结束循环
for ((gap=$length/2; gap>0; gap/=2))
do
#因为gap为整个长度的一半,所以gap到length结尾包含的元素数刚好为需要进行直接插入算法的个数
  for ((i=gap; i<$length; i++))
    do
    #设一个第三变量方便直接插入进行交换
      temp=${array[$i]}
       #对距离为gap的元素组进行排序,每一轮比较拿当前轮次最后一个元素与组内其他元素比较,将数组大的往后放
      for((j=i-gap; j>=0&&temp<${array[$j]}; j-=gap))
        do
          array[$j+$gap]=${array[$j]}
        done
      array[$j+$gap]=$temp
    done
done

echo "新的数组为 ${array[*]}"

在这里插入图片描述

在这里插入图片描述

到此这篇关于shell中的排序算法示例代码的文章就介绍到这了,更多相关shell 排序算法 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-人工智能
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯