七大排序算法之快速排序

@(算法笔记)[排序算法, 快速排序, C++实现]

[TOC]

---

快速排序的介绍：

快速排序是C. A. R. Hoare在1962年提出的，平均时间复杂度为O(nlogn)级的高效率算法，也是目前O(nlogn)的排序算法中使用最多的算法，这段时间想把自己学过的算法都整理一遍，于是就写了这篇博客，来记录自己的学习过程吧...也希望能给初学者带来一些帮助。

---

快速排序的核心思想

每次排序都需要以序列的第一个值为关键值，将序列分成两个部分，并且使其中一部分的值都大于关键值，而另一部分的值都小于关键值，然后再分别对两个部分都再次进行本操作，直至某次操作的部分只有一个值。整个排序过程可以通过递归的方式进行，使整个序列变成有序序列。

---

简单例子

初学者们可能无法看懂上面的描述，不过没关系，让我们来举个栗子:

待排序序列：    5   3   7   6   9   1   2
第一轮排序：    2   3   1   5   9   6   7
第二轮排序：    1   2   3   5   7   6   9
第三轮排序：    1   2   3   5   6   7   9
第四轮排序：    1   2   3   5   6   7   9

第一轮快速排序，把上面这个序列分成了两个部分，然后5作为关键值在中间
第二轮快速排序，分别再对之前的两个序列再进行操作，2和9分别是关键值
第三轮中，只有一个值的序列不再进行操作，现在灰色区域的序列
第四轮中，每个部分都只有一个值了，排序结束

由此可见，快速排序要做的事，就是用二分的思想，每次都将待处理的序列分成两个部分，并且保证其中一个序列的值都大于另一个序列的值，显然，将本操作执行完之后，序列自然就都是有序的了，那剩下的问题只有，每轮的操作该如何实现了。

---

每轮快排的具体实现

每轮操作该如何执行？ 我们要做到以O(n)的时间复杂度，做到让序列分成两个部分，该如何实现呢？

其实这个实现起来并不困难，举个栗子：

初始序列：
5   3   7   6   9   1   2    
我们选中第一个数字5作为关键值，然后先从后往前找比关键值小的数
5   3   7   6   9   1   2
此时我们找到了数字2，它比关键数5要大，于是我们让它和关键数交换
2   3   7   6   9   1   5
关键数到了后面，我们锁定5，转换方向，再从前面开始找比5大的数
2   3   7   6   9   1   5   
此时我们找到了数字7，交换
2   3   5   6   9   1   7    
之后再转换方向，从上一次找到的位置从后往前找比关键值小的数1，交换
2   3   1   6   9   5   7    
与1交换，再从1往后找比5大的数，找到了6，交换
2   3   1   5   9   6   7     
5之后，6之前已经没有比关键字大的数了，结束

这样子一轮操作就结束了，我们也确实在O(n)的时间复杂度内，实现将数组分成两个序列了，看着这个栗子是不是有点天昏地转的感觉？哈哈，没事的，习惯就好了。

用语言来描述每轮的操作就是：锁定一个数为关键数，然后先从尾部往前找比第一个比关键数小的数，找到了交换并交换方向，没找到就结束本轮操作。换方向后，从刚刚交换的位置再往后/前找，找到第一个比关键数大/小的数，交换，直到没找到符合条件的数为止，本轮操作结束。

---

时间复杂度的讨论

上面的介绍中已经提到了，快速排序算法的时间复杂度是O(nlogn)，现在我们来简单地分析一下：

可见，虽然每轮操作中，待处理的序列段会逐渐变多，但需要处理的数字的数量是不会增加的，所以只要让操作的时间复杂度都是O(n) 就行了（此处的n是每段待处理的序列中数值的数量），这样就能保证每轮的时间复杂度都是O(n)。

接着再来讨论算法需要执行几轮：在数列足够乱序的情况下，我们假设每个部分操作完了之后，都会产生左右两个序列，即构造成一个满二叉树，在这个前提下，我们执行n轮，就能解决2的n次方个数的排序。所以只需进行logn次操作就能得到答案。当然，这个前提有点苛刻。但在平均情况（随机序列）下，执行的轮数的数量级都是logn，所以，我们说快速排序的平均时间复杂度是O(nlogn)。

有最好的情况，肯定也有最坏的情况，对快速排序来说，最坏的情况就是待排序的数组本身有序（顺序逆序都是），每次操作的时候，都会出现所有的数都在关键值的同一边的尴尬的情况，使得这个二叉树成了一个单向链表，那么操作的轮数就是n轮了，在这种极端的情况下，快速排序的时间复杂度就是O(n^2)了。

---

代码

    #include<cstdio>  
    #include<iostream>  
      
    using namespace std;  
      
    int a[100005];  
      
    void swap(int n,int m)  
    {  
        int temp=a[n];  
        a[n]=a[m];  
        a[m]=temp;  
    }  
      
    int partition(int p,int q)  
    {  
        int n=q,s=1;//n为临时变量，s为记录方向的变量  
        while(p!=q)//只要p和q两变量不相等，就代表没找完  
        {  
            if( s && a[n]<a[p]) //s判断方向  
            {  
                s=!s;//找到了，改变方向  
                swap(n,p);//交换  
                n=++p;  
            }  
            else if( s && a[n]>=a[p])//小于的话移一位  
            {  
                n=--q;  
            }  
            else if( !s && a[n]>a[q])//与上面同理  
            {  
                s=!s;  
                swap(n,q);  
                n=--q;  
            }  
            else if( !s && a[n]<=a[q])  
            {  
                n=++p;  
            }  
        }  
        return n;  
    }  
      
    void qsort(int p,int q)  
    {  
        int j=partition(p,q);//进行划分操作  
      
        //两个部分再次进入递归  
        if(p!=j) qsort(p,j-1);  
        if(q!=j) qsort(j+1,q);  
    }  
      
    int main()  
    {  
        int t;  
        scanf("%d",&t);  
        int i=0;  
        for(i=0;i<t;i++)//输入数据  
        {  
            scanf("%d",&a[i]);  
        }  
      
        qsort(0,t-1);//进行快速排序  
      
        for(i=0;i<t;i++)//输出数据  
        {  
            printf("%d ",a[i]);  
        }  
          
        return 0;  
    }