1
int Partition(int a[], int low, int high) {
2
    int pivot = a[low];                 // 取第一个元素为枢轴，挖坑
3
    while (low < high) {
4
        while (low < high && a[high] >= pivot) high--;
5
        a[low] = a[high];               // 比枢轴小的填坑，high 成新坑
6
        while (low < high && a[low] <= pivot) low++;
7
        a[high] = a[low];               // 比枢轴大的填坑，low 成新坑
8
    }
9
    a[low] = pivot;                     // 枢轴归位
10
    return low;                         // 返回枢轴最终位置
11
}
12

13
void QuickSort(int a[], int low, int high) {
14
    if (low < high) {
15
        int pos = Partition(a, low, high);
16
        QuickSort(a, low, pos - 1);
17
        QuickSort(a, pos + 1, high);
18
    }
19
}

1
void AdjustDown(int a[], int k, int len) {   // 向下调整
2
    a[0] = a[k];                             // 暂存待调结点
3
    for (int i = 2*k; i <= len; i *= 2) {
4
        if (i < len && a[i] < a[i+1]) i++;   // 取较大的孩子
5
        if (a[0] >= a[i]) break;             // 比孩子大，就位
6
        a[k] = a[i]; k = i;                  // 孩子上移，继续向下
7
    }
8
    a[k] = a[0];
9
}
10

11
void BuildMaxHeap(int a[], int len) {
12
    for (int i = len/2; i > 0; i--)          // 从最后一个非叶结点开始
13
        AdjustDown(a, i, len);
14
}
15

16
void HeapSort(int a[], int len) {
17
    BuildMaxHeap(a, len);
18
    for (int i = len; i > 1; i--) {          // n-1 趟
19
        Swap(a[i], a[1]);                    // 堆顶(最大)换到末尾
20
        AdjustDown(a, 1, i - 1);             // 剩余元素重新调整
21
    }
22
}

1
void Merge(int a[], int b[], int low, int mid, int high) {
2
    int i = low, j = mid + 1, k = low;
3
    while (i <= mid && j <= high)
4
        b[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];   // <= 保证稳定
5
    while (i <= mid)  b[k++] = a[i++];
6
    while (j <= high) b[k++] = a[j++];
7
    for (k = low; k <= high; k++) a[k] = b[k];
8
}
9

10
void MergeSort(int a[], int b[], int low, int high) {
11
    if (low < high) {
12
        int mid = (low + high) / 2;
13
        MergeSort(a, b, low, mid);
14
        MergeSort(a, b, mid + 1, high);
15
        Merge(a, b, low, mid, high);
16
    }
17
}

1
int BinarySearch(int a[], int n, int key) {
2
    int low = 0, high = n - 1, mid;
3
    while (low <= high) {
4
        mid = (low + high) / 2;
5
        if (a[mid] == key) return mid;
6
        else if (a[mid] > key) high = mid - 1;
7
        else low = mid + 1;
8
    }
9
    return -1;
10
}

1
LinkList Reverse(LinkList L) {
2
    LNode *p = L->next, *q;
3
    L->next = NULL;
4
    while (p) {
5
        q = p->next;          // 保住后继
6
        p->next = L->next;    // 头插
7
        L->next = p;
8
        p = q;
9
    }
10
    return L;
11
}

1
LNode *FindMiddle(LinkList L) {
2
    LNode *fast = L->next, *slow = L->next;
3
    while (fast && fast->next) {
4
        fast = fast->next->next;
5
        slow = slow->next;
6
    }
7
    return slow;              // 奇数中点，偶数为前一个中点
8
}

1
void InOrder2(BiTree T) {
2
    Stack S; InitStack(S);
3
    BiTree p = T;
4
    while (p || !IsEmpty(S)) {
5
        if (p) {              // 一路向左，沿途入栈
6
            Push(S, p);
7
            p = p->lchild;
8
        } else {              // 左边到头，出栈访问，转右
9
            Pop(S, p); Visit(p);
10
            p = p->rchild;
11
        }
12
    }
13
}

1
void LevelOrder(BiTree T) {
2
    Queue Q; InitQueue(Q);
3
    BiTree p;
4
    EnQueue(Q, T);
5
    while (!IsEmpty(Q)) {
6
        DeQueue(Q, p); Visit(p);
7
        if (p->lchild) EnQueue(Q, p->lchild);
8
        if (p->rchild) EnQueue(Q, p->rchild);
9
    }
10
}