第8章 排序代码

使用建议

• 先配合对应章节阅读：第8章 排序 正文
• 这一页优先提供站内可直接查看的代码版本，适合网页阅读和搜索。
• 这一页主要用于网页阅读，建议结合对应正文与逐行注释版一起使用。

文件位置

• 普通代码版：第8章普通代码版
• 逐行注释版：第8章逐行注释版代码
• 兼容编码版：第8章兼容编码版逐行注释代码

普通代码版

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_COUNTING_VALUE 100
#define RADIX_BASE 10
#define INF_KEY 0x3f3f3f3f

/* 打印数组：便于观察每种排序算法最终的输出结果。 */
void PrintArray(const int *array, int length, const char *label) {
    int i;

    if (array == NULL || length <= 0) {
        return;
    }

    printf("%s", label);
    for (i = 0; i < length; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

/* 交换两个整数：很多原地排序都会用到这个小工具。 */
void SwapInt(int *a, int *b) {
    int temp;

    if (a == NULL || b == NULL) {
        return;
    }

    temp = *a;
    *a = *b;
    *b = temp;
}

/* 直接插入排序：把前面一段看成已排序区，不断把新元素插进去。 */
void InsertSort(int *array, int length) {
    int i;
    int j;
    int temp;

    if (array == NULL || length <= 1) {
        return;
    }

    for (i = 1; i < length; i++) {
        temp = array[i];
        j = i - 1;
        while (j >= 0 && array[j] > temp) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = temp;
    }
}

/* 冒泡排序：相邻元素逆序就交换，每一趟把较大元素推到后面。 */
void BubbleSort(int *array, int length) {
    int i;
    int j;
    bool swapped;

    if (array == NULL || length <= 1) {
        return;
    }

    for (i = 0; i < length - 1; i++) {
        swapped = false;
        for (j = 0; j < length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                SwapInt(&array[j], &array[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

/* 简单选择排序：每一趟在未排序区中找最小值，再换到前面。 */
void SelectionSort(int *array, int length) {
    int i;
    int j;
    int min_index;

    if (array == NULL || length <= 1) {
        return;
    }

    for (i = 0; i < length - 1; i++) {
        min_index = i;
        for (j = i + 1; j < length; j++) {
            if (array[j] < array[min_index]) {
                min_index = j;
            }
        }
        if (min_index != i) {
            SwapInt(&array[i], &array[min_index]);
        }
    }
}

/* 一次划分：以首元素为枢轴，把小元素放左边，大元素放右边。 */
int Partition(int *array, int low, int high) {
    int pivot;

    pivot = array[low];
    while (low < high) {
        while (low < high && array[high] >= pivot) {
            high--;
        }
        array[low] = array[high];

        while (low < high && array[low] <= pivot) {
            low++;
        }
        array[high] = array[low];
    }
    array[low] = pivot;
    return low;
}

/* 快速排序：先划分，再递归处理左右子区间。 */
void QuickSort(int *array, int low, int high) {
    int pivot_pos;

    if (array == NULL || low >= high) {
        return;
    }

    pivot_pos = Partition(array, low, high);
    QuickSort(array, low, pivot_pos - 1);
    QuickSort(array, pivot_pos + 1, high);
}

/* 向下调整堆：把某个结点放到正确位置，保持大根堆性质。 */
void SiftDown(int *array, int start, int end) {
    int root;
    int child;

    if (array == NULL) {
        return;
    }

    root = start;
    while (2 * root + 1 <= end) {
        child = 2 * root + 1;
        if (child + 1 <= end && array[child + 1] > array[child]) {
            child++;
        }

        if (array[root] >= array[child]) {
            return;
        }

        SwapInt(&array[root], &array[child]);
        root = child;
    }
}

/* 堆排序：先建大根堆，再反复把堆顶最大元素换到末尾。 */
void HeapSort(int *array, int length) {
    int i;

    if (array == NULL || length <= 1) {
        return;
    }

    for (i = length / 2 - 1; i >= 0; i--) {
        SiftDown(array, i, length - 1);
    }

    for (i = length - 1; i > 0; i--) {
        SwapInt(&array[0], &array[i]);
        SiftDown(array, 0, i - 1);
    }
}

/* 归并两个有序子段：把 [left, mid] 和 [mid+1, right] 合成一个有序段。 */
void Merge(int *array, int left, int mid, int right, int *temp) {
    int i;
    int j;
    int k;

    i = left;
    j = mid + 1;
    k = left;

    while (i <= mid && j <= right) {
        if (array[i] <= array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = array[i++];
    }

    while (j <= right) {
        temp[k++] = array[j++];
    }

    for (k = left; k <= right; k++) {
        array[k] = temp[k];
    }
}

/* 归并排序递归版：不断二分，再把两个有序段归并起来。 */
void MergeSortRecursive(int *array, int left, int right, int *temp) {
    int mid;

    if (array == NULL || temp == NULL || left >= right) {
        return;
    }

    mid = left + (right - left) / 2;
    MergeSortRecursive(array, left, mid, temp);
    MergeSortRecursive(array, mid + 1, right, temp);
    Merge(array, left, mid, right, temp);
}

/* 归并排序外壳：负责申请辅助数组并启动递归。 */
void MergeSort(int *array, int length) {
    int *temp;

    if (array == NULL || length <= 1) {
        return;
    }

    temp = (int *)malloc((size_t)length * sizeof(int));
    if (temp == NULL) {
        return;
    }

    MergeSortRecursive(array, 0, length - 1, temp);
    free(temp);
}

/* 计数排序：适合关键字范围不大的非负整数序列。 */
bool CountingSort(int *array, int length, int max_value) {
    int counts[MAX_COUNTING_VALUE];
    int i;
    int index;

    if (array == NULL || length <= 0 || max_value < 0 || max_value >= MAX_COUNTING_VALUE) {
        return false;
    }

    memset(counts, 0, sizeof(counts));
    for (i = 0; i < length; i++) {
        if (array[i] < 0 || array[i] > max_value) {
            return false;
        }
        counts[array[i]]++;
    }

    index = 0;
    for (i = 0; i <= max_value; i++) {
        while (counts[i] > 0) {
            array[index++] = i;
            counts[i]--;
        }
    }

    return true;
}

/* 求序列最大值：给基数排序判断需要处理到哪一位。 */
int GetMaxValue(const int *array, int length) {
    int i;
    int max_value;

    if (array == NULL || length <= 0) {
        return -1;
    }

    max_value = array[0];
    for (i = 1; i < length; i++) {
        if (array[i] > max_value) {
            max_value = array[i];
        }
    }

    return max_value;
}

/* 按某一位做稳定计数：这是 LSD 基数排序每一趟真正落地的核心。 */
bool CountingSortByDigit(int *array, int length, int exponent) {
    int counts[RADIX_BASE];
    int *output;
    int i;
    int digit;

    if (array == NULL || length <= 0 || exponent <= 0) {
        return false;
    }

    output = (int *)malloc((size_t)length * sizeof(int));
    if (output == NULL) {
        return false;
    }

    memset(counts, 0, sizeof(counts));
    for (i = 0; i < length; i++) {
        if (array[i] < 0) {
            free(output);
            return false;
        }
        digit = (array[i] / exponent) % RADIX_BASE;
        counts[digit]++;
    }

    for (i = 1; i < RADIX_BASE; i++) {
        counts[i] += counts[i - 1];
    }

    for (i = length - 1; i >= 0; i--) {
        digit = (array[i] / exponent) % RADIX_BASE;
        output[counts[digit] - 1] = array[i];
        counts[digit]--;
    }

    memcpy(array, output, (size_t)length * sizeof(int));
    free(output);
    return true;
}

/* 基数排序：从个位开始，逐位做稳定分配与收集。 */
bool RadixSortLSD(int *array, int length) {
    int max_value;
    int exponent;

    if (array == NULL || length <= 0) {
        return false;
    }

    max_value = GetMaxValue(array, length);
    if (max_value < 0) {
        return false;
    }

    for (exponent = 1; max_value / exponent > 0; exponent *= RADIX_BASE) {
        if (!CountingSortByDigit(array, length, exponent)) {
            return false;
        }
    }

    return true;
}

/* 打印外部排序中的归并段：帮助学生把“段”真正看出来。 */
void PrintRuns(const int *array, int length, int run_size, const char *label) {
    int start;
    int end;
    int i;

    if (array == NULL || length <= 0 || run_size <= 0 || label == NULL) {
        return;
    }

    printf("%s", label);
    for (start = 0; start < length; start += run_size) {
        end = start + run_size;
        if (end > length) {
            end = length;
        }
        printf("[");
        for (i = start; i < end; i++) {
            printf("%d", array[i]);
            if (i + 1 < end) {
                printf(" ");
            }
        }
        printf("] ");
    }
    printf("\n");
}

/* 外部排序中的一趟归并：把相邻两个有序段合成更大的有序段。 */
void MergePass(const int *src, int *dest, int length, int run_size) {
    int left;
    int mid;
    int right;
    int i;
    int j;
    int k;

    for (left = 0; left < length; left += 2 * run_size) {
        mid = left + run_size;
        right = left + 2 * run_size;
        if (mid > length) {
            mid = length;
        }
        if (right > length) {
            right = length;
        }

        i = left;
        j = mid;
        k = left;
        while (i < mid && j < right) {
            if (src[i] <= src[j]) {
                dest[k++] = src[i++];
            } else {
                dest[k++] = src[j++];
            }
        }
        while (i < mid) {
            dest[k++] = src[i++];
        }
        while (j < right) {
            dest[k++] = src[j++];
        }
    }
}

/* 外部排序模拟：先生成初始归并段，再按固定段长做多趟归并。 */
bool ExternalMergeSortSimulation(int *array, int length, int initial_run_size) {
    int *temp;
    int start;
    int run_length;
    int pass;

    if (array == NULL || length <= 0 || initial_run_size <= 0) {
        return false;
    }

    temp = (int *)malloc((size_t)length * sizeof(int));
    if (temp == NULL) {
        return false;
    }

    for (start = 0; start < length; start += initial_run_size) {
        run_length = initial_run_size;
        if (start + run_length > length) {
            run_length = length - start;
        }
        MergeSort(array + start, run_length);
    }
    PrintRuns(array, length, initial_run_size, "Initial runs: ");

    pass = 1;
    for (run_length = initial_run_size; run_length < length; run_length *= 2) {
        MergePass(array, temp, length, run_length);
        memcpy(array, temp, (size_t)length * sizeof(int));
        printf("After merge pass %d (run size = %d): ", pass, run_length * 2);
        PrintRuns(array, length, run_length * 2, "");
        pass++;
    }

    free(temp);
    return true;
}

/* 输出一轮败者树赢家：把最小关键字持续弹出，模拟多路归并中的选优过程。 */
void LoserTreeAdjust(int *keys, int *tree, int size, int player) {
    int parent;

    parent = (player + size) / 2;
    while (parent > 0) {
        if (keys[player] > keys[tree[parent]]) {
            SwapInt(&player, &tree[parent]);
        }
        parent /= 2;
    }
    tree[0] = player;
}

void BuildLoserTree(int *keys, int *tree, int size) {
    int i;

    keys[size] = -INF_KEY;
    for (i = 0; i < size; i++) {
        tree[i] = size;
    }
    for (i = size - 1; i >= 0; i--) {
        LoserTreeAdjust(keys, tree, size, i);
    }
}

void LoserTreeDemo(const int *sources, int size) {
    int keys[17];
    int tree[16];
    int i;
    int winner;

    if (sources == NULL || size <= 0 || size > 16) {
        return;
    }

    for (i = 0; i < size; i++) {
        keys[i] = sources[i];
    }

    BuildLoserTree(keys, tree, size);
    printf("Loser tree merge order: ");
    for (i = 0; i < size; i++) {
        winner = tree[0];
        printf("%d ", keys[winner]);
        keys[winner] = INF_KEY;
        LoserTreeAdjust(keys, tree, size, winner);
    }
    printf("\n");
}

/* 置换-选择模拟：用有限内存把输入序列切成更长的初始归并段。 */
bool ReplacementSelectionRuns(const int *input, int length, int memory_size) {
    int keys[32];
    bool frozen[32];
    bool active[32];
    int next_input;
    int active_count;
    int run_count;
    int last_output;
    int i;
    int winner;
    int winner_key;
    bool has_unfrozen;

    if (input == NULL || length <= 0 || memory_size <= 0 || memory_size > 32) {
        return false;
    }

    active_count = 0;
    next_input = 0;
    while (active_count < memory_size && next_input < length) {
        keys[active_count] = input[next_input++];
        frozen[active_count] = false;
        active[active_count] = true;
        active_count++;
    }

    run_count = 1;
    last_output = -INF_KEY;
    printf("Replacement selection runs:\n");
    printf("Run %d: ", run_count);

    while (active_count > 0) {
        winner = -1;
        for (i = 0; i < memory_size; i++) {
            if (!active[i] || frozen[i]) {
                continue;
            }
            if (winner == -1 || keys[i] < keys[winner]) {
                winner = i;
            }
        }

        if (winner == -1) {
            printf("\n");
            run_count++;
            has_unfrozen = false;
            for (i = 0; i < memory_size; i++) {
                if (active[i]) {
                    frozen[i] = false;
                    has_unfrozen = true;
                }
            }
            if (!has_unfrozen) {
                break;
            }
            last_output = -INF_KEY;
            printf("Run %d: ", run_count);
            continue;
        }

        winner_key = keys[winner];
        printf("%d ", winner_key);
        last_output = winner_key;

        if (next_input < length) {
            keys[winner] = input[next_input++];
            frozen[winner] = keys[winner] < last_output;
        } else {
            active[winner] = false;
            frozen[winner] = false;
            active_count--;
        }
    }

    return true;
}

/* 拷贝数组：让同一组样例可以给不同算法分别使用。 */
void CopyArray(int *dest, const int *src, int length) {
    if (dest == NULL || src == NULL || length <= 0) {
        return;
    }

    memcpy(dest, src, (size_t)length * sizeof(int));
}

/* 主函数：集中演示第 8 章启动版已经落地的内部排序算法。 */
int main(void) {
    int sample1[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int sample2[] = {10, 7, 8, 9, 1, 5};
    int sample3[] = {4, 2, 2, 8, 3, 3, 1};
    int sample4[] = {329, 457, 657, 839, 436, 720, 355};
    int sample5[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4, 88, 12};
    int sample6[] = {7, 12, 5, 18, 9};
    int sample7[] = {17, 3, 25, 8, 12, 30, 5, 14, 29, 1, 9, 18};
    int buffer[16];
    int length1;
    int length2;
    int length3;
    int length4;
    int length5;
    int length6;
    int length7;

    length1 = (int)(sizeof(sample1) / sizeof(sample1[0]));
    length2 = (int)(sizeof(sample2) / sizeof(sample2[0]));
    length3 = (int)(sizeof(sample3) / sizeof(sample3[0]));
    length4 = (int)(sizeof(sample4) / sizeof(sample4[0]));
    length5 = (int)(sizeof(sample5) / sizeof(sample5[0]));
    length6 = (int)(sizeof(sample6) / sizeof(sample6[0]));
    length7 = (int)(sizeof(sample7) / sizeof(sample7[0]));

    CopyArray(buffer, sample1, length1);
    InsertSort(buffer, length1);
    PrintArray(buffer, length1, "Insert sort: ");

    CopyArray(buffer, sample1, length1);
    BubbleSort(buffer, length1);
    PrintArray(buffer, length1, "Bubble sort: ");

    CopyArray(buffer, sample1, length1);
    SelectionSort(buffer, length1);
    PrintArray(buffer, length1, "Selection sort: ");

    CopyArray(buffer, sample2, length2);
    QuickSort(buffer, 0, length2 - 1);
    PrintArray(buffer, length2, "Quick sort: ");

    CopyArray(buffer, sample2, length2);
    HeapSort(buffer, length2);
    PrintArray(buffer, length2, "Heap sort: ");

    CopyArray(buffer, sample1, length1);
    MergeSort(buffer, length1);
    PrintArray(buffer, length1, "Merge sort: ");

    CopyArray(buffer, sample3, length3);
    if (CountingSort(buffer, length3, 8)) {
        PrintArray(buffer, length3, "Counting sort: ");
    } else {
        printf("Counting sort failed.\n");
    }

    CopyArray(buffer, sample4, length4);
    if (RadixSortLSD(buffer, length4)) {
        PrintArray(buffer, length4, "Radix sort: ");
    } else {
        printf("Radix sort failed.\n");
    }

    CopyArray(buffer, sample5, length5);
    if (ExternalMergeSortSimulation(buffer, length5, 4)) {
        PrintArray(buffer, length5, "External merge sort simulation: ");
    } else {
        printf("External merge sort simulation failed.\n");
    }

    LoserTreeDemo(sample6, length6);
    if (!ReplacementSelectionRuns(sample7, length7, 4)) {
        printf("Replacement selection simulation failed.\n");
    }

    return 0;
}

逐行注释版

/* 绗?{number}琛岋細寮曞叆褰撳墠鏂囦欢闇€瑕佷娇鐢ㄧ殑澶存枃浠躲€?*/
#include <stdbool.h>
/* 绗?{number}琛岋細寮曞叆褰撳墠鏂囦欢闇€瑕佷娇鐢ㄧ殑澶存枃浠躲€?*/
#include <stdio.h>
/* 绗?{number}琛岋細寮曞叆褰撳墠鏂囦欢闇€瑕佷娇鐢ㄧ殑澶存枃浠躲€?*/
#include <stdlib.h>
/* 绗?{number}琛岋細寮曞叆褰撳墠鏂囦欢闇€瑕佷娇鐢ㄧ殑澶存枃浠躲€?*/
#include <string.h>
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細瀹氫箟鍚庨潰浠ｇ爜浼氬弽澶嶄娇鐢ㄧ殑瀹忓父閲忋€?*/
#define MAX_COUNTING_VALUE 100
/* 绗?{number}琛岋細瀹氫箟鍚庨潰浠ｇ爜浼氬弽澶嶄娇鐢ㄧ殑瀹忓父閲忋€?*/
#define RADIX_BASE 10
/* 绗?{number}琛岋細瀹氫箟鍚庨潰浠ｇ爜浼氬弽澶嶄娇鐢ㄧ殑瀹忓父閲忋€?*/
#define INF_KEY 0x3f3f3f3f
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 打印数组：便于观察每种排序算法最终的输出结果。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void PrintArray(const int *array, int length, const char *label) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int i;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL || length <= 0) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
    printf("%s", label);
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = 0; i < length; i++) {
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
        printf("%d ", array[i]);
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
    printf("\n");
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 交换两个整数：很多原地排序都会用到这个小工具。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void SwapInt(int *a, int *b) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int temp;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (a == NULL || b == NULL) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    temp = *a;
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    *a = *b;
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    *b = temp;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 直接插入排序：把前面一段看成已排序区，不断把新元素插进去。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void InsertSort(int *array, int length) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int i;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int j;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int temp;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL || length <= 1) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = 1; i < length; i++) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        temp = array[i];
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        j = i - 1;
/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
        while (j >= 0 && array[j] > temp) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            array[j + 1] = array[j];
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
            j--;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        array[j + 1] = temp;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 冒泡排序：相邻元素逆序就交换，每一趟把较大元素推到后面。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void BubbleSort(int *array, int length) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int i;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int j;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    bool swapped;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL || length <= 1) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = 0; i < length - 1; i++) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        swapped = false;
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
        for (j = 0; j < length - 1 - i; j++) {
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
            if (array[j] > array[j + 1]) {
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
                SwapInt(&array[j], &array[j + 1]);
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
                swapped = true;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
            }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (!swapped) {
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
            break;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 简单选择排序：每一趟在未排序区中找最小值，再换到前面。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void SelectionSort(int *array, int length) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int i;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int j;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int min_index;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL || length <= 1) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = 0; i < length - 1; i++) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        min_index = i;
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
        for (j = i + 1; j < length; j++) {
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
            if (array[j] < array[min_index]) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
                min_index = j;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
            }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (min_index != i) {
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
            SwapInt(&array[i], &array[min_index]);
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 一次划分：以首元素为枢轴，把小元素放左边，大元素放右边。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
int Partition(int *array, int low, int high) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int pivot;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    pivot = array[low];
/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
    while (low < high) {
/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
        while (low < high && array[high] >= pivot) {
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
            high--;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        array[low] = array[high];
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
        while (low < high && array[low] <= pivot) {
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
            low++;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        array[high] = array[low];
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    array[low] = pivot;
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
    return low;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 快速排序：先划分，再递归处理左右子区间。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void QuickSort(int *array, int low, int high) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int pivot_pos;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL || low >= high) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    pivot_pos = Partition(array, low, high);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    QuickSort(array, low, pivot_pos - 1);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    QuickSort(array, pivot_pos + 1, high);
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 向下调整堆：把某个结点放到正确位置，保持大根堆性质。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void SiftDown(int *array, int start, int end) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int root;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int child;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    root = start;
/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
    while (2 * root + 1 <= end) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        child = 2 * root + 1;
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (child + 1 <= end && array[child + 1] > array[child]) {
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
            child++;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (array[root] >= array[child]) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
            return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
        SwapInt(&array[root], &array[child]);
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        root = child;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 堆排序：先建大根堆，再反复把堆顶最大元素换到末尾。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void HeapSort(int *array, int length) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int i;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL || length <= 1) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = length / 2 - 1; i >= 0; i--) {
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
        SiftDown(array, i, length - 1);
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = length - 1; i > 0; i--) {
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
        SwapInt(&array[0], &array[i]);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
        SiftDown(array, 0, i - 1);
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 归并两个有序子段：把 [left, mid] 和 [mid+1, right] 合成一个有序段。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void Merge(int *array, int left, int mid, int right, int *temp) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int i;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int j;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int k;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    i = left;
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    j = mid + 1;
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    k = left;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
    while (i <= mid && j <= right) {
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (array[i] <= array[j]) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            temp[k++] = array[i++];
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
        } else {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            temp[k++] = array[j++];
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
    while (i <= mid) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        temp[k++] = array[i++];
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
    while (j <= right) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        temp[k++] = array[j++];
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (k = left; k <= right; k++) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        array[k] = temp[k];
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 归并排序递归版：不断二分，再把两个有序段归并起来。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void MergeSortRecursive(int *array, int left, int right, int *temp) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int mid;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL || temp == NULL || left >= right) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    mid = left + (right - left) / 2;
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    MergeSortRecursive(array, left, mid, temp);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    MergeSortRecursive(array, mid + 1, right, temp);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    Merge(array, left, mid, right, temp);
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 归并排序外壳：负责申请辅助数组并启动递归。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void MergeSort(int *array, int length) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int *temp;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL || length <= 1) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    temp = (int *)malloc((size_t)length * sizeof(int));
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (temp == NULL) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    MergeSortRecursive(array, 0, length - 1, temp);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    free(temp);
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 计数排序：适合关键字范围不大的非负整数序列。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
bool CountingSort(int *array, int length, int max_value) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int counts[MAX_COUNTING_VALUE];
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int i;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int index;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL || length <= 0 || max_value < 0 || max_value >= MAX_COUNTING_VALUE) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return false;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    memset(counts, 0, sizeof(counts));
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = 0; i < length; i++) {
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (array[i] < 0 || array[i] > max_value) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
            return false;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
        counts[array[i]]++;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    index = 0;
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = 0; i <= max_value; i++) {
/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
        while (counts[i] > 0) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            array[index++] = i;
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
            counts[i]--;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
    return true;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 求序列最大值：给基数排序判断需要处理到哪一位。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
int GetMaxValue(const int *array, int length) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int i;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int max_value;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL || length <= 0) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return -1;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    max_value = array[0];
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = 1; i < length; i++) {
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (array[i] > max_value) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            max_value = array[i];
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
    return max_value;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 按某一位做稳定计数：这是 LSD 基数排序每一趟真正落地的核心。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
bool CountingSortByDigit(int *array, int length, int exponent) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int counts[RADIX_BASE];
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int *output;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int i;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int digit;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL || length <= 0 || exponent <= 0) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return false;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    output = (int *)malloc((size_t)length * sizeof(int));
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (output == NULL) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return false;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    memset(counts, 0, sizeof(counts));
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = 0; i < length; i++) {
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (array[i] < 0) {
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
            free(output);
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
            return false;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        digit = (array[i] / exponent) % RADIX_BASE;
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
        counts[digit]++;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = 1; i < RADIX_BASE; i++) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        counts[i] += counts[i - 1];
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = length - 1; i >= 0; i--) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        digit = (array[i] / exponent) % RADIX_BASE;
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        output[counts[digit] - 1] = array[i];
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
        counts[digit]--;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    memcpy(array, output, (size_t)length * sizeof(int));
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    free(output);
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
    return true;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 基数排序：从个位开始，逐位做稳定分配与收集。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
bool RadixSortLSD(int *array, int length) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int max_value;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int exponent;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL || length <= 0) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return false;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    max_value = GetMaxValue(array, length);
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (max_value < 0) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return false;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (exponent = 1; max_value / exponent > 0; exponent *= RADIX_BASE) {
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (!CountingSortByDigit(array, length, exponent)) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
            return false;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
    return true;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 打印外部排序中的归并段：帮助学生把“段”真正看出来。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void PrintRuns(const int *array, int length, int run_size, const char *label) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int start;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int end;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int i;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL || length <= 0 || run_size <= 0 || label == NULL) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
    printf("%s", label);
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (start = 0; start < length; start += run_size) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        end = start + run_size;
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (end > length) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            end = length;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
        printf("[");
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
        for (i = start; i < end; i++) {
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
            printf("%d", array[i]);
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
            if (i + 1 < end) {
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
                printf(" ");
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
            }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
        printf("] ");
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
    printf("\n");
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 外部排序中的一趟归并：把相邻两个有序段合成更大的有序段。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void MergePass(const int *src, int *dest, int length, int run_size) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int left;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int mid;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int right;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int i;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int j;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int k;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (left = 0; left < length; left += 2 * run_size) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        mid = left + run_size;
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        right = left + 2 * run_size;
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (mid > length) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            mid = length;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (right > length) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            right = length;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        i = left;
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        j = mid;
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        k = left;
/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
        while (i < mid && j < right) {
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
            if (src[i] <= src[j]) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
                dest[k++] = src[i++];
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
            } else {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
                dest[k++] = src[j++];
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
            }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
        while (i < mid) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            dest[k++] = src[i++];
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
        while (j < right) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            dest[k++] = src[j++];
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 外部排序模拟：先生成初始归并段，再按固定段长做多趟归并。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
bool ExternalMergeSortSimulation(int *array, int length, int initial_run_size) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int *temp;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int start;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int run_length;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int pass;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (array == NULL || length <= 0 || initial_run_size <= 0) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return false;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    temp = (int *)malloc((size_t)length * sizeof(int));
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (temp == NULL) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return false;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (start = 0; start < length; start += initial_run_size) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        run_length = initial_run_size;
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (start + run_length > length) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            run_length = length - start;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
        MergeSort(array + start, run_length);
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    PrintRuns(array, length, initial_run_size, "Initial runs: ");
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    pass = 1;
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (run_length = initial_run_size; run_length < length; run_length *= 2) {
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
        MergePass(array, temp, length, run_length);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
        memcpy(array, temp, (size_t)length * sizeof(int));
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
        printf("After merge pass %d (run size = %d): ", pass, run_length * 2);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
        PrintRuns(array, length, run_length * 2, "");
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
        pass++;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    free(temp);
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
    return true;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 输出一轮败者树赢家：把最小关键字持续弹出，模拟多路归并中的选优过程。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void LoserTreeAdjust(int *keys, int *tree, int size, int player) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int parent;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    parent = (player + size) / 2;
/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
    while (parent > 0) {
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (keys[player] > keys[tree[parent]]) {
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
            SwapInt(&player, &tree[parent]);
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        parent /= 2;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    tree[0] = player;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void BuildLoserTree(int *keys, int *tree, int size) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int i;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    keys[size] = -INF_KEY;
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = 0; i < size; i++) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        tree[i] = size;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = size - 1; i >= 0; i--) {
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
        LoserTreeAdjust(keys, tree, size, i);
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void LoserTreeDemo(const int *sources, int size) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int keys[17];
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int tree[16];
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int i;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int winner;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (sources == NULL || size <= 0 || size > 16) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = 0; i < size; i++) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        keys[i] = sources[i];
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    BuildLoserTree(keys, tree, size);
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
    printf("Loser tree merge order: ");
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
    for (i = 0; i < size; i++) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        winner = tree[0];
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
        printf("%d ", keys[winner]);
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        keys[winner] = INF_KEY;
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
        LoserTreeAdjust(keys, tree, size, winner);
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
    printf("\n");
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 置换-选择模拟：用有限内存把输入序列切成更长的初始归并段。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
bool ReplacementSelectionRuns(const int *input, int length, int memory_size) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int keys[32];
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    bool frozen[32];
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    bool active[32];
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int next_input;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int active_count;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int run_count;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int last_output;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int i;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int winner;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int winner_key;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    bool has_unfrozen;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (input == NULL || length <= 0 || memory_size <= 0 || memory_size > 32) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return false;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    active_count = 0;
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    next_input = 0;
/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
    while (active_count < memory_size && next_input < length) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        keys[active_count] = input[next_input++];
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        frozen[active_count] = false;
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        active[active_count] = true;
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
        active_count++;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    run_count = 1;
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    last_output = -INF_KEY;
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
    printf("Replacement selection runs:\n");
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
    printf("Run %d: ", run_count);
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細寮€濮嬩竴娆?while 寰幆锛屽彧瑕佹潯浠舵垚绔嬪氨缁х画鎵ц銆?*/
    while (active_count > 0) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        winner = -1;
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
        for (i = 0; i < memory_size; i++) {
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
            if (!active[i] || frozen[i]) {
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
                continue;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
            }
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
            if (winner == -1 || keys[i] < keys[winner]) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
                winner = i;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
            }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (winner == -1) {
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
            printf("\n");
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
            run_count++;
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            has_unfrozen = false;
/* 绗?{number}琛岋細寮€濮嬩竴娆?for 寰幆锛屾寜鍥哄畾鍖洪棿鎴栨鏁伴噸澶嶆墽琛屽悗缁鍙ャ€?*/
            for (i = 0; i < memory_size; i++) {
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
                if (active[i]) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
                    frozen[i] = false;
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
                    has_unfrozen = true;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
                }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
            }
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
            if (!has_unfrozen) {
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
                break;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
            }
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            last_output = -INF_KEY;
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
            printf("Run %d: ", run_count);
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
            continue;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        winner_key = keys[winner];
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
        printf("%d ", winner_key);
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
        last_output = winner_key;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
        if (next_input < length) {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            keys[winner] = input[next_input++];
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            frozen[winner] = keys[winner] < last_output;
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
        } else {
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            active[winner] = false;
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
            frozen[winner] = false;
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
            active_count--;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
        }
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
    return true;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 拷贝数组：让同一组样例可以给不同算法分别使用。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
void CopyArray(int *dest, const int *src, int length) {
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (dest == NULL || src == NULL || length <= 0) {
/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
        return;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    memcpy(dest, src, (size_t)length * sizeof(int));
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細杩欐槸鍘熶唬鐮佷腑鑷甫鐨勮鏄庢€ф敞閲娿€?*/
/* 主函数：集中演示第 8 章启动版已经落地的内部排序算法。 */
/* 绗?{number}琛岋細瀹氫箟鍑芥暟 ㈠紑濮嬪啓杩欎釜鍑芥暟鐨勫叿浣撳疄鐜般€?*/
int main(void) {
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int sample1[] = {49, 38, 65, 97, 76, 13, 27, 49};
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int sample2[] = {10, 7, 8, 9, 1, 5};
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int sample3[] = {4, 2, 2, 8, 3, 3, 1};
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int sample4[] = {329, 457, 657, 839, 436, 720, 355};
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int sample5[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4, 88, 12};
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int sample6[] = {7, 12, 5, 18, 9};
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int sample7[] = {17, 3, 25, 8, 12, 30, 5, 14, 29, 1, 9, 18};
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int buffer[16];
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int length1;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int length2;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int length3;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int length4;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int length5;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int length6;
/* 绗?{number}琛岋細澹版槑褰撳墠璇彞鍚庨潰瑕佷娇鐢ㄧ殑鍙橀噺銆佹寚閽堟垨灞€閮ㄦ暟鎹€?*/
    int length7;
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    length1 = (int)(sizeof(sample1) / sizeof(sample1[0]));
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    length2 = (int)(sizeof(sample2) / sizeof(sample2[0]));
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    length3 = (int)(sizeof(sample3) / sizeof(sample3[0]));
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    length4 = (int)(sizeof(sample4) / sizeof(sample4[0]));
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    length5 = (int)(sizeof(sample5) / sizeof(sample5[0]));
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    length6 = (int)(sizeof(sample6) / sizeof(sample6[0]));
/* 绗?{number}琛岋細缁欏彉閲忋€佹暟缁勫厓绱犳垨鎸囬拡璧嬪€硷紝鏇存柊褰撳墠鐘舵€併€?*/
    length7 = (int)(sizeof(sample7) / sizeof(sample7[0]));
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    CopyArray(buffer, sample1, length1);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    InsertSort(buffer, length1);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    PrintArray(buffer, length1, "Insert sort: ");
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    CopyArray(buffer, sample1, length1);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    BubbleSort(buffer, length1);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    PrintArray(buffer, length1, "Bubble sort: ");
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    CopyArray(buffer, sample1, length1);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    SelectionSort(buffer, length1);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    PrintArray(buffer, length1, "Selection sort: ");
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    CopyArray(buffer, sample2, length2);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    QuickSort(buffer, 0, length2 - 1);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    PrintArray(buffer, length2, "Quick sort: ");
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    CopyArray(buffer, sample2, length2);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    HeapSort(buffer, length2);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    PrintArray(buffer, length2, "Heap sort: ");
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    CopyArray(buffer, sample1, length1);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    MergeSort(buffer, length1);
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    PrintArray(buffer, length1, "Merge sort: ");
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    CopyArray(buffer, sample3, length3);
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (CountingSort(buffer, length3, 8)) {
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
        PrintArray(buffer, length3, "Counting sort: ");
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
    } else {
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
        printf("Counting sort failed.\n");
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    CopyArray(buffer, sample4, length4);
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (RadixSortLSD(buffer, length4)) {
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
        PrintArray(buffer, length4, "Radix sort: ");
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
    } else {
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
        printf("Radix sort failed.\n");
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    CopyArray(buffer, sample5, length5);
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (ExternalMergeSortSimulation(buffer, length5, 4)) {
/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
        PrintArray(buffer, length5, "External merge sort simulation: ");
/* 绗?{number}琛岋細鎵ц杩欎竴琛屼唬鐮侊紝缁х画鎺ㄨ繘褰撳墠閫昏緫銆?*/
    } else {
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
        printf("External merge sort simulation failed.\n");
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細璋冪敤涓€涓嚱鏁帮紝璁╁畠甯垜浠畬鎴愬綋鍓嶈繖涓€姝ユ搷浣溿€?*/
    LoserTreeDemo(sample6, length6);
/* 绗?{number}琛岋細杩涜鏉′欢鍒ゆ柇锛屽喅瀹氬綋鍓嶆祦绋嬪簲璇ヨ蛋鍝釜鍒嗘敮銆?*/
    if (!ReplacementSelectionRuns(sample7, length7, 4)) {
/* 绗?{number}琛岋細鎶婂綋鍓嶇粨鏋滄墦鍗板嚭鏉ワ紝鏂逛究瑙傚療鎺掑簭鍚庣殑杈撳嚭銆?*/
        printf("Replacement selection simulation failed.\n");
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
    }
/* 绗?{number}琛岋細绌鸿锛岀敤鏉ュ垎闅斾笉鍚岀殑浠ｇ爜閫昏緫娈点€?*/

/* 绗?{number}琛岋細鎶婂綋鍓嶅嚱鏁扮殑缁撴灉杩斿洖缁欒皟鐢ㄨ€咃紝骞剁粨鏉熷綋鍓嶅嚱鏁般€?*/
    return 0;
/* 绗?{number}琛岋細浠ｇ爜鍧楃粨鏉燂紝褰撳墠缁撴瀯銆佸惊鐜垨鍑芥暟鍦ㄨ繖閲屾敹鍙ｃ€?*/
}

继续阅读

← 上一章代码：第7章 查找代码