快速排序与qsort函数应用详解

快速排序算法原理

快速排序(Quick Sort)是一种高效的排序算法，采用分治策略。其基本思想是：

1. 选择基准值(pivot)：从数组中选择一个元素作为基准
2. 分区(partition)：将数组分为两部分，小于基准的放在左边，大于基准的放在右边
3. 递归排序：对左右两部分递归地应用快速排序

C语言实现示例

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

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = (low - 1);      // i是小于基准的元素的索引
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

时间复杂度分析

• 情况：O(n log n)
• 平均情况：O(n log n)
• 最坏情况：O(n²)（当数组已经有序或所有元素相同时）

C标准库中的qsort函数

C语言标准库提供了通用的快速排序函数qsort，原型如下：

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

参数说明

1. base：指向要排序数组的个元素的指针
2. nmemb：数组中元素的数量
3. size：每个元素的大小（以字节为单位）
4. compar：比较函数的指针

比较函数编写规则

比较函数应该返回：

• 负数：如果个参数应该排在第二个参数前面
• 零：如果两个参数相等
• 正数：如果个参数应该排在第二个参数后面

qsort使用示例

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

// 整型比较函数
int compareInt(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

// 字符串比较函数
int compareStr(const void* a, const void* b) {
    return strcmp(*(const char**)a, *(const char**)b);
}

int main() {
    // 整型数组排序
    int arr[] = {10, 5, 15, 12, 90, 80};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    qsort(arr, n, sizeof(int), compareInt);
    
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    
    // 字符串数组排序
    const char* strArr[] = {"banana", "apple", "orange", "grape"};
    int strN = sizeof(strArr)/sizeof(strArr[0]);
    
    qsort(strArr, strN, sizeof(const char*), compareStr);
    
    for (int i = 0; i < strN; i++)
        printf("%s ", strArr[i]);
    printf("\n");
    
    return 0;
}

高级应用技巧

1. 多条件排序

typedef struct {
    char name[50];
    int age;
    float score;
} Student;

int compareStudent(const void* a, const void* b) {
    Student* sa = (Student*)a;
    Student* sb = (Student*)b;
    
    // 先按分数降序
    if (sa->score > sb->score) return -1;
    if (sa->score < sb->score) return 1;
    
    // 分数相同按年龄升序
    if (sa->age < sb->age) return -1;
    if (sa->age > sb->age) return 1;
    
    // 年龄也相同按姓名升序
    return strcmp(sa->name, sb->name);
}

2. 对指针数组排序

int comparePtr(const void* a, const void* b) {
    int* pa = *(int**)a;
    int* pb = *(int**)b;
    return (*pa - *pb);
}

void sortPointerArray(int* arr[], int n) {
    qsort(arr, n, sizeof(int*), comparePtr);
}

3. 非递增排序

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

注意事项

1. 稳定性：快速排序不是稳定的排序算法，相等元素的相对位置可能会改变
2. 递归深度：对于大型数组，递归可能导致栈溢出，可以考虑使用迭代实现
3. 基准选择：在实际应用中，常使用"三数取中"法选择基准值以避免最坏情况
4. 小数组优化：对于小数组(如n<10)，插入排序可能比快速排序更高效

性能优化建议

1. 对于重复元素多的数组，可以考虑三路快速排序
2. 在递归到小规模子数组时切换到插入排序
3. 随机化基准选择以避免恶意构造的最坏情况
4. 对于几乎有序的数组，可以考虑先检查是否已接近有序

通过理解快速排序的原理和掌握qsort的用法，可以在大多数排序场景中获得良好的性能表现。

（本文来源：nzw6.com）