快速排序

  #返回上一级

@Author: 张海拔

@Update: 2014-04-30

@Link: http://www.cnblogs.com/zhanghaiba/p/3515078.html

我们知道，三种基本排序算法（冒泡、选择、插入）可以看做减治算法（待排序规模规模不增减小）

而快速排序和归并排序是基于分治的思想，当你画出递归树的时候，容易看出每趟排序的效率均为O(n)，而规模并不线性递减，而是以lg(n)的速度递减；

这也正是这两种基于分治思想排序算法的高效之处。

快速排序属于交换排序方法，可以说是对冒泡排序的改进。

首先你必须知道分治法，通过“冒泡”（划分过程），使得枢纽元素p的左边元素都<=p，右边元素都>=p。此时枢纽元素的最终位置已经完全确定。

一次划分后，左边部分的数组和右边部分部分的数组都是一个规模变小的原问题。因此，用递归处理这个问题是很自然的事情。

这种二分递归的场景，很容易联系到二叉树的遍历。

其实，快排过程就可以画一棵二叉树来描述，树没有扩展时是一个数组，扩展后（划分完毕）则树根是已经确定位置的元素。

那么，整个过程就是二叉树的前序遍历，在访问当前根之前就进行数组划分（即树的扩展）。

当你画出了快速排序的二叉树，不难分析出效率——

假定树的严格平衡的，那么每一层的划分遍历效率都是O(n)，而二叉树的高度是logn，所以快速排序的最好效率是O(n*logn)。

至于划分函数，有很多的实现方法。比较朴素的实现就是大量通过swap()函数，毕竟快速排序一般归类为交换排序方法。

划分函数对应着一趟排序，这个过程可以看做“冒泡”，但这个泡在左右跳跃，并且幅度越来越小，最后停在一个位置，左边都比这个泡“轻”，右边都比这个泡“重”。

我这里的划分函数优化了交换过程，效率会更好一些。

我们知道，递归的划分目标是：使得一个元素p，使得其左边的元素均<=p，右边的元素均>=p。该元素p成为枢纽元素。

假定待排序数组是随机的，那么中枢元素选择数组最左边的元素即可。

首先，保存当前数组的最左元素a[l]为p。

然后，设置两个指针i, j，分别指向当前数组最左元素a[l]，和最右元素a[r];

最初，a[i]是一个可以被覆盖的元素（其值保存在p中），所以我们从数组的最右端开始扫描(j--)，目的是找到比p小的首个元素a[j]，该元素的值保存到a[i]元素中；

但是这可以保证a[i]是落在p元素的左边吗？显然我们首先需要始终保证i < j，并且a[i]被覆盖后，a[j]就是一个可以被覆盖的元素了。

此时需要从a[i+1]开始往左扫描(i++)，目的是找到比p大的首个元素a[i]， 以覆盖a[j]，这个过程的中止条件是i == j。

中止的条件，也满足数组只有一个元素的情景。这个位置的元素值就是枢纽元素的值，此时执行a[i] = p;

上述过程可以抽象成一个devide函数如下：

int devide(int *array, int left, int right)
{
    int i = left, j = right; p = array[left];
    while (i < j) {
        while (i < j && a[j] >= p)
            ++j;
        if (i < j) // 执行判断前，一定有a[j] < p
            a[i++] = a[j];
        while (i < j && a[i] <= p)
            ++i;
        if (i < j) // 执行判断前，一定有a[i] > p
            a[j--] = a[i];
    }
    // 跳出循环，则一定满足i == j
    a[i] = p;
    return i;
}

有了devide函数，那快排的主逻辑就更清晰了：

void quick_sort(int *array, int left, int right)
{
    if (left >= right)
        return;

    int mid = devide(array, left, right);

    quick_sort(array, left, mid-1);
    quick_sort(array, mid+1, right);
}

一般来说，快速排序作为一个抽象元就可以了，devide抽象出来就有些过度了。最终quick_sort Demo如下：

/*
 *Author: ZhangHaiba
 *Date: 2014-1-11
 *File: quick_sort.c
 *
 *a quick sort demo
 *UpDate: 2014-4-30
 */

#include <stdio.h>
#define N 512

//interface
void quick_sort(int* array, int left, int right);
void set_array(int* array, int num);
void show_array(int* array, int num);


int array[N];

int main(void)
{
    int n;

    scanf("%d", &n);
    set_array(array, n);
    quick_sort(array, 0, n-1);
    show_array(array, n);
    return 0;
}

void quick_sort(int *a, int l, int r)
{
    if (l >= r)
        return;

    int i = l, j = r, p = a[l];

    while (i < j) {
        while (i < j && a[j] >= p)
            --j;
        if (i < j)
            a[i++] = a[j];
        while (i < j && a[i] <= p)
            ++i;
        if (i < j)
            a[j--] = a[i];
    }
    a[i] = p;

    quick_sort(a, l, i-1);
    quick_sort(a, i+1, r);
}


void set_array(int *a, int n)
{
    int i;
    
    for (i = 0; i < n; ++i)
        scanf("%d", a+i);
}

void show_array(int *a, int n)
{
    int i;
    
    for (i = 0; i < n; ++i)
        printf(i == n-1 ? "%d
" : "%d ", a[i]);
}

最后我们再看看K&R的一个quick_sort实现

void quick_sort_KandR(int *a, int left, int right)
{
    if (left >= right) return;
    int last = left, i = left+1;
    for (i <= right; ++i)
        if (a[i] < a[left])
            swap(a, ++last, i);
    swap(v, left, last);
    quick_sort_KandR(a, left, last-1);
    quick_sort_KandR(a, last+1, right);
}

/*
我们要使a[last]元素左边均<=它，右边均>=它
首先，我们设中枢元素为a[left],
然后，我们使a[left+1~last]中元素均<= a[left], a[last+1~right]均>=a[left]
最后，交换a[left]与a[last]即可。
a[last]为向右遍历过程中最后出现的<=a[left]的元素，为了不覆盖已知的<=p[left]元素，所以++last
*/

 #返回上一级