优化#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 200000 void swap(int arr[], int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } void quickSort(int arr[], int left, int right) { if (left >= right) return; int i = left, j = right, pivot = arr[left + (right - left) / 2]; while (i <= j) { while (arr[i] < pivot) i++; while (arr[j] > pivot) j--; if (i <= j) { swap(arr, i, j); i++; j--; } } quickSort(arr, left, j); quickSort(arr, i, right); } int main() { int arr[N]; for (int i = 0; i < N; i++) { arr[i] = i; } srand((unsigned)time(NULL)); for (int i = 0; i < N / 100; i++) { int a = rand() % N; int b = rand() % N; swap(arr, a, b); } clock_t start1 = clock(); quickSort(arr, 0, N - 1); clock_t end1 = clock(); printf("未改进的快速排序时间：%f秒\n", (double)(end1 - start1) / CLOCKS_PER_SEC); clock_t start2 = clock(); clock_t end2 = clock(); printf("改进的快速排序时间：%f秒\n", (double)(end2 - start2) / CLOCKS_PER_SEC); return 0; }

这段代码实现的是快速排序算法，针对这段代码的优化有以下几点：

1. 减少交换操作次数：在快速排序中，交换操作是比较耗时的操作。可以使用指针来避免过多的交换操作，提高排序效率。

2. 优化pivot的选取：pivot的选择对快速排序的效率有很大的影响。可以采用三数取中法来选择pivot，即取left、right和中间位置的数，然后选择其中位于中间的数作为pivot。

3. 优化递归：快速排序是一个递归算法，递归深度过深会导致栈溢出。可以使用非递归方式实现快速排序，或者采用尾递归优化。

4. 优化内存：在排序过程中，会创建大量的临时数组，这会占用大量的内存。可以使用原地排序算法，来减少内存的使用。原地排序指在排序过程中，不需要额外的内存空间，只利用原数组进行排序。

对于这段代码，我们可以实现pivot的优化，即采用三数取中法来选择pivot，代码修改如下：

int medianOfThree(int arr[], int left, int right) {
    int mid = left + (right - left) / 2;
    if (arr[left] > arr[mid]) {
        swap(arr, left, mid);
    }
    if (arr[left] > arr[right]) {
        swap(arr, left, right);
    }
    if (arr[mid] > arr[right]) {
        swap(arr, mid, right);
    }
    return mid;
}

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;
    int i = left, j = right, pivot = arr[medianOfThree(arr, left, right)];
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

这样可以对快速排序的效率进行优化。