给我用C++写快速排序程序，附带解释

以下是用C语言写的快速排序程序：

#include <stdio.h>

void quickSort(int arr[], int left, int right) {
    int i = left, j = right;
    int tmp;
    int pivot = arr[(left + right) / 2];
 
    /* 分割数组 */
    while (i <= j) {
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i <= j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    };
 
    /* 递归排序左半部分 */
    if (left < j)
        quickSort(arr, left, j);
    /* 递归排序右半部分 */
    if (i < right)
        quickSort(arr, i, right);
}

int main() {
    int arr[] = {7, 6, 5, 9, 8, 4, 3, 1, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    int i;
    
    printf("Before sorting:\n");
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    quickSort(arr, 0, n-1);
    
    printf("\nAfter sorting:\n");
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

解释：

快速排序是一种分治法排序算法。它的基本思想是选择一个基准元素，将数组分成两个子数组，分别是小于基准元素的元素和大于基准元素的元素，并递归排序这两个子数组。在快速排序中，通常使用数组中间的元素作为基准元素，称为枢轴（pivot）。

快速排序的具体实现如下：

1. 选取基准元素，将数组分成两个部分，左半部分为小于等于基准元素的元素，右半部分为大于基准元素的元素。

2. 递归地对左半部分和右半部分进行排序。

3. 当左右半部分都有序时，整个数组也就有序了。

快速排序的时间复杂度为O(nlogn)，是一种高效的排序算法。