排序算法温习（6）——QuickSort排序

排序算法复习（6）——QuickSort排序

1.基本原理：

（1）使用分而治之法，将数组一分为二（至于怎么分？这就是快速排序的精粹所在、理解的难点所在），然后递归排序子数组。

（2）递归结束的条件是子数组为空或者仅仅含有1个元素！！

关键是找出P的位置，根据该下标把数组A[L,H]分成两半，A[L,P-1]和A[P+1,H]；其中A[L,P-1]中的所有元素小于A[P]，A[P+1,H]中所有元素大于A[P]，但是A[L,P-1]和A[P+1,H]未必就是有序的！然后递归调用即可。

递归结束的条件是子数组为空或者仅仅含有1个元素！！

2、数组如何划分

2.1这里使用的是《编程珠玑》第11章介绍的方法。

2.1.1选取第一个元素为主轴元素

排序算法温习（6）——QuickSort排序

//a[low],a[low+1],...,a[high]
//
static int partition(int* a,int low,int high)
{
    int m = low;
    //use the first element in each array
    int pivot = a[low];
    int pivot_index = low;
    for( int j = low + 1; j <= high ; ++j)
    {
        if ( a[j] < pivot )
        {
            ++m;
            swap(a[m],a[j]);
        }
    }
    swap(a[pivot_index],a[m]);
    return m;
}

/*if we have an array:
\ int a[100];
\ USE quick_sort(a,0,99),NOT quick_sort(a,0,100)
*/
static void quick_sort(int* a,int low,int high)
{
    //assert( a != NULL && n > 0);
    if( low >= high )
        return;

    int q = partition(a,low,high);
    quick_sort(a,low,q - 1);
    quick_sort(a,q + 1,high);
}

2.1.2

2.1.3双向划分

2.1.4小数组上使用insertion sort

2.2这里使用的是《算法导论》第7章介绍的方法。

2.2.1选取A[p..r]中的A[r]为主轴元素

排序算法温习（6）——QuickSort排序

static int partition(int* a,int low,int high)
{
    int x = a[high];
    int i = low - 1;

    for( int j = low; j <= high - 1; ++j)
    {
        if ( a[j] <= x )
        {
            ++i;
            swap(a[i],a[j]);
        }
    }
    swap(a[(i+1)],a[high]);

    return (i+1);
}

2.2.2随机化版本

不是始终采用A[r]为主元，而是从子数组A[p..r]中随机选择一个元素，即将A[r]于从A[p..r]中随机选出的一个元素交换。

static int partition(int* a,int low,int high)
{
    int x = a[high];
    int i = low - 1;

    for( int j = low; j <= high - 1; ++j)
    {
        if ( a[j] <= x )
        {
            ++i;
            swap(a[i],a[j]);
        }
    }
    swap(a[(i+1)],a[high]);

    return (i+1);
}

int random_partition(int* a,int low,int high)
{
    int i = low + ( rand() % (high - low) + 1);
    swap(a[i],a[high]);
    return partition(a,low,high);
}

/*if we have an array:
\ int a[100];
\ USE quick_sort(a,0,99),NOT quick_sort(a,0,100)
*/
static void quick_sort(int* a,int low,int high)
{
    //assert( a != NULL && n > 0);
    if( low >= high )
        return;

    int q = random_partition(a,low,high);
    quick_sort(a,low,q - 1);
    quick_sort(a,q + 1,high);
}

2.2.3Hoare划分法（思考题7-1）

。。。待续

2.2.4三数取中（思考题7-5）

。。。待续

参考：

算法导论

编程珠玑

排序算法温习（6）——QuickSort排序

相关推荐