quickSort(int[] arr, int low, int high)

`quickSort(int[] arr, int low, int high)` 是快速排序算法中的一个递归函数，用于对数组的指定范围进行排序。

参数说明：
- `arr`：待排序的数组
- `low`：排序范围的起始索引
- `high`：排序范围的结束索引

函数实现：
1. 如果 `low` 小于 `high`，则执行以下步骤：
- 选择基准元素（pivot）：通常选择数组的最后一个元素 `arr[high]` 作为基准元素。
- 调用 `partition()` 函数，将数组划分为两部分，并返回基准元素的索引 `pivotIndex`。
- 递归调用 `quickSort()` 函数对基准元素左边的子数组进行排序，即调用 `quickSort(arr, low, pivotIndex - 1)`。
- 递归调用 `quickSort()` 函数对基准元素右边的子数组进行排序，即调用 `quickSort(arr, pivotIndex + 1, high)`。

2. 如果 `low` 大于等于 `high`，则不执行任何操作，直接返回。

通过不断地划分和递归排序，最终整个数组就会被排序。

相关问题

#include<stdio.h> void Swap(int arr[], int low, int high) { int temp; temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; } int Partition(int arr[], int low, int high) { int base = arr[low]; while(low < high) { while(low < high && arr[high] >= base) { high --; } Swap(arr, low, high); while(low < high && arr[low] <= base) { low ++; } Swap(arr, low, high); } return low; } void QuickSort(int arr[], int low, int high) { if(low < high) { int base = Partition(arr, low, high); QuickSort(arr, low, base - 1); QuickSort(arr, base + 1, high); } } int main() { int n; scanf("%d\n",&n); int arr[n]; int i , j; for(i = 0; i < n; i ++) { scanf("%d",&arr[i]); } printf("\n"); QuickSort(arr, 0, n-1); for(j = 0; j < n; j ++) { printf("%4d",arr[j]); } return 0; }

这是一个使用 C 语言实现的快速排序算法。首先定义了 Swap 函数用于交换数组中两个元素的位置，然后定义了 Partition 函数用于确定基准值的位置（即将数组划分为两部分，并返回基准值所在的下标），最后定义了 QuickSort 函数用于进行快速排序（即不断递归地对子数组进行划分和排序）。在主函数中，首先输入数组的长度 n 和 n 个元素，然后对数组进行快速排序并输出排序后的结果。

优化#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 main() { int arr[] = { 64, 25, 12, 22, 11 }; int n = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1); printf("Sorted array: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0;}

下面是一个对快速排序进行了优化的 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;
    int j = high;

    while (1) {
        do {
            i++;
        } while (arr[i] < pivot);

        do {
            j--;
        } while (arr[j] > pivot && j > low);

        if (i >= j) {
            break;
        }

        swap(&arr[i], &arr[j]);
    }

    swap(&arr[i], &arr[high]);
    return i;
}

void quickSort(int arr[], int low, int high) {
    while (low < high) {
        int pi = partition(arr, low, high);

        if (pi - low < high - pi) {
            quickSort(arr, low, pi - 1);
            low = pi + 1;
        } else {
            quickSort(arr, pi + 1, high);
            high = pi - 1;
        }
    }
}

int main() {
    int arr[] = { 64, 25, 12, 22, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

这个算法中主要的优化是在 partition 函数中对 i 和 j 的递增和递减操作进行了优化，使得它可以更快地找到基准元素的位置。同时，算法中还增加了一个判断，比较左右子数组的大小，选择较小的那个先进行排序，可以减少递归的层数。这些优化可以使得快速排序的性能得到进一步提升。