内部排序->插入排序->直接插入排序

文字描述:

将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表

示意图:

算法分析:

时间复杂度为n*n，辅助存储为1，是稳定的排序方法。

代码实现:

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 #define EQ(a, b) ((a) == (b))
 5 #define LT(a, b) ((a) <  (b))
 6 #define LQ(a, b) ((a) <= (b))
 7 
 8 #define MAXSIZE 20
 9 typedef int KeyType;
10 typedef int InfoType;
11 typedef struct{
12     KeyType key;
13     InfoType otherinfo;
14 }RedType;
15 
16 typedef struct{
17     RedType r[MAXSIZE+1];
18     int length;
19 }SqList;
20 
21 void InsertSord(SqList *L){
22     int i = 0, j = 0;
23     for(i=2; i<=L->length; i++){
24         if(LT(L->r[i].key, L->r[i-1].key)){
25             L->r[0] = L->r[i];
26             L->r[i] = L->r[i-1];
27             for(j=i-2; LT(L->r[0].key, L->r[j].key); --j){
28                 L->r[j+1] = L->r[j];
29             }
30             L->r[j+1] = L->r[0];
31         }
32     }
33 }
34 
35 void PrintList(SqList L){
36     int i = 0;
37     printf("len:%d; data:", L.length);
38     for(i=1; i<=L.length; i++){
39         printf("%d ", L.r[i].key);
40     }
41     printf("
");
42     return ;
43 }
44 
45 
46 int  main(int argc, char *argv[])
47 {
48     if(argc < 2){
49         return -1;
50     }
51     SqList L;
52     int i = 0;
53     for(i=1; i<argc; i++){
54         if(i>MAXSIZE)
55             break;
56         L.r[i].key = atoi(argv[i]);
57     }
58     L.length = (i-1);
59 
60     InsertSord(&L);
61     PrintList(L);
62     return 0;
63 }

直接插入排序

运行：

~$ ./a.out 3 5 7 3 1 9 6 4
len:8; data:1 3 3 4 5 6 7 9