快速排序是一种基于分治策略的高效排序算法。其基本思想如下：

1. 分解： 选择一个基准元素，将数组分为两个子序列，使得左侧子序列的所有元素都不大于基准元素，右侧子序列的所有元素都大于基准元素。
2. 治理： 对两个子序列分别进行快速排序。
3. 合并： 将排好序的两个子序列合并在一起，得到原问题的解。

方法一

算法步骤：

1. 选取数组的第一个元素作为基准元素 pivot，初始化指针 i 和 j 分别指向数组的左端和右端。
2. 从右向左扫描，找到第一个小于 pivot 的元素，并与 q[i] 交换，然后 i 向右移动一位。
3. 从左向右扫描，找到第一个大于 pivot 的元素，并与 q[j] 交换，然后 j 向左移动一位。
4. 重复步骤 2 和 3，直到 i 和 j 重合。
5. 此时 i 和 j 所指的位置正好是 pivot 元素，递归处理左右两个子序列。

C++代码

void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int x = l + r >> 1, i = l, j = r;
    swap(q[l], q[x]);
    int pivot = q[l];
    while (i < j) {
        while (i < j && q[j] > pivot) j--;
        if (i < j) swap(q[i++], q[j]);
        while (i < j && q[i] < pivot) i++;
        if (i < j) swap(q[i], q[j--]);
    }
    quick_sort(q, l, i - 1);
    quick_sort(q, i + 1, r);
}

方法二

算法步骤：

1. 选择数组中间的元素作为基准元素 x，初始化指针 i 和 j 分别指向数组的左端减一和右端加一。
2. 使用 do-while 循环从左向右找到第一个大于等于 x 的元素，从右向左找到第一个小于等于 x 的元素。
3. 如果 i 小于 j，则交换 q[i] 和 q[j]。
4. 递归处理左右两个子序列。

C++代码

void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j) {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

方法三

算法步骤：

1. 选择数组中间的元素作为基准元素 x，初始化指针 i 和 j 分别指向数组的左端和右端。
2. 使用 while 循环从左向右找到第一个大于等于 x 的元素，从右向左找到第一个小于等于 x 的元素。
3. 如果 i 小于等于 j，则交换 q[i] 和 q[j]，并移动指针。
4. 递归处理左右两个子序列。

C++代码

void quick_sort(int q[], int l, int r) {
if (l >= r) return;
int i = l, j = r, x = q[l + r >> 1];
while (i <= j) {
while (q[i] < x) i++;
while (q[j] > x) j--;
if (i <= j) swap(q[i++], q[j--]);
}
quick_sort(q, l, j);
quick_sort(q, i, r);
}