使用快速排序对带有指针的数组进行排序

快速排序是一种高效的排序算法，采用分治法策略。它通过选择一个基准元素，将数组分成两个子数组，其中一个子数组的所有元素都小于基准元素，另一个子数组的所有元素都大于基准元素，然后递归地对这两个子数组进行排序。

基础概念

基准元素（Pivot）：选择数组中的一个元素作为基准。
分区（Partitioning）：重新排列数组，使得所有小于基准的元素放在基准前面，所有大于基准的元素放在基准后面。
递归排序：对基准左右两边的子数组分别进行快速排序。

优势

平均时间复杂度为 (O(n \log n))，效率高。
原地排序，不需要额外的存储空间。

类型

Lomuto分区方案：简单但效率较低，最坏情况下时间复杂度为 (O(n^2))。
Hoare分区方案：更高效，最坏情况下时间复杂度也是 (O(n^2))，但实际应用中表现更好。

应用场景

大规模数据的排序。
需要高性能排序的场景。

示例代码：使用快速排序对带有指针的数组进行排序

假设我们有一个结构体数组，每个元素包含一个指针和一个值：

typedef struct {
    int *ptr;
    int value;
} Element;

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

int partition(Element arr[], int low, int high) {
    int pivot = arr[high].value;
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j].value < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

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

int main() {
    Element arr[] = {{&value1, 10}, {&value2, 7}, {&value3, 8}, {&value4, 9}, {&value5, 1}};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i].value);
    }
    return 0;
}

遇到的问题及解决方法

问题1：快速排序的最坏情况时间复杂度为 (O(n^2))

原因：当每次选择的基准元素都是数组中的最小或最大值时，会导致分区极不平衡。

解决方法：

使用随机选择基准元素的方法。
使用三数取中法选择基准元素。

问题2：递归深度过大导致栈溢出

原因：递归调用层次过深，超过了系统允许的最大栈深度。

解决方法：

将递归改为迭代，使用栈来模拟递归过程。

示例代码：改进的分区方案（三数取中法）

int medianOfThree(Element arr[], int low, int high) {
    int mid = low + (high - low) / 2;
    if (arr[low].value > arr[mid].value) swap(&arr[low], &arr[mid]);
    if (arr[low].value > arr[high].value) swap(&arr[low], &arr[high]);
    if (arr[mid].value > arr[high].value) swap(&arr[mid], &arr[high]);
    return mid;
}

int partitionImproved(Element arr[], int low, int high) {
    int pivotIndex = medianOfThree(arr, low, high);
    int pivot = arr[pivotIndex].value;
    swap(&arr[pivotIndex], &arr[high]);
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j].value < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

通过这些改进，可以有效减少快速排序在最坏情况下的性能问题。