排序算法-----插入排序

排序算法-----插入排序Insretsort

插入排序算法属于速度比较快速的高级排序算法，其基本思想是从第一个数开始进行循环，在他后面的数单独提出来放在一边，然后于他前面的数字相比，若前面的数字大于这个选出来的数字，则将前面的数字向后移动一个单位，直到遇到比选出来的数字小时，将这个选出来的数字放在小数字之后，实现的是插入操作。经过一次循环后，所有的数字的顺序就确定了。

具体的实例如下：
4，8，3，6，5，7，2，1，9
（1）首先我们保持第一个数字不动，从第二个数字开始，将他取出来temp=8，然后在找他的前一个元素，进行比较，4<8，则4不用移动，将8赋给m+1位置，j++。
4，8，3，6，5，7，2，1，9 -------------------------------结果：4，8，3，6，5，7，2，1，9
　　j 　　　　　　　　　　    temp=8
m
（2）然后将j位置上数字，即第三个数字，将他取出来temp=3，然后在找他的前一个元素，进行比较，8>3，则8向后移动一位，即m+1的位置上，同时m--
4，8，3，6，5，7，2，1，9 -------------------------------结果：4，3，8，6，5，7，2，1，9
　　　 j 　　　　　　　　　 temp=3
　 m
取出m位置的元素与temp比较，若大于m位置元素后移动一位，否则将temp的值赋值给m位置后面一位，跳过m的循环即可。若取出来的元素是序列的最小元素，则m位置的需要一直向后移动，同时执行m--操作，直到m<0为止；
4，3，8，6，5，7，2，1，9 -------------------------------结果：3，4，8，6，5，7，2，1，9
j temp=3
m
（3）以此类推即可；
3，4，8，6，5，7，2，1，9 -------------------------------结果：3，4，6，8，5，7，2，1，9
　　　　　j temp=6
m
（4）
3，4，6，8，5，7，2，1，9 -------------------------------结果：3，4，5，6，8，7，2，1，9
　　　　　　 j temp=5
　　　　 m
（5）
3，4，5，6，8，7，2，1，9 -------------------------------结果：3，4，5，6，7，8，2，1，9
　　　　　　　　j temp=7
　　　　　　 m
（6）
3，4，5，6，7，8，2，1，9 -------------------------------结果：2，3，4，5，6，7，8，1，9
　　　　　　　　　 j temp=2
　　　　　　　  m
（7）
2，3，4，5，6，7，8，1，9 -------------------------------结果：1，2，3，4，5，6，7，8，9
　　　　　　　　　　　 j temp=1
　　　　　　　　　 m
（8）
1，2，3，4，5，6，7，8，9 -------------------------------结果：1，2，3，4，5，6，7，8，9
　　　　　　　　　　　　   j temp=9
　　　　　　　　　　    m
总结：
我们发现j循环的次数比序列的个数少1，所以j<n即可；
m循环的每一次都是从j-1开始的，最小的时候可以为0，m的范围是-1<m,不断地做m--操作；
我在写代码的时候的遇到的两个问题：
1、是忘记在某个数找到自己位置的时候需要跳出m的循环
解决方式：使用break；
2、m的取值上，最开始我让m=j，发现操作时m的变化容易弄混
解决办法：让m=j-1，看着清晰；

代码如下：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 int Insertsort(int *a, int k);
 4 int main() {
 5     int b[9] = { 4,8,3,6,2,1,5,9,7 };
 6     printf("排序前的序列如下：\n");
 7     for (int i = 0; i < 9; i++) {
 8         if (i!=8){
 9             printf("%d,",b[i]);
10         }
11         else {
12             printf("%d\n", b[i]);
13         }
14     }
15     Insertsort(b, 9);
16     printf("排序后的序列如下：\n");
17     for (int i = 0; i < 9; i++) {
18         if (i != 8) {
19             printf("%d,", b[i]);
20         }
21         else {
22             printf("%d\n", b[i]);
23         }
24     }
25     system("pause");
26 }
27 
28 int Insertsort(int *a, int n) {
29     for (int j = 1; j < n; j++) {
30         int temp = a[j];
31         for (int m = j - 1; m > -1; m--) {
32             if (a[m] > temp) {
33                 a[m + 1] = a[m];
34                 if (m == 0) {
35                     a[m] = temp;       //对于a[0]的赋值，勿忘
36                 }
37             }
38             else {
39                 a[m + 1] = temp;
40                 break;
41             }
42         }
43     }
44 }

排序算法-----插入排序

推荐阅读