存在问题

快排模板中，

int mid = (l + r + 1) / 2，q[mid]与q[i]、q[j]比较

int x = q[(l + r + 1) / 2]，x与q[i]、q[j]比较

这两者看起来等价，但前者是错误的。

错误样例：

分析过程

数据：

0 1 2 3 4 5 6 7 8 9
49 59 88 37 98 97 68 54 31 3
i j mid q[mid]
初始 0 9 5 97

quick_sort(q, 0, 9)

i、j指针移动到i:4 j:9

0 1 2 3 4 5 6 7 8 9
49 59 88 37 98 ==97== 68 54 31 3

交换->swap(q[4], q[9])

由于i小于j（i:4 j:9），继续移动

0 1 2 3 4 5 6 7 8 9
49 59 88 37 3 ==97== 68 54 31 98

i、j指针移动到i:5 j:8

0 1 2 3 4 5 6 7 8 9
49 59 88 37 3 ==97== 68 54 31 98

交换->swap(q[5],q[8])

i:5 j:8

0 1 2 3 4 5 6 7 8 9
49 59 88 37 3 31 68 54 97 98

到此就可以发现问题的所在了，由于mid = (l + r + 1) / 2，所以比较的q[mid]变成了31,，不是原来的97了。

结论

如果由

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void quick_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r + 1) / 2, i = l - 1, j = r + 1;
    while (i < j)
    {
        do
            i++;
        while (q[i] < q[mid]);
        do
            j--;
        while (q[j] > q[mid]);
        if (i < j)
            swap(q[i], q[j]);
    }
    quick_sort(q, l, i - 1);
    quick_sort(q, i, r);
}

由上面的例子可以发现，q[mid]的值在动态变化，从97变成了31，这违背了快排的思想。

所以正确的做法应该是int x = q[(l + r + 1) / 2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void quick_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int x = q[(l + r + 1) / 2], i = l - 1, j = 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, i - 1);
    quick_sort(q, i, r);
}

用一个变量保存下中间的值，然后每次比较，将小于它的放在左边，大于它的放在右边。