快速排序

快速排序是很常用的排序方法，它的时间复杂度较理想，平均时间复杂度为O(NlogN)(注：最坏情况下时间复杂度与冒泡排序相同，都是O(N²))。快速排序的本质是二分思想：将一系列数按照某个基准，分为大于它的数和小于它的数，将这两组数分出来后，再用递归的思想使用相同的一段代码再次分数，直到最后完成排序。

具体思路

  1. 选择一个基准数；基准就是判断标准，它决定了大于它和小于它的数会在每一次递归快速排序中被分到基准的两侧(这两侧在下一次递归中分开处理)；一般情况下，基准可以任选，只要它出现在了所需要排序的数字中即可，一般选择数组的第一个元素作为基准，简单方便；
  2. 设计交换方法：这里需要使用两个迭代器(即for循环中的i和j)，想象它们是哨兵；两个哨兵指向数组的[0]和最后一个元素，让远离基准一侧的哨兵首先工作：它通过while或for来检测它每一步遇到的数组元素的大小，如果元素比基准大，那么继续走下一步(这种元素不需要交换，因为它们比基准大，它们现在的位置就是合理的位置)；如果比基准小，那么停下来；接下来让基准那一侧的哨兵出发，检测遇到的数，如果小于基准，则跳过；如果大于基准，则停下来；当两个哨兵没有相遇的时候(使用if判断i!=j)，则交换它们指向的元素。
  3. 重复交换步骤多次，直到两个哨兵相遇(用while循环控制)，当哨兵相遇的时候(i==j)，表明这个时候已经找到了基准应该在的位置，因此让基准与这个位置交换，令基准就位，这时，基准和它两边的数都已经初步就位了(表现在基准左侧都小于基准，右侧皆大于基准)。注意，这并不表明基准左右两侧已经拥有正确的顺序，只是说大小关系；即1、4、2都在基准6的左边，但是不能确定2比4小就以为2在4的左边；
  4. 递归，将基准左侧和基准右侧的元素分别使用递归来处理；

注意事项

  1. 这种算法的思想可以理解为不断地将每一次递归的基准放到中间，要明白每一次递归的基准都是在改变的(每一次递归都将子集的第一个元素作为基准)
  2. 特别注意：必须让远离基准一侧的’哨兵’先走，否则你得到的结果是不正确的[解释见下]
  3. 每一次排序是为了将基准放到它应该在的位置，对其他元素的移动是为了满足大小顺序要求，并不是为了使基准外的其他元素有正确的顺序，只是希望他们满足大小关系而已

为什么要让远离基准的’哨兵’迭代器j先走呢？

考虑这种情况：当i和j相遇前的最后一个元素是小于基准的情况。
先说结果：如果基准这一侧的哨兵现行，会导致错过‘基准应有的位置’，导致基准会被交换到一个不正确的位置，并且这个位置上的数交换到基准的位置之后，会使得基准两侧的大小关系不正确；

例子：我写了一个简单的示例描述这种问题：为了简单明了地描述这个问题，我仅仅使用了快速排序的第一步来描述，并没有进入到递归的环节，因为问题就出在第一步，而且递归里面也是这种问题的重复而已；
对它们排序：6,1,2,7,9,3,4,5,10,8：
[不论使用远离一侧还是靠近基准一侧的哨兵先行，前几步排序的结果是相同的]：如下：进行第一次交换：得到6，1，2，5，9，3，4，7，10，8(5和7交换)
第二次：得到6，1，2，5，4，3，9，7，10，8（4和9交换）
此时焦点聚集到中间的三个数字：4，3，9，此时i指向4且j指向9。
问题出现了：如果错误地让i先走，则此时i依次读取4、3、9三个数，我们把4称为i，3称为i+1而9称为j，此时i+1小于基准(数值6)，因此被跳过，而i遇到j的时候停止移动，不仅是因为j大于基准，还因为两个哨兵相遇必须停止(因为哨兵相遇表明基准就应该交换到这里)。这时按照哨兵相遇时的处理办法，将这个位置与哨兵交换，得到结果就是j与数组[0]交换(即j的位置与基准交换，注意此时i == j)，最终结果就是一个大于基准的数跑到了基准的左侧，导致快速排序错误失败。
总结：当哨兵相遇之前，如果出现相遇位置的数值刚好让左侧哨兵跳过了，那么实际相遇位置不是正确的应该的相遇位置
解决：让远离基准一侧的哨兵先行可以完全避免这种逻辑上的问题

C代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
class:QuickSort
author:zhy
IDE:Windows 10 VSCode
Complire:minGW(gcc-4.8.1)
*/

#include<stdlib.h>
#include<stdio.h>

//交换数组的元素
int swap_array_value(int *a,int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

/*QuickSort*/
//注意，该函数使用了递归，请小心你的堆栈空间的大小、空间复杂度
int quick_sort(int left,int right,int arr[])
{
    int i = left;        //记录需要排序的区间范围
    int j = right;
    int base = left;     //记录基准数的索引位置，这里选择第一个元素作为基准
    int base_value;      //准备记录基准数的值

    if(NULL == arr){     //参数安全检测
        return -1;
    }

    if(i >= j){          //递归结束条件：当左迭代器越过右迭代器时，表明本段排序已完成
        return 1;
    }

    base_value = arr[base];     //(在每一次递归的数组中)取得基准数值

    while(i != j)   //左右两侧的'哨兵'相遇的时候，停止，因为此时已经成功令基准就位
    {
        for(;arr[j] >= base_value && i < j;--j);    //让非基准一侧的哨兵先走
        for(;arr[i] <= base_value && i < j;++i);    //注意判断条件，不能让基准一侧的哨兵越过了另一侧的哨兵
        //由上两个for的条件限定，i是不可能大于j的，但是可能会等于j,因此这里需要判断
        if(i < j){   
            swap_array_value(arr+i,arr+j);      
        //当i!=j的时候才交换i和j,i和j相等的时候交换基准和i(当然因为这个时候i==j，所以交换基准和j也是ok的)
        }       /*跳出while循环，此时i == j*/
    }
    
    /*将基准放到它应该在的位置，将基准与i做交换*/
    swap_array_value(arr+base,arr+i);
    /*可以实现同样的交换功能的代码：*/
    //arr[base] = arr[i];
    //arr[i] = base_value;
    /*相同：*/
    //swap_array_value(arr+base,arr+j);

    //递归，将基准左侧的所有元素作为一个新的范围再进行一次步骤相同的快速排序
    quick_sort(left,i-1,arr);    //注意，此时基准的位置就是i的位置，不再是base了
    quick_sort(i+1,right,arr);

    return 0;
}

int main(int argc,char *argv[])
{
    int iter=0;
    int arr[] = {6,1,2,7,9,3,4,5,10,8};

    quick_sort(0,sizeof(arr)/sizeof(int)-1,arr);    
    //注意，第二个参数必须减一，否则超出缓冲区

    for(iter=0;iter<sizeof(arr)/sizeof(int);++iter)
        printf("%d\t",arr[iter]);
    
    return 0;
}