首页 > 代码库 > 算法重拾之路——快速排序

算法重拾之路——快速排序

***************************************转载请注明出处:http://blog.csdn.net/lttree********************************************



第一章:分治与递归


快速排序


算法描述:

同合并排序一样,就是对于一堆数据进行排序。

快排的原理就是,找一个标准,以这个标准为中心进行扩展。就像以前 做操 的时候,老师会说,以XXX为基准,成体操队形散开,这时,XXX左右的人分别就会向它看齐,并向外扩散。快排原理也差不多,最原始的是以得到的第一个元素为标准,然后比这个元素小的在它左面,大的在右面。

注意,这里的第一个元素,是传进来的参数中最左面的元素,并非是整个数组的第一个元素。

总体来说就是三个步骤

<1>Divide(分解):数组内一个元素a[m]为基准,把整个数组a[0:n-1]分成三个部分:数组内所有小于a[m]的元素集合a[0:m-1],a[m],数组内所有大于a[m]的元素的集合a[m+1,n-1]。

<2> Conquer(递归求解):通过递归调用快速排序算法分别对 a[l:m-1] 和 a[m+1,r]进行排序

<3> Merge(合并):因为对a[l:m-1]和a[m+1,r]排序是就地进行,所以不需要执行其他任何计算就已经合并完成。


程序代码:

template <class Type>
void Swap(Type& a,Type& b)
{
    Type temp = a;
    a = b;
    b = temp;
}

template <class Type>
int Partition(Type arr[], int l ,int r )
{
    // 给的初始数据是这样的,比如arr有6个数,l为0,r为5,
    // 就是对数组下表为0~5的位置(共6个元素)进行排序
    int i = l , j = r+1 ;
    Type temp = arr[l];

    while( true )
    {
        // 从前往后找,小于第一个元素(temp)的数下标
        while( arr[++i] < temp && i < r );
        // 从后往前找,大于第一个元素(temp)的数下标
        while( arr[--j] > temp );
        if( i >= j )    break;
        // 将两个下标元素数交换
        Swap(arr[i],arr[j]);
    }
    // 最后将第一个元素的数放在中间
    arr[l] = arr[j];
    arr[j] = temp;
    return j;
}

template <class Type>
void QuickSort( Type arr[] , int l , int r )
{
    if( l < r ) {
        int m = Partition(arr,l,r);
        QuickSort(arr,l,m-1);
        QuickSort(arr,m+1,r);
    }
}


算法分析:

快排的运行时间与划分是否对称有关,最坏的情况发生在 划分过程的两个区域分别包含1个和n-1个元素的时候。因为函数Partition函数的计算时间为O(n),所以假设Partition函数的每一步划分都是最不对称划分,则计算时间的复杂度T(n)为:

T(n)= O(1) 当n≤1

=T(n-1)+O(n) 当n>1

解这个递归方程可以得到 T(n) = O(n^2)

但如果最好的情况下,每次划分都是均等划分,则此时计算时间复杂度T(n)为:

T(n)= O(1) 当n≤1

=2*T(n/2)+O(n) 当n>1

解这个递归方程可以得到T(n) = O(nlog(n))

而且经过证明,平均复杂度也是O(nlog(n)),这在基于比较的排序算法中,算是快速的,因而得名快速排序。


算法优化:

对于快速排序的优化,就是对于基准的的优化。在算法分析中也可以看出,一个好的基准的是非常重要的,所以它的优化就在于此。

在上述函数中,用一个random获取一个下标位置,而不是用第一个元素的值。





***************************************转载请注明出处:http://blog.csdn.net/lttree********************************************


算法重拾之路——快速排序