排序算法之------快速排序

以下内容摘自《啊哈，算法》讲解的通俗易懂，大赞作者的文字功底！

一、什么是排序算法

举个例子：现有一组数据 6 1 2 7 9 3 4 5 采用快速排序，具体步骤如下：

首先让变量i、j分别指向最左端和最右端，即i指向6所在的位置，j指向5所在位置。

首先让j开始移动，因为此处设置的基准数是最左边的数，所以需要让哨兵j 先出动（如果不这样做的话，按照下面的步骤，得不到预期效果）

哨兵j 一步一步地向左挪动（即j），直到找到一个小于6 的数停下来。接下来哨兵i 再一步一步向右挪动（即i++），直到找到一个大于6
的数停下来。最后哨兵j 停在了数字5 面前，哨兵i 停在了数字7 面前。

交换前

交换后

到此，第一次交换结束。接下来哨兵j 继续向左挪动（再次友情提醒，每次必须是哨兵j 先出发）。他发现了4（比基准数6 要小，满足要求）之后停了下来。哨兵i 也继续向右挪
动，他发现了9（比基准数6 要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下：

交换前：

交换后：

第二次交换结束，“探测”继续。哨兵j 继续向左挪动，他发现了3（比基准数6 要小，满足要求）之后又停了下来。哨兵i 继续向右移动，糟啦！此时哨兵i 和哨兵j 相遇了，哨兵i 和哨兵j 都走到3 面前。说明此时“探测”结束。我们将基准数6 和3 进行交换。执行过程如下：

i，j相遇：

准备交换：

交换后：

（注意：此时i，j都指向6的位置）

到此第一轮“探测”真正结束。此时以基准数6 为分界点，6 左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j 的使命就是要找小于基准数的数，
而哨兵i 的使命就是要找大于基准数的数，直到i 和j 碰头为止。

现在基准数6已经归位，刚好处于序列的第6个位置，在基准数6的左边全部小于6，在基准数的右边全部大于6.现在以6为界将序列分为左右两部分，分别对左右两部分递归执行

以上算法，直到最终只有一个数字为止（只剩下一个数字也就不用比较啦）

快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了

整个排序过程如下：

二、算法分析

快速排序之所以比较快，是因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全
部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换，交换的距离就大得多了。因此总的比较和交换次数就少了，速度自然就提高了。

当然在最坏的情况下，仍可能是相邻的两个数进行了交换。

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

以下是一个博客详细分析的复杂度，原文地址：http://blog.csdn.net/yuzhihui_no1/article/details/44198701

时间复杂度

快速排序涉及到递归调用，所以该算法的时间复杂度还需要从递归算法的复杂度开始说起；

递归算法的时间复杂度公式：T[n] = aT[n/b] + f(n) ；对于递归算法的时间复杂度这里就不展开来说了；

最优情况下时间复杂度

快速排序最优的情况就是每一次取到的元素都刚好平分整个数组(很显然我上面的不是)；

此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间；

下面来推算下，在最优的情况下快速排序时间复杂度的计算(用迭代法)：

T[n] = 2T[n/2] + n ----------------第一次递归

令：n = n/2 = 2 { 2 T[n/4] + (n/2) } + n ----------------第二次递归

= 2^2 T[ n/ (2^2) ] + 2n

令：n = n/(2^2) = 2^2 { 2 T[n/ (2^3) ] + n/(2^2)} + 2n ----------------第三次递归

= 2^3 T[ n/ (2^3) ] + 3n

......................................................................................

令：n = n/( 2^(m-1) ) = 2^m T[1] + mn ----------------第m次递归(m次后结束)

当最后平分的不能再平分时，也就是说把公式一直往下跌倒，到最后得到T[1]时，说明这个公式已经迭代完了（T[1]是常量了）。

得到：T[n/ (2^m) ] = T[1] ===>> n = 2^m ====>> m = logn；

T[n] = 2^m T[1] + mn ；其中m = logn;

T[n] = 2^(logn) T[1] + nlogn = n T[1] + nlogn = n + nlogn ；其中n为元素个数

又因为当n >= 2时：nlogn >= n (也就是logn > 1)，所以取后面的 nlogn；

综上所述：快速排序最优的情况下时间复杂度为：O( nlogn )

最差情况下时间复杂度

最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)

这种情况时间复杂度就好计算了，就是冒泡排序的时间复杂度：T[n] = n * (n-1) = n^2 + n;

综上所述：快速排序最差的情况下时间复杂度为：O( n^2 )

平均时间复杂度

快速排序的平均时间复杂度也是：O(nlogn)

空间复杂度

其实这个空间复杂度不太好计算，因为有的人使用的是非就地排序，那样就不好计算了（因为有的人用到了辅助数组，所以这就要计算到你的元素个数了）；我就分析下就地快速排序的空间复杂度吧；

首先就地快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；

最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况

最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况

还有个问题就是怎么取哨兵元素才能不会让这个算法退化到冒泡排序，想想了还是算了吧，越深入研究就会有越多感兴趣的问题，而我又不是搞算法分析的，所以就先这样吧。

具体代码如下（个人写的，不是原文作者的）：

#include<stdio.h> 
#include<string.h>
#define N 100
 
void quickSort(int array[],int left,int right)
{ 
    int i = left;
    int j = right;
    int value = array[left],temp;    // 得到哨兵元素
    // 异常处理，保证right >= left 
    if(left>right)
        return;
    
    while(i < j)
    {
        // 从右向左找一个比基准数小的 
        while(value<=array[j] && i<j) j--;
        // 从左到右找一个比基数大的
        while(value>=array[i] && i<j)  i++;
        // 当i，j没相遇时  交换两者位置
        if(i < j)
        {
            temp = array[j];
            array[j] = array[i];
            array[i] = temp;
        }
        
    }    
    // 最终基准归位 
    if(i == j)
    {
        array[left] = array[i];
        array[i] = value;
    } 
    
    // 递归调用基准数划分的左右两组序列
    quickSort(array,left,i-1);
    quickSort(array,i+1,right); 
    
}

void print(int array[],int len)
{
    int i;
    for(i=0;i<len;++i)
        printf("%d	",array[i]);
}
int main()
{
    int n,i,array[N]; // n表示要输入排序元素的个数
    scanf("%d",&n);
    for(i=0;i<n;++i)
    {
        scanf("%d",&array[i]);
    } 
    
    // 调用排序函数
    quickSort(array,0,n-1);
    //打印函数 
    print(array,n);
    printf("
");
    return 0;
}

测试用例如下：