美文网首页
1.4排序——快排:它到底快不快

1.4排序——快排:它到底快不快

作者: 吃个小烧饼 | 来源:发表于2017-07-12 02:24 被阅读96次

快排是一种使用广泛的排序,它比merge需要的空间更小,而且改进过的快排速度很快,平均O(nlgn)。快排也用到了递归的思想,所以我才说递归很重要的嘛。

我们大概看一下快排的基本过程:选择一个数,把小于它的放左边,不小于它的放右边。没了。那么很显然,这个算法的特点和难点就是“怎么选出一个合适的点”和“怎么实现‘放’”。选择肯定是超重要的,还记得上一节的“递归树”吗,如果采用“二路归并”,在这里就是分为2个序列,那么最好是把分开的点选在中间,因为树高是通过最长路径来计算的。

另一个问题就是怎么实现这个“通过一个点把比它小的全放左边比它大的全放右边”。我们大概可以这样做:一个flag从最左端开始移动,一个flag从最右端开始移动,当碰到一个左侧的点大于被选择点,并且一个右侧的点小于被选择的点时,交换它们。
当然,在执行的时候我们可以把选中的那个点放在数组的最右边,当然也可以不动,比如我们直接选择最左端和最右端的点当作我们的判断点。
那么我们来实现一哈:

//先实现一下主函数
template <typename T>
void QuickSort( T a[ ], int n )
{
    if (n <= 1)
        return;
    Qsort( a, 0, n-1 );
}  //是的,这就完了

哈哈,我们赶紧来实现一哈核心功能Qsort():

template <typename T>
void Qsort( T a[ ], int Left, int Right )
{
    if ( Left >= Right)  //说明已经不能再divide了
        return;
    int i = Left, j = Right;
    T pivot = a[ Left ];  //选最左端点为pivot
    while ( i < j )
    {
        while ( i < j && a[ j ] >= pivot )  //这里需要 i < j 为了控制不过界
            --j;  //当a[ j ]比pivot大时,继续递减,直到减到不满足条件
        a[ i ] = a[ j ];  //把 j 位置上的值赋给 i ,而第一个i正是pivot
        while ( i < j && a[i] >= pivot )
            ++i;
        a[ j ] = a[ i ];  //继上,把这个i赋给j上一次的位置,很巧妙吧
    }
    a[ i ] = pivot;
    Qsort( a, Left, i - 1 );
    Qsort( a, i + 1, Right );  //分别去i-1和i+1,跳过i
}

简单分析一下,
1)为什么要从j开始计算呢?因为我们把pivot设在了最左端,这个位置一定要当作第一个被交换的位置,才能保证程序的顺利运行(所以如果pivot在最右端,你会了吗?)。
2)为什么最后是a[ i ] = pivot;结尾呢?很简单,回到程序,我们先从j计算,再计算i的移动,那么很显然是把i的位置和pivot交换啊~~

不过,正如很多书上所说(就当是吧),因为现实中很多序列并不是完全无序的,取第一个比较冒险,有可能出现最差解,所以有以下2种取法:
1.随机(我感觉挺好的,他们说计算量耗费大)。
2.3数取中值:就是第1,最后,中间3个元素取他们的中值作为pivot。实现方法很简单:

void mid3( T a[], int L, int R )
{
    int C = ( L + R ) / 2;
    if ( a[ L ] > a[ C ] )
        swap( a[ C ], a[ L ] );
    if ( a[ C ] > a[ R ] )
        swap( a[ C ], a[ R ] );
    if ( a[ R ] > a[ L ] )
        swap( a[ R ], a[ L ] );
    swap( a[ C ], a[ Left + 1 ] );
    return a[ Left + 1 ] ;
}

先讲结果:分别把左中右3个数排序,然后把中数放到第2个位置。当然调用的时候也需稍作调整,此处不再赘述。
一个需要注意的地方是:这3个数比较并无特别的规则,只需要两两比较就好了(C32=3而已)。

时间复杂度我就不证了,最坏是O(n2),当每次pivot都取第一个的时候。

堆排序我们先不讲了,等到聊到优先队列的时候再说吧。那么,我们第一个话题似乎就结束了~~

BTW,你有没有觉得用c++写这段代码好多啊,要不然,我们用python大概写一下?

def qsort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a)//2]  # 使用py3.x,2.x的话不需要//
    left = [x for x in a if x < pivot]
    mid = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]
    return qsort(left) + mid + qsort(right)  # 已经实现一次划分了

是不是有点恐怖,这么复杂的算法,仅仅不到10行······

相关文章

网友评论

      本文标题:1.4排序——快排:它到底快不快

      本文链接:https://www.haomeiwen.com/subject/wytmhxtx.html