C语言快速排序随机生成时间比较

快速排序是一种常用的高效排序算法，其基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。在C语言中，快速排序通常通过递归实现。

当涉及到随机生成作为快速排序策略的一部分时，这意味着在选择分割点时，我们不是固定使用第一个元素或最后一个元素，而是随机选取数组中的某个元素。这样做的好处有两点：

1. **提高平均性能**：随机选择分割点使得每次划分的数据分布更均匀，避免了最坏情况下（如输入已经部分有序）快速排序退化为O(n^2)的时间复杂度，从而提升排序的平均效率。

2. **减少最坏情况出现概率**：如果每次都能选择到数组中心或者其他均匀分布的元素作为分割点，那么每次划分都将数组分成大致相等的两部分，降低了算法遇到极端情况的概率。

在C语言中，你可以这样做：

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

int partition_random(int arr[], int low, int high) {
    srand(time(0)); // 设置随机种子，保证每次调用都是随机的
    int pivot_index = rand() % (high - low + 1) + low; // 随机选择分割点
    int pivot = arr[pivot_index];
    swap(&arr[pivot_index], &arr[high]); // 将pivot放在末尾

    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_random(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition_random(arr, low, high);
        quicksort_random(arr, low, pi - 1);
        quicksort_random(arr, pi + 1, high);
    }
}

// 其他辅助函数...