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

#include <stdio.h>

// 交换两个数
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);

    for (int j = low; j < high; 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);
    }
}

// 优化后的划分函数，使用随机化选择枢轴
int randomizedPartition(int arr[], int low, int high) {
    int i = low + rand() % (high - low + 1);
    swap(&arr[i], &arr[high]);
    return partition(arr, low, high);
}

// 优化后的快速排序函数
void optimizedQuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = randomizedPartition(arr, low, high);

        optimizedQuickSort(arr, low, pi - 1);
        optimizedQuickSort(arr, pi + 1, high);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);
    printf("Sorted array (original quicksort): \n");
    printArray(arr, n);

    // 恢复原数组
    int arr2[] = {10, 7, 8, 9, 1, 5};
    printf("Original array again: \n");
    printArray(arr2, n);

    optimizedQuickSort(arr2, 0, n - 1);
    printf("Sorted array (optimized quicksort): \n");
    printArray(arr2, n);

    return 0;
}

原始快速排序：
- swap函数用于交换两个整数。
- partition函数选择数组的最后一个元素作为枢轴，将数组分为两部分，左边部分小于等于枢轴，右边部分大于枢轴，并返回枢轴的最终位置。
- quickSort函数递归地调用partition函数，对左右两部分进行排序。
优化方法：
- 随机化枢轴选择：在randomizedPartition函数中，通过随机选择一个元素与数组的最后一个元素交换，然后再进行划分，这样可以避免在数组已排序等特殊情况下，每次都选择边界元素作为枢轴导致的性能退化。
- optimizedQuickSort函数使用randomizedPartition进行划分，从而提升性能。
测试部分：
- 在main函数中，首先打印原始数组，然后使用原始快速排序和优化后的快速排序分别对数组进行排序，并打印排序后的结果。

星途面试题库

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

知识考点

面试题答案