面试题：C语言快速排序的优化实现

Question

用C语言实现一个优化版本的快速排序。要求在传统快速排序的基础上，考虑处理数组中大量重复元素的情况，以提高排序效率。例如，可以使用三数取中选择基准元素，并且在处理重复元素时，采用特殊的分区策略，减少不必要的交换操作。

Answer 1

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

// 交换两个元素
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 三数取中选择基准元素
int medianOfThree(int arr[], int left, int right) {
    int mid = left + (right - left) / 2;
    if ((arr[left] <= arr[mid] && arr[mid] <= arr[right]) ||
        (arr[right] <= arr[mid] && arr[mid] <= arr[left]))
        return mid;
    else if ((arr[mid] <= arr[left] && arr[left] <= arr[right]) ||
             (arr[right] <= arr[left] && arr[left] <= arr[mid]))
        return left;
    else
        return right;
}

// 分区函数，处理重复元素
int partition(int arr[], int left, int right) {
    int pivotIndex = medianOfThree(arr, left, right);
    swap(&arr[pivotIndex], &arr[right]);
    int pivot = arr[right];
    int i = left - 1;
    int j = right;
    for (;;) {
        while (arr[++i] < pivot);
        while (arr[--j] > pivot && j > left);
        if (i >= j) break;
        swap(&arr[i], &arr[j]);
    }
    swap(&arr[i], &arr[right]);
    return i;
}

// 优化的快速排序
void optimizedQuickSort(int arr[], int left, int right) {
    if (left < right) {
        int pivotIndex = partition(arr, left, right);
        optimizedQuickSort(arr, left, pivotIndex - 1);
        optimizedQuickSort(arr, pivotIndex + 1, right);
    }
}

int main() {
    int arr[] = {3, 6, 8, 10, 1, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    optimizedQuickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}