C语言笔记：插入排序法精讲

分手后的思念是犯贱 2023-06-06 08:25 0阅读 0赞

### 文章目录 ###

*  算法描述
 *  关于插入排序法的稳定性问题

# 算法描述 #

插入排序总的思维来讲，就是每一趟将一个待排序的元素，按照其值的大小插入到有序序列的合适位置上，使有序序列长度增加1，直到所有元素全部插入完成。

我们可以举一个形象的例子，比如我们玩扑克牌斗地主时，每次从牌堆中抓一张牌，是不是需要按顺序插入到已有牌（从小到大排好了）序列中，方便我们抓完牌之后，出牌，出顺子，连子等等。

假设只有6张牌，从上到下分别是5，2，4，6，1，3，只有一个玩家就是你，现在模拟一下这些牌到你手上变成有序序列的过程，右手一张一张摸牌，左手拿好所有摸完的牌：

*  右手抓第一张牌5时，左手上没有任何牌，无所谓顺序，直接放到左手就好，但这一张牌可以看做就是一个有序序列
 *  右手抓第二张牌2时，需要和左手拿的牌号为5的牌比较，按从下到大的顺序排好，此时左手拿的牌从左到右分别是2，5
 *  右手抓第三张牌4时，需要和左手拿的牌2,5比较，按从小到大的顺序插入适当的位置，此时左手拿的牌从左到右分别是2，4，5
 *  …  
    后面的牌以此类推插入正确的位置。

由于下面的代码中6个数是存放在下标连续的数组中，所以不可能在两个相邻下标中插入第一下标存放数据，只能对相邻下标的后一个下标向后移动一个下标，给待插入数"腾出"空位，如果相邻下标的后一个下标后面还有元素，则其后元素需要全部后移一个下标，一直到后面没有需要移动的元素为止。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70]  
实现代码：

#include <stdio.h>
    const int N=6;
    void InsertSort(int *r,int n);
    void Output(int r[],int n);//输出数组的n个元素
    int main(void)
    { 
     int a[]={ 5,2,4,6,1,3};
     printf("排序前的序列为：");
     Output(a,N);
     printf("\n");
     InsertSort(a,N);
     printf("排序后的序列为：");
     Output(a,N);
     return 0; 
    } 
    void InsertSort(int *r,int n)
    { 
     int x;
     for(int i=1;i<n;i++)//默认r[0]看做是一个有序序列，从r[1]扫描到r[N-1]元素依次把无序元素插入到有序序列中 
     { 
      x=r[i];//从无序序列中找到r[i]位置时，前面元素可能向后移动，使用临时变量x存放待插入元素，因为有序序列会调整，向后移动
      int j=i-1;//j记录有序序列最后一个元素下标，即j记录每个待插入元素开始扫描有序序列元素的下标
      while(j>=0&&x<r[j])//当待插入元素x小于有序序列的其中一个元素，则该有序序列中的一个元素赋值到后一个下表中，同时有序序列下标前移一位 
      { 
       r[j+1]=r[j];
       j--; 
      } 
      r[j+1]=x;//将待插入元素x赋值给while循环比较的元素下标 
      printf("第%d趟排序：插入元素%d后，有序区间变化：",i,x);
      Output(r,N);
      printf("\n"); 
     } 
     
    }
    void Output(int r[],int n)
    { 
     for(int i=0;i<n;i++)
     { 
      printf("%-4d",r[i]);
     }
     printf("\n");
    }

输出：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 1]

# 关于插入排序法的稳定性问题 #

因为每趟确定待排序元素x的位置时，while（j>=0&&x<r\[j\]）这个循环条件成立时，r\[j\]才向后移动，而当x==r\[j\]时，不进入while循环进行后移操作，待插入元素仍在r\[j\]后面，所以插入排序算法是稳定的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70]: /images/20230601/d9e550059b2848c7aecaa0a0b996a63b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 1]: /images/20230601/c2f31354a3fd46f896fdba0b0c7214b4.png