排序

定义结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define MAXSIZE 20 

typedef int KeyType;

typedef char InfoType[10];

typedef struct {
    KeyType key;
    InfoType otherinfo;
}RedType;

typedef struct {
    RedType r[MAXSIZE + 1];
    int length;
}SqList;

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertSort(SqList &L){
    int j;
    for (int i = 2; i <= L.length; i++) {
       if(L.r[i].key < L.r[i - 1].key){
           L.r[0] = L.r[i];
           L.r[i] = L.r[i - 1];
           for (j = i - 2; L.r[0].key < L.r[j].key; j--) {
               L.r[j + 1] = L.r[j];
           }
           L.r[j + 1] = L.r[0];
       }
    }
}

折半插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void BInsertSort(SqList &L){
    int i, j;
    for(i = 2; i <= L.length; i++){
        L.r[0] = L.r[i];
        int Low = 1, High = i - 1, Mid;
        while(Low <= High){
            Mid = (Low + High) / 2;
            if(L.r[0].key < L.r[Mid].key) High = Mid - 1;
            else Low = Mid + 1;
        } 
        for(j = i - 1; j >= High + 1; j--) L.r[j + 1] = L.r[j];
        L.r[High + 1] = L.r[0];
    }
}