七大排序算法之快速排序

c/c++

浏览数:173

2019-3-30

AD:资源代下载服务

七大排序算法之快速排序

@(算法笔记)[排序算法, 快速排序, 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;  
    }