数据结构-直接插入排序

浏览数：26 / 时间：2015年06月08日

例如：待排序数组为：7 2 4 1 3 2

第一次排序：2 7 4 1 3 2

第二次排序：2 4 7 1 3 2

第三次排序：1 2 4 7 3 2

第四次排序：1 2 3 4 7 2

第五次排序：1 2 2 3 4 7

程序实现代码如下：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <time.h>
 4 #define MAXSIZE 20
 5 typedef int KeyType;
 6 typedef char InfoType;
 7 
 8 //结构体定义
 9 typedef struct {
10     KeyType key;
11     InfoType otherinfo;
12 }RedType;
13 typedef struct {
14     RedType r[MAXSIZE+1];
15     int length;
16 }SqList;
17 
18 //函数定义
19 void print(SqList *L);
20 void init(SqList *L);
21 void insertSort(SqList *L);
22 
23 //初始化，产生随机数组
24 void init(SqList *L) {
25     int n,i;
26     printf("请输入待排序的元素个数：");
27     scanf("%d",&n);
28     srand(((int)time(0)));//设置随机种子
29     for(i=1; i<=n; i++) {
30         L->r[i].key = rand()%10+1;
31     }
32     L->length = n;
33     printf("随机产生的待排数组为：");
34     print(L);
35 }
36 
37 //输出数组元素
38 void print(SqList *L) {
39     int i;
40     for(i=1; i<=L->length; i++) {
41         printf("%d ",L->r[i].key);
42     }
43     printf("\n");
44 }
45 
46 //进行直接插入排序
47 void insertSort(SqList *L) {
48     int i,j;
49     for(i=2; i<=L->length; i++) {
50         if(L->r[i].key < L->r[i-1].key) {
51             L->r[0] = L->r[i];//设置哨兵
52             L->r[i] = L->r[i-1];
53             for(j=i-2; L->r[0].key<L->r[j].key; --j) {
54                 L->r[j+1] = L->r[j];//记录后移,Lj移动到Lj+1位置------>Lj+1=Lj
55             }
56             /*for(j=i-1; L->r[0].key<L->r[j].key; --j) {
57                 L->r[j] = L->r[j-1];
58             }*/
59             //循环后j=0;
60             L->r[j+1] = L->r[0];//插入正确的位置
61         }
62     }
63 }
64 
65 //主函数
66 int main()
67 {
68     SqList sq;
69     init(&sq);
70     insertSort(&sq);
71     printf("排序之后的数组为：");
72     print(&sq);
73     return 0;
74 }