2023年浙江大学研究生入学考试

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#define NotFound 0

Position BinarySearch(List Tb1, ElementType K) {
    Position left, right, mid;
    left = 1;
    right = Tb1 -> Last;
    while(left <= right) {
        mid = (left + right) / 2;
        if(K < Tb1 -> Data[mid]) right = mid - 1;
        else if(K > Tb1 -> Data[mid]) left = mid + 1;
        else return mid;
    }
    return NotFound;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

typedef int ElementType;
typedef int Position; /* 数组下标 */
typedef struct LNode* PtrToLNode;

struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 记录线性表的最后一个元素所在位置(初始 -1)  */
};

typedef PtrToLNode List;

List MakeEmpty(){
    List L;
    L = (List)malloc(sizeof(struct LNode));
    L -> Last = -1;
    return L;
}

Position Find(List L, ElementType X) {
    Position i = 0;
    while(i <= L -> Last && L -> Data[i] != X) 
        i ++;
    if(i > L -> Last) return ERROR;
    return i;
}

/* 在为序 i 前插入一个新元素 */
bool Insert(List L, ElementType X, int i) {
    Position j;

    if(L -> Last == MAXSIZE - 1) {
        printf("表满");
        return false;
    }

    if(i < 1 || i > L -> Last + 2) {
        printf("位序不合法");
        return false;
    }

    for(j = L -> Last; j >= i - 1; j --) 
        L -> Data[j + 1] = L -> Data[j];
    L -> Data[i - 1] = X;
    L -> Last ++;
    return true;
}

/* 删除为序为 i 的元素 */
bool Delete(List L, int i) {
    Position j;

    if(i < 1 || i > L -> Last + 1) {
        printf("位序不合法");
        return false;
    }

    for(j = i; j <= L -> Last; j ++) 
        L -> Data[j - 1] = L -> Data[j];
    L -> Last --;
    return true;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

typedef int ElementType;
typedef struct LNode * PtrToLNode;

struct LNode{
    ElementType Data;
    PtrToLNode Next;
};

typedef PtrToLNode Position;
typedef PtrToLNode List;

int Length(List L) {
    Position p;
    int cnt = 0;
    p = L;
    while(p) {
        p = p -> Next;
        cnt ++;
    }
    return cnt;
}

/* 查找第 k 个元素 */
ElementType FindKth(List L, int K) {
    Position p;
    int cnt = 1;
    p = L;
    while(p && cnt < K) {
        p = p -> Next;
        cnt ++;
    }
    if((cnt == K) && p)
        return p -> Data;
    else
        return ERROR;
}

/* 查找第一个值为 X 的元素的地址 */
Position Find(List L, ElementType X) {
    Position p = L;
    while(p && p -> Data != X) 
        p = p -> Next;
    if(p) return p;
    else return NULL;
}

/* 在指定为序 i 前插入元素 X, 如果该链表有空的头节点, 则可省略 i==1 的特判 */
List Insert(List L, ElementType X, int i) {
    Position tmp, pre;

    tmp = (Position)malloc(sizeof(struct LNode));
    tmp -> Data = X;
    if(i == 1) {
        tmp -> Next = L;
        return tmp;
    } else {
        int cnt = 1;
        pre = L;
        while(pre && cnt < i - 1) {
            pre = pre -> Next;
            cnt ++;
        }
        if(pre == NULL || cnt != i - 1) {
            printf("插入位置参数错误！");
            free(tmp);
            return NULL;
        } else {
            tmp -> Next = pre -> Next;
            pre -> Next = tmp;
            return L;
        }
    }
}

/* 删除为序为 i 的元素 */
bool Delete(List L, int i) {
    Position tmp, pre = L;
    int cnt = 0;
    while(pre && cnt < i - 1) {
        pre = pre -> Next;
        cnt ++;
    }
    if(pre == NULL || cnt != i - 1 || pre -> Next == NULL) {
        printf("插入位置参数错误！");
        return false;
    } else {
        tmp = pre -> Next;
        pre -> Next = tmp -> Next;
        free(tmp);
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

typedef int ElementType;
typedef int Position;
typedef struct SNode *PtrToSNode;

struct SNode{
    ElementType *Data;
    Position Top;           /*栈顶指针, -1 为空, MaxSize - 1 为满 */
    int MaxSize;
};
typedef PtrToSNode Stack;

Stack CreatStack(int MaxSize) {
    Stack S = (Stack)malloc(sizeof (struct SNode));
    S -> Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    S -> Top = -1;
    S -> MaxSize = MaxSize;
    return S;
}

bool IsFull(Stack S) {
    return (S -> Top == S -> MaxSize -1);
}

bool Push(Stack S, ElementType X) {
    if(IsFull(S)) {
        printf("堆栈满");
        return false;
    }
    S -> Data[++(S -> Top)] = X;
    return true;
}

bool IsEmpty(Stack S) {
    return (S -> Top == -1);
}

ElementType Pop(Stack S) {
    if(IsEmpty(S)) {
        printf("堆栈空");
        return ERROR;
    }
    return S -> Data[(S -> Top)--];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

typedef struct SNode * PtrToSNode;
struct SNode{
    ElementType Data;
    PtrToSNode Next;
};

typedef PtrToSNode Stack;

Stack CreatStack(int MaxSize) {
    Stack S;
    S = (Stack)malloc(sizeof (struct SNode));
    S -> Next = NULL;
    return S;
}

bool Push(Stack S, ElementType X) {
    PtrToSNode TmpCell;
    TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
    TmpCell -> Data = X;
    TmpCell -> Next = S -> Next;
    S -> Next = TmpCell;
    return true;
}

bool IsEmpty(Stack S) { return (S -> Next == NULL); }

ElementType Pop(Stack S) {
    if(IsEmpty(S)) {
        printf("堆栈空");
        return ERROR;
    }
    
    PtrToSNode FirstCell;
    ElementType TopElem;

    FirstCell = S -> Next;
    TopElem = FirstCell -> Data;
    S -> Next = FirstCell -> Next;
    free(FirstCell);
    return TopElem;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

typedef int Position;
typedef struct QNode * PtrToQNode;

struct QNode {
    ElementType * Data;
    Position Front, Rear;
    int MaxSize;
};

typedef PtrToQNode Queue;

Queue CreateQueue(int MaxSize) {
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q -> Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    Q -> Front = Q -> Rear = 0;
    Q -> MaxSize = MaxSize;
    return Q;
}

bool IsFull(Queue Q) {　return ((Q -> Rear + 1) % Q -> MaxSize == Q -> Front);}

bool Add(Queue Q, ElementType X) {
    if(IsFull(Q)) {
        printf("队列满");
        return false;
    }
    Q -> Rear = (Q -> Rear + 1) % Q -> MaxSize;
    Q -> Data[Q -> Rear] = X;
    return true;
}

bool IsEmpty(Queue Q) {　return (Q -> Front == Q -> Rear);}

ElementType Delete(Queue Q) {
    if(IsEmpty(Q)) {
        printf("队列空");
        return ERROR;
    }
    Q -> Front = (Q -> Front + 1) % Q -> MaxSize;
    return Q -> Data[Q -> Front];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

typedef struct Node * PtrToNode;
struct Node{
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode Position;

typedef struct QNode * PtrToQNode;
struct QNode {
    Position Front, Rear;
};
typedef PtrToQNode Queue;

Queue CreateQueue(int MaxSize) {
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q -> Front = Q -> Rear = NULL;
    return Q;
}

bool Add(Queue Q, ElementType X) {
    Position Tmp = (Position)malloc(sizeof(struct Node));
    Tmp -> Data = X;
    Tmp -> Next = NULL;
    if(Q -> Rear == NULL){
        Q -> Rear = Q -> Front = Tmp;
        return true;
    } 
    Q -> Rear -> Next = Tmp;
    Q -> Rear = Tmp;
    return 0;
}

bool IsEmpty(Queue Q) {　return(Q -> Front == NULL);}

ElementType Delete(Queue Q) {
    Position FrontCell; 
    ElementType FrontElem;

    if(IsEmpty(Q)) {
        printf("队列空");
        return ERROR;
    }

    FrontCell = Q -> Front;
    if(Q -> Front == Q -> Rear) 
        Q -> Front = Q -> Rear = NULL;
    else 
        Q -> Front = Q -> Front -> Next;
    
    FrontElem = FrontCell -> Data;
    free(FrontCell);
    return FrontElem;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

typedef struct TNode * BTPosition;
typedef BTPosition BinTree;
struct TNode {
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

void OrderTraversal(BinTree BT) {
    if(BT) {
        /* 此处加入判断叶节点, 则可实现遍历叶节点 */
        /* 先序遍历 （根左右）*/
        OrderTraversal(BT -> Left);
        /* 中序遍历 （左根右）*/
        OrderTraversal(BT -> Right);
        /* 后序遍历 （左右根）*/
    }
}

void InorderTraversal(BinTree BT) {
    BinTree T = BT;
    Stack S = CreatStack();

    while(T || !IsEmpty(S)) {
        while(T) {
            Push(S, T);
            T = T -> Left;
        }
        T = (BinTree)Pop(S);
        /* T -> Data 访问结点 */
        T = T -> Right;
    }
}

/*层序遍历*/
void LevellorderTraversal(BinTree BT) {
    Queue Q;
    BinTree T;

    if(!BT) return;

    Q = CreatQueue();
    Add(Q, BT);
    while(!IsEmpty(Q)) {
        T = (BinTree)Delete(Q);
        /* 取出结点 */
        if(T -> Left) Add(Q, T -> Left);
        if(T -> Right) Add(Q, T -> Right);
    }
}

int GetHight(BinTree BT) {
    int HL, HR, MaxH;

    if(BT) {
        HL = GetHight(BT -> Left);
        HR = GetHight(BT -> Right);
        MaxH = HL > HR ? HL : HR;
        return (MaxH + 1);
    }
    return 0;
}

/*层序生成二叉树*/
BinTree CreatBinTree(){
    int Data;
    BinTree BT, T;
    Queue Q = CreatQueue();

    // 输入根节点
    scanf("%d", &Data);
    if(Data != 0) {
        BT = (BinTree)malloc(sizeof(struct TNode));
        BT -> Data = Data;
        BT -> Left = BT -> Right = NULL;
        Add(Q, BT);
    } else return NULL;

    while(!IsEmpty(Q)) {
        T = (BinTree)Delete(Q);
        scanf("%d", &Data);
        if(Data != 0) {
            T -> Left = (BinTree)malloc(sizeof(struct TNode));
            T -> Left -> Data = Data;
            T -> Left -> Left = T -> Left -> Right = NULL;
            Add(Q, T -> Left);
        } else T -> Left = NULL;
        scanf("%d", &Data);
        if(Data != 0) {
            T -> Right = (BinTree)malloc(sizeof(struct TNode));
            T -> Right -> Data = Data;
            T -> Right -> Left = T -> Left -> Right = NULL;
            Add(Q, T -> Right);
        } else T -> Right = NULL;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

typedef struct TNode * BSTPosition;
typedef BSTPosition BinTree;
struct TNode {
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

void OrderTraversal(BinTree BT) {
    if(BT) {
        OrderTraversal(BT -> Left);
        OrderTraversal(BT -> Right);
    }
}

BSTPosition Find(BinTree BST, ElementType X) {
    if(!BST) return NULL;

    if(X > BST -> Data) {
        Find(BST -> Right, X);
    } else if(X < BST -> Data) {
        Find(BST -> Left, X);
    } else return BST;
}
BSTPosition FindMax(BinTree BST) {
    if(!BST) return NULL;
    else if(!BST -> Left) return BST;
    else return FindMax(BST -> Left);
}
BSTPosition FindMin(BinTree BST) {
    if(BST) 
        while (BST -> Right) {
            BST = BST -> Right;
        }
    return BST;
}

BSTPosition Insert(BinTree BST, ElementType X) {
    if(!BST) {
        BST = (BSTPosition) malloc (sizeof(struct TNode));
        BST -> Data = X;
        BST -> Left = BST -> Right = NULL;
    } else {
        if(X < BST -> Data)
            BST -> Left = Insert(BST -> Left, X);
        else if(X > BST -> Data)
            BST -> Right = Insert(BST -> Right, X);
        /*X 已存在则什么都不做*/
    }
    return BST;
}

BinTree Delete(BinTree BST, ElementType X) {
    BSTPosition Tmp;
    if(!BST)
        printf("要删除的元素未找到");
    else {
        if(X < BST -> Data)
            BST -> Left = Delete(BST -> Left, X);
        else if(X >BST -> Data)
            BST -> Right = Delete(BST -> Right, X);
        else { // 应当删除的结点
            if(BST -> Left && BST -> Right) {
                Tmp = FindMin(BST -> Right); // 找右子树的最小结点
                BST -> Data = Tmp -> Data;
                BST -> Right = Delete(BST -> Right, BST -> Data);
            } else { /* 只有一个儿子或没有儿子 */
                Tmp = BST;
                if(!BST -> Left) // 只有右儿子或者没有子结点(NULL), 
                    BST = BST -> Right;
                else
                    BST = BST -> Left;
                free(Tmp);
            }
        }
    }
    return BST;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

typedef struct HNode *Heap;
struct HNode {
    ElementType *Data;
    int Size;
    int Capacity;
};
typedef Heap MaxHeap;

#define MaxData 998244353 /* 比所有元素大或小的元素作为哨兵 */

MaxHeap CreatHeap(int MaxSize) {
    MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
    H -> Data = (ElementType*)malloc((MaxSize + 1) * sizeof(ElementType));
    H -> Size = 0;
    H -> Capacity = MaxSize;
    H -> Data[0] = MaxData; /* 设置哨兵 */
    return H;
}

bool IsFull(MaxHeap H) { return H -> Size == H -> Capacity; }

bool Insert(MaxHeap H, ElementType X) {
    if(IsFull(H)) {
        printf("最大堆已满");
        return false;
    }

    int idx = ++ H -> Size; /* 指向应当插入的位置 */
    /* 上滤 X */
    for( ; H -> Data[idx / 2] < X; idx /= 2)
        H -> Data[idx] = H -> Data[idx / 2];

    H -> Data[idx] = X;
    return true;
}

bool IsEmpty(MaxHeap H) { return (H -> Size == 0); }

ElementType DeleteMax(MaxHeap H) {
    int Parent, Child;
    ElementType MaxItem, X;
    if(IsEmpty(H)) {
        printf("最大堆为空");
        return false;
    }
    MaxItem = H -> Data[1];
    X = H -> Data[H -> Size --]; /* 规模减小并且取出最后元素 */
    for(Parent = 1; Parent * 2 <= H -> Size; Parent = Child) {
        Child = Parent * 2;
        /* Child指向左右儿子中大的 */
        if((Child != H -> Size) && (H -> Data[Child] < H -> Data[Child + 1])) 
            Child ++;
        /* 找到位置 */
        if(X >= H -> Data[Child]) break;
        /* 下滤 X */
        else
            H -> Data[Parent] = H -> Data[Child];
    }
    H -> Data[Parent] = X;

    return MaxItem;
}

/* 将以 p 为根的子堆调整为最大堆 */
void PercDown(MaxHeap H, int p) {
    int Parent, Child;
    ElementType X;

    X = H -> Data[p];
    for(Parent = p; Parent * 2 <= H -> Size; Parent = Child) {
        Child = Parent * 2;
        if((Child != H -> Size) && (H -> Data[Child] < H -> Data[Child + 1])) 
            Child ++;
        if(X >= H -> Data[Child]) break;
        else
            H -> Data[Parent] = H -> Data[Child];
    }
    H -> Data[Parent] = X;
}

void BuildHeap(MaxHeap H) {
    for(int i = H -> Size / 2; i > 1; i --) 
        PercDown(H, i);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

typedef struct HTNode *HuffmanTree;
struct HTNode {
    int Weight;
    HuffmanTree Left;
    HuffmanTree Right;
};
HuffmanTree Huffman(MinHeap H) {
    int i, N;
    HuffmanTree T;

    BuildHeap(H); /* 调整 O(N)*/
    N = H -> Size;
    /* 作 Size - 1 次合并 */
    for(int i = 1; i < N; i ++) {
        T = (HuffmanTree)malloc(sizeof(struct HTNode));
        T -> Left = DeleteMin(H);
        T -> Right = DeleteMin(H);
        T -> Weight = T -> Left -> Weight + T -> Right -> Weight;
        Insert(H, T);
    }
    return DeleteMin(H);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

typedef struct AVLNode * AVLPosition;
typedef AVLPosition AVLTree;
struct AVLNode {
    ElementType Data;
    AVLTree Left;
    AVLTree Right;
    int Height;
};

int Max(int a, int b) { return a > b ? a : b; }
int GetHeight(AVLTree T) { return T == NULL ? 0 : T -> Height; }
 
/* 左单旋 */
AVLTree SingleLeftRotataion(AVLTree A) {
    AVLTree B = A -> Left;
    A -> Left = B -> Right;
    B -> Right = A;
    A -> Height = Max(GetHeight(A -> Left), GetHeight(A -> Right)) + 1;
    B -> Height = Max(GetHeight(B -> Left), A -> Height) + 1;
    return B;
}
/* 右单旋 */
AVLTree SingleRightRotataion(AVLTree A) {
    AVLTree B = A -> Right;
    A -> Right = B -> Left;
    B -> Left = A;
    A -> Height = Max(GetHeight(A -> Left), GetHeight(A -> Right)) + 1;
    B -> Height = Max(GetHeight(B -> Left), A -> Height) + 1;
    return B;
}
/* 左-右 双旋 */
AVLTree DoubleLeftRightRotation(AVLTree A) {
    /* 先对左子树作右旋，再对整棵树作左旋 */
    A -> Left = SingleRightRotataion(A -> Left);
    return SingleLeftRotataion(A);
}
/* 右-左 双旋 */
AVLTree DoubleRightLeftRotation(AVLTree A) {
    A -> Right = SingleLeftRotataion(A -> Right);
    return SingleRightRotataion(A);
}

AVLTree Insert(AVLTree T, ElementType X) {
    /* 若插入空树，则新建结点 */
    if(!T) {
        T = (AVLTree)malloc(sizeof (struct AVLNode));
        T -> Data = X;
        T -> Height = 1;
        T -> Left = T -> Right = NULL;
    } else if(X < T -> Data) { 
        /* 插入到左子树 */
        T -> Left = Insert(T -> Left, X);
        /* 判断树是否平衡 */
        if(GetHeight(T -> Left) - GetHeight(T -> Right) == 2) {
            /* 通过 X 与左子树的值的大小判断旋转方式*/
            if(X < T -> Left -> Data)
                T = SingleLeftRotataion(T);
            else
                T = DoubleLeftRightRotation(T);
        }
    } else if(X > T -> Data) {
        T -> Right = Insert(T -> Right, X);
        if(GetHeight(T -> Left) - GetHeight(T -> Right) == -2) {
            if(X > T -> Right -> Data) 
                T = SingleRightRotataion(T);
            else
                T = DoubleRightLeftRotation(T);
        }
    }
    /* X == T -> Data 无需插入 */
    T -> Height = Max(GetHeight(T -> Left), GetHeight(T -> Right)) + 1;

    return T;
}

1
2
3
4
5
6
7
8
9

void SimpleSelect(ElementType A[], int N) {
    int i, j, min;
    for(i = 0; i < N - 1; i ++) {
        min = i;
        for(j = i + 1; j < N; j ++) 
            if(A[j] < A[min]) min = j;
        Swap(&A[i], &A[min]);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void PercDown(ElementType A[], int p, int N) {
    /* 将 A[p] 为根的子堆调整 */
    int Parent, Child;
    ElementType X;

    X = A[p];
    for(Parent = p; (Parent * 2 + 1) < N; Parent = Child) {
        Child = Parent * 2 + 1;
        if((Child != N - 1) && (A[Child] < A[Child + 1]))
            Child ++;
        if(X >= A[Child]) break;
        else A[Parent] = A[Child];
    }
    A[Parent] = X;
}

void HeapSort(ElementType A[], int N) {
    int i;
    for(i = N / 2 - 1; i >= 0; i --) /* 建立最大堆 */
        PercDown(A, i, N);

    for(int i = N - 1; i > 0; i --) {
        Swap(&A[0], &A[i]);
        PercDown(A, 0, i);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void InsertionSort(ElementType A[], int N) {
    int i, P;
    ElementType Tmp;
    for(P = 1; P < N; P ++) {
        Tmp = A[P];
        for(i = P; i > 0 && A[i-1] > Tmp; i --) 
            A[i] = A[i - 1];
        A[i] = Tmp;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

void ShellSOrt(ElementType A[], int N) {
    int Si, D, P, i;
    ElementType Tmp;

    int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};

    for(Si = 0; Sedgewick[Si] >= N; Si ++) ;

    for(D = Sedgewick[Si]; D > 0; D = Sedgewick[++Si]) {
        /* 插入排序 */
        for( P = D; P < N; P ++) {
            Tmp = A[P];
            for(i = P; i >= D && A[i-D] > Tmp; i -= D)
                A[i] = A[i - D];
            A[i] =Tmp;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void BubbleSort(ElementType A[], int N) {
    int P, i;
    int flag;

    for(P = N - 1; P >= 0; P--) {
        flag = 0;
        for(i = 0; i < P; i ++) {
            if(A[i] > A[i + 1]) {
                Swap(&A[i], &A[i + 1]);
                flag = 1;
            }
        }
        if(!flag) break;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/* 选中值 */
ElementType Median3(ElementType A[], int Left, int Right) {
    int Center = (Left + Right) / 2;
    if(A[Left] > A[Center]) Swap(&A[Left], &A[Center]);

    if(A[Left] > A[Right]) Swap(&A[Left], &A[Right]);

    if(A[Center] > A[Right]) Swap(&A[Center], &A[Right]);
    /* A[Left] <= A[Center] <= A[Right] 所以中值 A[Center]作为基准 */
    Swap(&A[Center], &A[Right - 1]); /*将基准藏到右边, 只需考虑, left + 1 ... right - 2*/
    return A[Right - 1];
}

void Qsort(ElementType A[], int Left, int Right) {
    int Pivot, Cutoff, Low, High;
    /* 如果元素够多进入快排 */
    if(Cutoff <= Right - Left) {
        Pivot = Median3(A, Left, Right);
        Low = Left; High = High - 1;
        while(1) {
            while (A[++Low] < Pivot);
            while (A[--High] > Pivot);
            if(Low < High) Swap(&A[Low], &A[High]);
            else break;
        }
        Swap(&A[Low], &A[Right - 1]); /* 把基准换到正确的位置 */
        Qsort(A, Left, Low - 1);
        Qsort(A, Low + 1, Right);
    }
    else InsertionSort(A, Right - Left + 1);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

void Merge(ElementType A[], ElementType TmpA[], int L, int R, int RightEnd) {
    int LeftEnd, NumElements, Tmp;
    int i;
    /*L ~ R - 1 与 R ~ RightEnd 合并为有序*/
    LeftEnd = R - 1; /*左边终点*/
    Tmp = L;         /*序列起点*/
    NumElements = RightEnd - L + 1;
    /*复制数组*/
    while(L <= LeftEnd && R <= RightEnd) {
        if(A[L] <= A[R])
            TmpA[Tmp ++] = A[L++];
        else
            TmpA[Tmp ++] = A[R++];;
    }    
    while(L <= LeftEnd) TmpA[Tmp++] = A[L++];
    while(R <= RightEnd) TmpA[Tmp++] = A[R++];

    for(i = 0; i < NumElements; i ++, RightEnd --) 
        A[RightEnd] = TmpA[RightEnd];
}

void Msort(ElementType A[], ElementType TmpA[], int L, int RightEnd) {
    int Center;
    if(L < RightEnd) {
        Center = (L + RightEnd) / 2;
        Msort(A, TmpA, L, Center); 
        Msort(A, TmpA, Center + 1, RightEnd); 
        Merge(A, TmpA, L, Center + 1, RightEnd); 
    }
}

void MergeSort(ElementType A[], int N) {
    ElementType *TmpA;
    TmpA = (ElementType*)malloc(N*sizeof(ElementType));

    if(TmpA != NULL) {
        Msort(A, TmpA, 0, N - 1);
        free(TmpA);
    }
}