十大经典排序算法之——插入排序

72 阅读 0 评论 48 点赞

我是靠谱客的博主健康花卷，最近开发中收集的这篇文章主要介绍十大经典排序算法之——插入排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

之前已和大家分享过“选择排序”的算法及实现，感兴趣的XDM可以点击下方链接浏览阅读，或点击关注，我们将持续、完整更新整个系列。↓

十大经典排序算法之——选择排序https://blog.csdn.net/xuedaon/article/details/122209124

回到今天的主题：插入排序。

插入排序是一种比较简单直观的排序，算是新手入门级排序，逻辑也容易理解。

在生活中，插入排序也是很常见的，比如说军训站队列的时候教官需要对学生的身高进行一个比较，可能两两比较，可能一排进行比较，混迹在高个子中的矮个子就会被单独拧出来，放回矮个人队伍里，在矮个子里突出的高个子也会插入到高个子行列中，这就算是最基本的插入排序的逻辑。

接下来官方话语进行解释：插入排序实际上就是对未排序的数组进行排序，从第一个数开始遍历，每次遍历最新的数都要从后往前进行比较，找到比它小的数，然后插在它的后面（这里数组顺序为升序），以此类推，直到遍历完最后一个数，排序完成。

有了大概的一个逻辑之后，再来想插入排序的思路就简单多了：

首先，随机定义一个数组，从第一个数开始进行第一次的遍历，这个时候它的前面没有其他的数，所以比较不了，还是勇站第一位。

接下来第二位登场，它需要从当前位置从后往前开始比较，找到比它小的那位数（a[i] > a[i-1]），然后插入到它的后面（如图1-1所示）。

图1-1

数组中每一位数都要进行相同的遍历方式，直到最后一个数比较完（具体遍历过程，由图1-2可见）

图1-2

附完整代码：

#include <stdio.h>
int main()
{
int a[]={4,2,5,3,7,1,0};
int len = sizeof(a)/sizeof(int);
int i = 0,j = 0;
for(i = 1; i < len; i++)
{
//若第 i 个元素大于 i-1 元素则直接插入；反之，需要找到适当的插入位置后在插入。
if(a[i] < a[i-1])   
          {
              j = i-1;
              int x = a[i];
			//采用顺序查找方式找到插入的位置，在查找的同时，
//将数组中的元素进行后移操作，给插入元素腾出空间
              while(j > -1 && x < a[j])               
{
                  a[j+1] = a[j];
                  j--;
              }
              a[j+1] = x;  // c插到正确的位置
          }
     }
     for(j = 0; j < len; j++)
     {
          printf("%dn",a[j]);   // 最后打印一遍数组
     }
return 0;
}