题目描述

对于这个模板我有话说。

第一个问题：有人提出为什么不是QuickSort(q, l, j - 1), QuickSort(q, j + 1, r);
关于这个题我罗列了一下输入

7
7 5 2 3 4 6 9

每次排序后的结果为

6 5 2 3 4 
7 9 
4 5 2 3 
6 
3 2 
5 4 
2 
3 
2 3 4 
5 
2 3 4 5 6 7 
9 
2 3 4 5 6 7 9 

大家可以看出，第一次我选择的分界元素是7，然而第一次排序后，你看到的j是4，j + 1 == 7，这个j != 7,但是很多人会说，j + 1 == 7呀，好的，我们可以试试QuickSort(q, l, j), QuickSort(q, j + 2, r);嘿嘿，这个结果也是不对的。

第二个问题，为什么j不能换成i，我做了一个小小的实验
输入

5
3 1 2 4 5

每次排序后我输出了i和j

i = 2 j = 1
i = 1 j = 0
i = 3 j = 3
1 2 3 4 5 

i和j的值不一样，具体原因还需要模拟试试。

第三个问题能不能把do while换成while,此处可以看出结果是不对的，那么为什么不对呢，大家来找茬 hh

算法1

(快排) $O(nlogn)$

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void QuickSort(vector<int> &q, int l, int r)
{
    if(l >= r) return;

    int i = l - 1, j = r + 1, x = q[l];
    while(i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if(i < j) swap(q[i], q[j]);
        else break;
    }
    for(int k = l; k <= j;  k ++ ) cout << q[k] << ' ';
    cout << endl;
    for(int k = j + 1; k <= r;  k ++ ) cout << q[k] << ' ';
    cout << endl;
    QuickSort(q, l, j), QuickSort(q, j + 1, r);
}

int main()
{
    int n;
    cin >> n;
    vector<int> input(n, 0);
    for(int i = 0; i < n; i ++ ) cin >> input[i];
    QuickSort(input, 0, n - 1);
    for(int i = 0; i < n; i ++ ) cout  << input[i] << ' ';
    cout << endl;

    return 0;
}

在分享一个错误的代码模板

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void QuickSort(vector<int> &q, int l, int r)
{
    if(l >= r) return;

    int i = l , j = r, x = q[l];
    while(i < j)
    {
        while (i <= r && q[i] < x) i ++ ;
        while (j >= l && q[j] > x) j -- ;
        if( i < j) swap(q[i], q[j]);
        else break;
    }
    QuickSort(q, l, j), QuickSort(q, j + 1, r);
}

int main()
{
    int n;
    cin >> n;
    vector<int> input(n, 0);
    for(int i = 0; i < n; i ++ ) cin >> input[i];
    QuickSort(input, 0, n - 1);
    for(int i = 0; i < n; i ++ ) cout  << input[i] << ' ';
    cout << endl;

    return 0;
}

错误模板改改就对了，代码如下

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void QuickSort(vector<int> &q, int l, int r)
{
    if(l >= r) return;

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

int main()
{
    int n;
    cin >> n;
    vector<int> input(n, 0);
    for(int i = 0; i < n; i ++ ) cin >> input[i];
    QuickSort(input, 0, n - 1);
    for(int i = 0; i < n; i ++ ) cout  << input[i] << ' ';
    cout << endl;

    return 0;
}