切分部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int partition(int arr[], int low, int high) {
    int pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) high--;
        // swap(arr[low], arr[high]);
arr[low] = arr[high];

        while (low < high && arr[low] <= pivot) low++;
        // swap(arr[low], arr[high]);
arr[high] = arr[low];
    }
arr[low] = pivot;
    return low;
}

swap包含在头文件<algorithm>中,当然用传统t = a, a = b, b = t的办法也可以。

主体部分:

1
2
3
4
5
6
7
void QSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        QSort(arr, low, pivot - 1); //采用递归的方式对切分后的子数组排序
        QSort(arr, pivot + 1, high);
    }
}

其中,参数low和high表示的是数组元素的下标,分别代表待排序数组的最左端元素和最右端元素(都包括)。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
#include<ctime>
using namespace std;

int main()
{
    srand(time(0));
    int a[100];
    for (int i = 0; i != 100; i++)
        a[i] = rand() % 1000;
    //QSort(a, 0, 100)
    QSort(a, 0, 99); //拳打下标越界,脚踢死循环。

    for (int i = 0; i != 100; i++) {
        cout << a[i] << ' ';
        if ((i + 1) % 10 == 0)
            cout << endl;
    }
    return 0;
}