1、算法思想

快速排序是一种基于分治策略的排序思想，分治法的思想:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。而快排的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分比令一部分的所有数据都要小。然后按照同样的方法分别对这两部分进行快速排序，这个风格排序过程是递归进行，从此使整个数据变成有序序列。

2、算法模拟

假设要排序的数组是a[1]...a[n]，首先任意选取一个数据（通常为第一个数据）作为关键数据，然后将所有比它小的数放在它前面，将所有比它大的数放在它后面，这就是一趟快速排序的过程。

1. 设置两个变量i、j。排序开始时i=0，j=n。
2. 以第一个数组元素作为关键数据，赋值给x。即x=a[0]。
3. 从j开始向前搜索，找到第一个小于x的值，两者交换。
4. 从i开始向后搜索，找到第一个大于x的值，两者交换。
5. 重复第3、4步，直到i>=j。

3、代码实现

//快速排序
void quickSort(int left,int right){
    int i=left;
    int j=right;
    int t;
    int temp=a[left];//把左边第一个元素设置为基底

    if (left>right) //一定要加上这个条件判断，不然的话递归可能出不来。
    {
        return;
    }
    
    while (i!=j)
    {
        while (a[j]>=temp&&i<j)
        {
            j--;
        }
        while (a[i]<=temp&&i<j)  //相当于两个指针都在动
        {
            i++;
        }
        //交换两个数在数组中的位置
        if (i<j)
        {
            t=a[i];  
            a[i]=a[j];  
            a[j]=t; 
        }
    }
    //将基数归位
    a[left]=a[i];
    a[i]=temp;
    quickSort(left,i-1);
    quickSort(i+1,right);
}

4、算法复杂度

• 时间复杂度：快排的时间主要耗费在划分操作上，从上述代码看，快排的趟数取决于递归的深度。在最好的情况下，每次划分的序列是等长的。复杂度为O（nlog2n）。最坏的情况下，待排序序列正序或者逆序，每次划分只得到一个比上次划分少一个记录的子序列。此时，必须经过n-1次的递归调用才能把所有记录定位。因此最坏情况下是O（n²）。

由此可见快排对初始序列很敏感。

• 空间复杂度：由于快排是递归的，需要用系统栈来保存每一层递归的必要信息。其最大容量与递归的深度一致。最好情况下栈深为O（log2n）；最坏情况下，进行n-1次比较，栈深为O（n）。

5、快排适用性

该方法适用于待排序记录个数很大且原始记录随机排列的情况。快排的平均性能是迄今为止所有内排序算法中最好的一个。像Unix系统库函数中的qsort函数就是快排。