C++用分治算法快速排序

C++中使用分治算法实现快速排序，其基本思想是：选取一个基准元素，将待排序序列分成两个子序列，使得左边的子序列都小于等于基准元素，右边的子序列都大于等于基准元素，然后对左右两个子序列分别进行递归排序，最终得到有序序列。快速排序的时间复杂度为O(nlogn)。

具体实现步骤如下：
1. 选取一个基准元素，一般是第一个或最后一个元素。
2. 从序列的两端开始向中间扫描，将小于基准元素的元素交换到左边，将大于基准元素的元素交换到右边，直到左右两端相遇。
3. 将基准元素交换到中间位置，此时基准元素左边的元素都小于等于它，右边的元素都大于等于它。
4. 对左右两个子序列分别进行递归排序，直到子序列长度为1或0。

下面是C++代码实现快速排序：

#include<iostream>
using namespace std;

int partition(int r[], int low, int high)//划分函数
{
    int i = low, j = high, pivot = r[low];
    while (i < j) {
        while (i < j && r[j] > pivot) //向左移动 ，停 j--;
        if (i < j) swap(r[i++], r[j]);
        while (i < j && r[i] <= pivot) //向右移动，停 i++;
        if (i < j) swap(r[i], r[j--]);
    }
    return i;//返回最终划分完成后基准所在元素的位置
}

void QuickSort(int R[], int low, int high)
{
    int mid;
    if (low < high) {
        mid = partition(R, low, high);
        QuickSort(R, low, mid - 1);
        QuickSort(R, mid + 1, high);
    }
}

int main()
{
    int i, N;
    int *a;
    cout << "请输入要排序数据的个数：";
    cin >> N;
    a = new int[N];
    cout << "请输入要排序数据：";
    for (i = 0; i < N; i++) cin >> a[i];
    cout << endl;
    QuickSort(a, 0, N - 1);
    cout << "排序后序列为：" << endl;
    for (i = 0; i < N; i++) {
        if (i != 0) cout << " ";
        cout << a[i];
    }
    cout << endl;
    return 0;
}