提出

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序，它有一种比较重要的思想——分治思想。大致可以描述为，确保一组序列中存在一个特别的数据，其左边的数据都比他大（小），右边的数据都比它小（大），那么可以将这个数作为基准数，在其左边和右边分别再次确保一个数满足同等关系，直到区间大小为1，则排序完成。

时间复杂度

O(N*logN)

步骤

1. 选取基准数
2. 以基准数为中心点进行分区，左边分区比基准数小（大），右边分区比基准数大（小）。
3. 每个分区递归完成上述规则，直到分区大小为1。

代码实现

快速排序实现方式多样，这里对本实现方式做简要介绍。

在这里为实现代码简洁，选取第一个数作为基准数，如需设置其他位置的数作为基准数，则只需要将该位置的数与第一个数交换位置即可。

初始情况：

首先保存基准数的值( tmp = arr[s] )，然后从最右边查找第一个小于等于基准数的值，并将该值保存到基准值的位置（基准值已保存，所以可以直接将该值覆盖，红色覆盖蓝色），并将基准值位置向右偏移一位（s++），由于基准值以第一个数开始，则可以理解为将小值往右边扔。执行完成结果应当是这样：

此时可以看到有两个数值8，我们可以理解为，可以在右边的8头上随便动土~

因此，我们开始从基准值位置开始向右移动，直到找到第一个比基准值大的数。然后去欺负右边的8，直接覆盖掉他，然后右边界限减1（e–）。数组此时变为：

可以很直观的发现，此时有两个423，话不多说，从右边开始找小于基准值的数，盘他。

这样，我们始终保持一个可改变的数值去容纳查找到的符合规定的值，直到基准值到达右界限（ s >= e ）并将基准值赋予该位置( arr[s] = tmp )。则满足基准值左右分治条件（左边小与基准值，右边大于基准值）。结果为：

最后，划分左右分区，实行递归即可。

/*快速排序
 *C/C++
*/

#include <iostream>

using namespace std;


int quick_sort( int *arr, int start, int end )
{
    int s = start, e = end;//记录分区信息
    //swap(arr[s],arr[(s+e)]/2);
    int tmp = arr[s];//保存基准值
    
    if ( s >= e )
    {
        return 0;
    }

    while ( s < e )
    {
        while ( s < e && arr[e] )//从右向左查找第一个小于等于基准值的数
        {
            if ( arr[e--] <= tmp )
            {
                arr[s++] = arr[++e];//将该值往区间最右边移动
                break;
            }
        }

        while ( s < e && arr[s] ) //从左向右查找第一个大于基准值的数
        { 
            if ( arr[s++] > tmp )
            {
                arr[e--] = arr[--s];//将该值往区间最左边移动
                break;
            }
        }
    }

    arr[s] = tmp;//将基准值填入对应位置
    quick_sort( arr, start, s - 1 );//递归左分区
    quick_sort( arr, s + 1, end );//递归右分区
    return 0;
}

int main()
{
    int arr[] = {15, 3, 432, 23, 32, 13, 6, 3256, 5567, 12, 8, 987};
    int end = sizeof( arr ) / sizeof( arr[0] ) - 1;
    int start = 0;//此处以第一个数作为基准数，若以其他数（如中间数）作为基准数，则应实现并打开修改swap注释。
    quick_sort( arr, start, end );

    while ( start <= end )
    {
        cout << arr[start++] << endl;
    }

    return 0;
}

执行结果