C语言如何实现排序数组并查找指定顺位最低汽车价格的函数

错误思路说明 #

你之前用switch case实现失败是合理的：switch case仅适合处理固定范围的离散枚举值，而order参数是用户动态输入的，理论上可以覆盖1到数组长度的所有整数，用switch case需要穷举所有可能的order值，完全不具备可维护性和通用性。

方案1：排序法（实现简单，适合小规模数组） #

实现逻辑 #

1. 首先做参数合法性校验：size <= 0、order < 1、order > size均为非法输入，返回错误标识（这里假设价格均为正整数，用-1代表错误）
2. 拷贝一份原数组进行操作，避免修改传入的原始价格数组
3. 对拷贝后的数组做升序排序
4. 排序后数组下标为order - 1的元素即为第order小的价格

完整代码实现 #

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

// qsort需要的整数比较函数
int cmpInt(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int lowestPrice(int prices[], int size, int order) {
    // 非法输入校验
    if (size <= 0 || order < 1 || order > size) {
        return -1;
    }
    // 拷贝原数组避免修改原始输入
    int* temp = (int*)malloc(size * sizeof(int));
    memcpy(temp, prices, size * sizeof(int));
    // 升序排序
    qsort(temp, size, sizeof(int), cmpInt);
    int res = temp[order - 1];
    free(temp);
    return res;
}

// 测试用例
int main() {
    int testA1[] = { 25000, 20000, 29499, 10000, 20000, 29000, 25000, 20000 , 25000 , 10000 };
    int size = sizeof(testA1) / sizeof(testA1[0]);
    // 测试输入2，返回第二小价格
    printf("第2小价格：%d\n", lowestPrice(testA1, size, 2));
    // 测试输入5，返回第五小价格
    printf("第5小价格：%d\n", lowestPrice(testA1, size, 5));
    return 0;
}

测试输出 #

第2小价格：10000
第5小价格：20000

和预期结果完全一致。

方案2：快速选择算法（适合大规模数组，性能更优） #

如果需要处理的价格数组长度很大（比如上万、十万级以上），排序法的O(nlogn)时间复杂度偏高，可以用快速选择算法，平均时间复杂度为O(n)，仅需要定位第K小的元素不需要全量排序。

实现代码 #

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

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int left, int right) {
    int pivot = arr[right];
    int i = left;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[right]);
    return i;
}

int quickSelect(int arr[], int left, int right, int k) {
    if (left == right) return arr[left];
    int pivotIdx = partition(arr, left, right);
    if (k == pivotIdx) {
        return arr[k];
    } else if (k < pivotIdx) {
        return quickSelect(arr, left, pivotIdx - 1, k);
    } else {
        return quickSelect(arr, pivotIdx + 1, right, k);
    }
}

int lowestPrice(int prices[], int size, int order) {
    if (size <= 0 || order < 1 || order > size) {
        return -1;
    }
    // 拷贝原数组避免修改原始输入
    int* temp = (int*)malloc(size * sizeof(int));
    memcpy(temp, prices, size * sizeof(int));
    int res = quickSelect(temp, 0, size - 1, order - 1);
    free(temp);
    return res;
}

// 测试代码和排序法完全一致，输出结果相同

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