六、排序（3 题）

2026 校订版 · 专题阅读 · 保留代码与校订注 · 与版本锁一致

六、排序（3 题）

1. 快速排序

int partition(int A[], int low, int high) {
    int pivot = A[low];

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

        while (low < high && A[low] < pivot)
            low++;
        A[high] = A[low];
    }

    A[low] = pivot;
    return low;
}

void quickSort(int A[], int low, int high) {
    if (low >= high)
        return;

    int pivotPos = partition(A, low, high);
    quickSort(A, low, pivotPos - 1);
    quickSort(A, pivotPos + 1, high);
}

复杂度： 平均时间 O(n log n)，最坏时间 O(n²)；平均递归栈空间 O(log n)，最坏 O(n)。

校订注：原稿只给出 O(n log n) 和 O(log n)，这是平均情况，不是快速排序的最坏情况。

回源 · PDF 第 27 页 · b_27_1；PDF 第 27 页 · b_27_0

2. 二路归并排序

bool mergeRanges(int A[], int low, int mid, int high) {
    int length = high - low + 1;
    int *temp = (int *)malloc(length * sizeof(int));
    if (temp == NULL)
        return false;

    for (int i = low; i <= high; i++)
        temp[i - low] = A[i];

    int i = 0;
    int j = mid - low + 1;
    int leftEnd = mid - low;
    int rightEnd = high - low;
    int k = low;

    while (i <= leftEnd && j <= rightEnd) {
        if (temp[i] <= temp[j])
            A[k++] = temp[i++];
        else
            A[k++] = temp[j++];
    }
    while (i <= leftEnd)
        A[k++] = temp[i++];
    while (j <= rightEnd)
        A[k++] = temp[j++];

    free(temp);
    return true;
}

bool mergeSort(int A[], int low, int high) {
    if (low >= high)
        return true;

    int mid = low + (high - low) / 2;
    if (!mergeSort(A, low, mid))
        return false;
    if (!mergeSort(A, mid + 1, high))
        return false;
    return mergeRanges(A, low, mid, high);
}

复杂度： 时间 O(n log n)，额外空间 O(n)，递归栈 O(log n)。

调用后应检查 mergeSort(A, 0, n - 1) 的返回值；false 表示辅助数组申请失败，不能把当前数组误当成“已完成排序”。

校订注：原稿每次 malloc 后没有 free，会造成内存泄漏，本版已补上释放，并把内存申请失败逐层传回调用者。

回源 · PDF 第 27 页 · b_27_3；PDF 第 27 页 · b_27_2

3. 将集合划分为元素数最接近、元素和之差最大的两个子集（2016 年统考题）

给定由 n (n>=2) 个正整数构成的集合 A={a_k | 0<=k<n}，划分为不相交的 A1、A2。要求先使 |n1-n2| 最小，再使 |S1-S2| 最大。

void splitForMaximumSumDifference(int A[], int n,
                                  int A1[], int *n1,
                                  int A2[], int *n2) {
    int target = n / 2;
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        int pivotPos = partition(A, low, high);
        if (pivotPos == target)
            break;
        if (pivotPos < target)
            low = pivotPos + 1;
        else
            high = pivotPos - 1;
    }

    *n1 = target;
    *n2 = n - target;
    for (int i = 0; i < *n1; i++)
        A1[i] = A[i];
    for (int i = 0; i < *n2; i++)
        A2[i] = A[target + i];
}

复杂度： 基于快速选择，平均时间 O(n)、最坏时间 O(n²)；除输出数组外额外空间 O(1)。若使用线性时间的确定性选择算法，可保证最坏时间 O(n)。

核心思路： 为使元素个数之差最小，两组大小必须分别为 floor(n/2) 和 ceil(n/2)；在大小确定后，把较小的一半元素放入一组、较大的一半放入另一组，可使两组元素和之差最大。快速选择只需把数组划分到这个边界，无需完整排序。

校订注：原 PDF 的集合下标因排版看起来像 0<=a_k<n，结合原题应为 0<=k<n；它约束的是下标，不是元素值。原稿用完整快速排序，平均时间 O(n log n)，不是本题的更优做法。

回源 · PDF 第 27 页 · b_27_4；PDF 第 27 页 · b_27_5

---