关于各种排序的一些见解

2017-12-28 16:50:54


众所周知,排序是一种基础算法。新手在入门时几乎都会接触到这类问题,这些问题可以练习对基础语言的掌握能力,如对数组的处理。

排序常见的有冒泡、桶、归并、快排(甚至可以利用优先队列或者是红-黑树)。但是常用的就是归并和快排。

还有一种是一本通上讲的插入排序,复杂度为 ,做法基本和下面冒泡的算法一样。

冒泡的话时间开销有点大,效率也是 ,但有时求数组中的最大值也会用到冒泡的思想,例如

        for(int i=1;i<=n;i++)
        {
            if(a[i]>Max)
                Max=a[i];
        }

桶排也就是开一个数据范围非常大的数组,空间开销非常大,在函数里面一维数组只能开500,000左右,全局数组的话可以开到400,000,000(4亿),但这样的话,在函数里面能排的数据有限,但是排多了又会使空间超限。从另一个角度,在输出结果时,桶排序需要从头到尾遍历,时间复杂度是 。在联赛这种既卡时间又卡空间的情况下,以上两种都不能选。

归并排序的用途比较广,它可以用来求逆序对。和快速排序一样时间复杂度是 用作一般的排序不失为一种很明智的选择。那么现在进入正题,谈一谈常见的快速排序。

快速排序(quicksort)是20世纪60年代提出的一种算法,类似于归并,也有分治的一种思想,即找到一个基准数,将比它大的放在它的右边,比它小的放在它的左边。

  1. 基准数位置。

基准数的位置在教科书中一般选为最左边或最右边,我一般习惯于选最左边。不同选择对执行没有较大的影响。

  1. 左右移动的方式

目前我所见到的移动的方式,主要有两种,

一是j(从右)找到一个比基准数(记作k)小的数,然后让i(从左)找到一个比k大的数,然后进行交换。直到i,j相遇开始分治处理;

            void quick_sort(int x,int y)
            {
                int i=x,j=y,t;//t用于稍后的交换
                int k=a[x];
                if(i>=j)
                    return;
                while (i<j)
                {
                    while((i<j)&&a[j]>=k)
                        j--;
                    t=a[i];
                    a[i]=a[j];
                    a[j]=t;
                    while((i<j)&&(a[i]<k))
                        i++;
                    t=a[i];
                    a[i]=a[j];
                    a[j]=t;
                }
                quick_sort(x,i-1);
                quick_sort(i+1,y);
                return;
            }

另一种是 基准数记作k,基准数下标记作x

① i(从左)找到一个比k大的数,a[x]=a[i];

② j(从右)找到一个比k小的数,a[i]=a[j];

③ i(从左)找到一个比k大的数,a[j]=a[i];

④ 重复②③直到i==j;

⑤ 将a[i]赋值为基准数k;

第一种是快排的原始思想,交换->分治,但是借用了t来交换a[i]和a[j];

第二种的思想巧妙一些,没有用一次三句话操作,而是每次交换,都可以保证a[i]>a[j]。

    void quicksort(int x,int y)
    {
        int i=x,j=y;
        int k=a[x];
        if(i>=j)
            return;
        while(i<j)
        {
            while(i<j&&a[j]>k)
                j--;
            if(i<j)
            {
                a[i]=a[j];
                i++;
            }
            while(i<j&&a[i]<=k)
                i++;
            if(i<j)
            {
                a[j]=a[i];
                j--;
            }
        }
        a[i]=k;
        quicksort(x,i-1);
        quicksort(i+1,y);
    }

以上谈的快速排序两种方法,大致上没有较大区别,只不过在处理交换操作时,一个老老实实用了交换,另一个用了较巧妙的“赋值”,总体上看复杂度不相上下,但是我想当数据较大的时候可能会还是会有所区别。 如有不对的地方,敬请指正。