「三分钟系列01」3分钟看懂快速排序_离散数学 快速排序

排序算法千千万，只有快排的性能和优化后的泛化性质最好，在介绍快速排序前，先看看这张排序天梯图：

 

什么是快速排序？

快速排序是冒泡排序的改进版，也是最好的一种内排序，在很多面试题中都会出现，也是作为程序员必须掌握的一种排序方法。快速排序简单的说就是选择一个基准，将比起大的数放在一边，小的数放到另一边。对这个数的两边再递归上述方法。

 

思想:

1.待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素中随机选取一个作为,称为“枢轴”(pivot)。

2.基于这个值，将数组分为两部分，大的元素放在它的右边，比其小的放在它的左边。

3.可以肯定，如此一轮下来，这个枢轴的位置一定在最终位置上。

4.对两个子数组分别递归上述过程，直到每个数组只有一个元素。

5.排序完成。

 

下面再看看示图理解下吧：

 

 

下面是一个动态图，摘自WIKI，非常形象的解释了这一过程。

 

 

算法分析

 

 

算法性能/复杂度

可以看出，每一次调用partition()方法都需要扫描一遍数组长度（注意，在递归的时候这个长度并不是原数组的长度n，而是被分隔出来的小数组，即n*(2^(-i))），其中i为调用深度。

而在这一层同样长度的数组有2^i个。那么，每层排序大约需要O(n)复杂度。而一个长度为n的数组，调用深度最多为log(n)层。二者相乘，得到快速排序的平均复杂度为O(n ㏒n)。通常，快速排序被认为是在所有同数量级的排序方法中，平均性能最好。

 

算法初步优化

上面这个快速排序算法可以说是最基本的快速排序，因为它并没有考虑任何输入数据。但是，我们很容易发现这个算法的缺陷：这就是在我们输入数据基本有序甚至完全有序的时候，这算法退化为冒泡排序，不再是O(n㏒n)，而是O(n^2)了。

可以看出，每一次调用partition()方法都需要扫描一遍数组长度（注意，在递归的时候这个长度并不是原数组的长度n，而是被分隔出来的小数组，即n*(2^(-i))），其中i为调用深度。

而在这一层同样长度的数组有2^i个。那么，每层排序大约需要O(n)复杂度。而一个长度为n的数组，调用深度最多为log(n)层。二者相乘，得到快速排序的平均复杂度为O(n ㏒n)。通常，快速排序被认为是在所有同数量级的排序方法中，平均性能最好。

从代码中可以很容易地看出，快速排序单个栈的空间复杂度不高，每次调用partition方法时，其额外开销只有O(1)。所以，最好情形下快速排序空间复杂度大约为O(㏒n)。

 此外，快速排序需要一个递归栈，通常情况下这个栈不会很深，为log(n)级别。但是，如果每次划分的两个数组长度严重失衡，则为最坏情况，栈的深度将增加到O(n)。此时，由栈空间带来的空间复杂度不可忽略。如果加上额外变量的开销，这里甚至可能达到恐怖的O(n^2)空间复杂度。所以，快速排序的最差空间复杂度不是一个定值，甚至可能不在一个级别。

为了解决这个问题，我们可以在每次划分后比较两端的长度，并先对短的序列进行排序（目的是先结束这些栈以释放空间），可以将最大深度降回到O(㏒n)级别。

 

算法稳定性

快速排序并不是稳定的。这是因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。

 

代码实现（基础版本）

void quick_sort(int *a, int left, int right)
{
    
    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }
 
    int i = left;
    int j = right;
    int key = a[left];
      
    while(i < j)                               /*控制在当组内寻找一遍*/
    {
        while(i < j && key <= a[j])
        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
        序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/ 
        {
            j--;/*向前寻找*/
        }
          
        a[i] = a[j];
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
        a[left]，那么就是给key）*/
          
        while(i < j && key >= a[i])
        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
        因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        {
            i++;
        }
          
        a[j] = a[i];
    }
      
    a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
    quick_sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    quick_sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
                       /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}

 

此外，对于快排的优化也是一个很有趣的内容，具体可以参考我的下一篇博客~

 

参考文章：

 

1. Discrete mathematics and its applications, Kenneth H·Rosen 

2.  Introduction to Algorithms, Third Edition, Thomas H.Cormen / Charles E.Leiserson / Ronald L.Rivest / Clifford Stein 

3. 三种快排优化：http://blog.csdn.net/insistgogo/article/details/7785038

4. 快速排序讲解：快速排序的本质

 

---

欢迎大家扫码关注微信公众号「图灵的猫」，除了有更多AI、算法、Python相关文章分享，还有免费的SSR节点和外网学习资料。其他平台（微信/知乎/B站）也是同名「图灵的猫」，不要迷路哦~

---