直接插入排序（简单插入排序）

　　给定一个数字串：2 6 7 8 9 3 2 3 4

　　按从小到大的顺序排列输出

　　首先把第一个数字放到一个小组里：（2）6 7 8 9 3 2 3 4 

　　让后从第二个数字开始往小组里插入

　　比如第二个数字6，比2大，随意直接不动放在5后面就可以：（2 6） 7 8 9 3 2 3 4 

　　7 8 9同样：（2 6 7 8 9） 3 2 3 4

　　数字 3 与小组里的数字比较（从右往左），比 3 大的全部往右移动一格

　　移动后：2 （）6 7 8 9 2 3 4

　　原来的数字 3 被覆盖 ， 再填入上一行的括号中就好

　　2 3 6 7 8 9 2 3 4    

　　（2 3 6 7 8 9 ）2 3 4继续比较入小组。。。

特殊说明：

我们建立一个数组array[11]，一般数据区域为【1，10】闭区间

因为我们可以把替换是用的中间变量设置位array[0]，这样就不用再创建一个变量了（下文有实例）

 

代码如下：

  1. #include<stdio.h>
  2.  
  3. typedef int keytype;
  4. //简单插入排序
  5. void insertsort(keytype k[] , int n)
  6. {
  7.     int j;
  8.     for (size_t i =2 ; i <= n; i++)
  9.     {
  10.         k[0] = k[i];//k[0]为中间变量用来储存k[i]
  11.         j = i-1;
  12.         while (j>0 && k[j] > k[0])//组外元素与组内元素逐一比较
  13.         {
  14.             k[j+1] = k[j--];//组外元素比组内的这个元素小，组内的这个元素就后退一格
  15.         }
  16.         k[j+1] = k[0];//在这个位置，前面比自己小，后面比自己大，刚刚好落户，哈哈
  17.     }
  18. }
  19. #define MAX 100
  20. int main()
  21. {
  22.     int c;
  23.     int i = 1;
  24.     int k[MAX];
  25.     //读取一个数字串
  26.     printf("请输入一串无序数字：");
  27.     while ((c = getchar())!=\'\n\')
  28.     {
  29.         k[i++] = c-\'0\';
  30.     }
  31.     if (c==\'\n\')
  32.     {
  33.         k[i] = \'\0\';
  34.     }
  35.     //排序并打印排序结果
  36.     insertsort(k,i-1);
  37.     printf("这串数字从小到大为：");
  38.     for (size_t count = 1; count <= i-1; count++)
  39.     {
  40.         printf("%d",k[count]);
  41.     }
  42.     return 0;
  43. }

　　

运行结果:

 

版权声明：本文为jerryleesir原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/jerryleesir/p/13405785.html