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

文章目录

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

算法描述

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

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

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

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

后面的牌以此类推插入正确的位置。

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

在这里插入图片描述
实现代码:

1#include <stdio.h> 2const int N=6; 3void InsertSort(int *r,int n); 4void Output(int r[],int n);//输出数组的n个元素 5int main(void) 6{ 7 int a[]={5,2,4,6,1,3}; 8 printf("排序前的序列为:"); 9 Output(a,N); 10 printf("\n"); 11 InsertSort(a,N); 12 printf("排序后的序列为:"); 13 Output(a,N); 14 return 0; 15} 16void InsertSort(int *r,int n) 17{ 18 int x; 19 for(int i=1;i<n;i++)//默认r[0]看做是一个有序序列,从r[1]扫描到r[N-1]元素依次把无序元素插入到有序序列中 20 { 21 x=r[i];//从无序序列中找到r[i]位置时,前面元素可能向后移动,使用临时变量x存放待插入元素,因为有序序列会调整,向后移动 22 int j=i-1;//j记录有序序列最后一个元素下标,即j记录每个待插入元素开始扫描有序序列元素的下标 23 while(j>=0&&x<r[j])//当待插入元素x小于有序序列的其中一个元素,则该有序序列中的一个元素赋值到后一个下表中,同时有序序列下标前移一位 24 { 25 r[j+1]=r[j]; 26 j--; 27 } 28 r[j+1]=x;//将待插入元素x赋值给while循环比较的元素下标 29 printf("第%d趟排序:插入元素%d后,有序区间变化:",i,x); 30 Output(r,N); 31 printf("\n"); 32 } 33 34} 35void Output(int r[],int n) 36{ 37 for(int i=0;i<n;i++) 38 { 39 printf("%-4d",r[i]); 40 } 41 printf("\n"); 42} 43

输出:
在这里插入图片描述

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

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

代码交流 2021