Java知网

  • 首页
  • Spring Boot
  • 面试精选
  • 程序人生
  • 资源
  • 友链
  • 关于我
  1. 首页
  2. Java
  3. 正文

三分钟彻底理解插入排序

2021年5月2日 189点热度 0人点赞 0条评论

基本思想:每一步将一个待排序的数据插入到前面已经排好序的有序序列中,直到插完所有元素为止。

算法实现:直接插入排序是将无序序列中的数据插入到有序的序列中,在遍历无序序列时,首先拿无序序列中的首元素去与有序序列中的每一个元素比较并插入到合适的位置,一直到无序序列中的所有元素插完为止。对于一个无序序列arr{4,6,8,5,9}来说,我们首先先确定首元素4是有序的,然后在无序序列中向右遍历,6大于4则它插入到4的后面,再继续遍历到8,8大于6则插入到6的后面,这样继续直到得到有序序列{4,5,6,8,9}。

  1. 我们用一个变量tmp存放关键字,因为我们先确定第一个元素是暂时有序的,所以tmp存放无序序列的第二个元素,然后i开始也为第二个元素的下标,j则为i-1,因为j要用有序的区域元素来与无序的区域元素比较。那么一开始i=1,tmp=6,j=0,因为6>4,所以6就不用进行插入;然后i向右走,i=2,tmp=arr[2]=8,j=i-1=1,8>6>4也不用插入。

  1. i继续向右走,i=3,tmp=arr[3]=5,j=i-1=2,5<8则要将8给5所在的元素数据,j向左走继续遍历有序区域。

  1. 当j向右走到6时发现6>tmp=5,所以将6给它右边的第一个值(j+1的位置),再继续遍历有序区域,j=0时发现4<5则j+1的位置就是5该在的位置那么就将tmp的值5给j+1的位置的元素的值。

  1. 再继续上面的操作,i最后到9发现比前面有序区域的元素都大,则不用再插入了,这样就得到了一个有序序列{4,5,6,8,9}。

代码实现:

void StraightSort(int *arr,int len) {
    int tmp;
    int i;
    int j;
    for (i = 1;i < len;i++){
        tmp = arr[i];
        for (j = i - 1;j >= 0 && arr[j] > tmp;j--){
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = tmp;
    }
}
作者:RainySouL1994
来源:https://blog.csdn.net/qq_33289077/article/details/90370899

相关文章:

  1. 三分钟彻底理解堆排序
  2. 三分钟彻底理解快速排序
标签: 排序算法
最后更新:2021年9月4日

javatip

这个人很懒,什么都没留下

点赞
< 上一篇
下一篇 >

文章评论

取消回复
搜一搜
扫一扫
    关注公众号
  • 技术干货推送
  • 免费资料领取
  • 定时福利发放
分类
  • Java / 110篇
  • Mysql / 17篇
  • Redis / 10篇
  • Spring Boot / 29篇
  • Spring Cloud / 16篇
  • 消息队列 / 14篇
  • 程序人生 / 21篇
  • 资源 / 3篇
  • 面试 / 23篇
归档
  • 2022年4月 / 1篇
  • 2022年1月 / 1篇
  • 2021年12月 / 9篇
  • 2021年11月 / 2篇
  • 2021年9月 / 10篇
  • 2021年8月 / 4篇
  • 2021年7月 / 2篇
  • 2021年6月 / 10篇
  • 2021年5月 / 18篇
  • 2021年4月 / 75篇
  • 2021年3月 / 78篇

COPYRIGHT © 2021 javatip.cn. ALL RIGHTS RESERVED.

陇ICP备19004310号-2

甘公网安备 62010202003150号