C语言实现特定规则数组排序的高效算法求解

你担心的遍历数组操作是O(n)复杂度，远低于快排的O(n log n)，所以整体时间复杂度依然满足O(n log n)的要求。以下是具体实现方案：

实现步骤 #

1. 升序排序整个数组：用标准库的qsort（或自定义快速排序）对数组进行升序排序，时间复杂度O(n log n)。
2. 分区分离偶数与奇数：遍历数组，将所有偶数交换到数组左半部分，奇数留在右半部分，同时统计偶数的数量count_even。这一步是线性时间O(n)，不影响整体复杂度。
3. 反转奇数部分实现降序：升序排序后的奇数是从小到大排列的，直接反转右半部分的奇数子数组，即可得到降序排列。反转操作是O(k)（k为奇数个数），属于线性时间。

C语言代码实现 #

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

// 比较函数：用于qsort升序排序
int compare_asc(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

// 分区函数：将偶数移到左半部分，返回偶数的数量
int partition_even(int *A, int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (A[i] % 2 == 0) {
            // 交换当前偶数到左部的count位置
            int temp = A[count];
            A[count] = A[i];
            A[i] = temp;
            count++;
        }
    }
    return count;
}

// 反转数组指定区间[start, end)
void reverse_array(int *A, int start, int end) {
    end--; // 转为闭区间[start, end]
    while (start < end) {
        int temp = A[start];
        A[start] = A[end];
        A[end] = temp;
        start++;
        end--;
    }
}

// 主函数：数组重排
void rearrange_array(int *A, int n) {
    // 1. 升序排序整个数组
    qsort(A, n, sizeof(int), compare_asc);
    
    // 2. 分区分离偶数和奇数，得到偶数数量
    int count_even = partition_even(A, n);
    
    // 3. 反转奇数部分实现降序
    reverse_array(A, count_even, n);
}

// 测试函数
int main() {
    int A[] = {6, 8, 8, 10, 20, 5, 1};
    int n = sizeof(A) / sizeof(A[0]);
    
    rearrange_array(A, n);
    
    printf("重排后数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", A[i]);
    }
    printf("\n");
    // 输出应为：6 8 8 10 20 5 1 （符合左偶升序、右奇降序的需求）
    
    return 0;
}

复杂度说明 #

• 升序排序：O(n log n)，是整个流程的时间复杂度瓶颈。
• 分区操作：O(n)，线性遍历数组并交换元素。
• 反转操作：O(k)，k为奇数元素的数量，k ≤ n，属于线性时间。

三者相加后，整体时间复杂度为O(n log n)，完全满足要求。同时整个过程未使用辅助数组，仅用少量临时变量。

补充说明 #

如果偏好使用快速排序实现奇数部分降序（而非反转），可修改qsort的比较函数为降序：

int compare_desc(const void *a, const void *b) {
    return *(int*)b - *(int*)a;
}

然后在步骤3中调用：

qsort(A + count_even, n - count_even, sizeof(int), compare_desc);

这一步时间复杂度为O(k log k)，依然不会改变整体O(n log n)的复杂度。

内容的提问来源于stack exchange，提问作者LiorMorali