用c++写一个快速排序

以下是使用 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 - 1; 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);
    }
}

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

int main() {
    int arr[] = {5, 2, 7, 3, 9, 1, 4, 6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArray(arr, n);

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

快速排序是一种常用的排序算法，它的时间复杂度为 O(nlogn)，其中 n 是待排序元素的数量。快速排序的基本思想是通过划分将待排序序列分成两个子序列，其中一个子序列的所有元素都小于另一个子序列中的元素。然后，再对这两个子序列分别进行快速排序，以此类推，直到整个序列有序。在上面的示例中，我们使用了递归来实现快速排序。具体来说，我们在数组中选择一个元素作为基准值（通常是最后一个元素），然后将数组分成两个子数组：一个子数组中的所有元素都小于基准值，而另一个子数组中的所有元素都大于或等于基准值。然后，我们递归地对这两个子数组进行快速排序，最终得到有序的数组。