快速排序（1）基本算法实现

浏览数：20 / 时间：2015年06月08日

1. 基本算法

1.1 算法原理

快速排序是一种分治排序算法。它将数组划分为左右两个部分，然后分别对这两部分排序。关键在划分的过程中，它将重排数组，使的以下条件成立：

对于某个划分元素指针 i ,a[i]将处于排序后数组的最终的位置上
a[l],……，a[i-1] 中的元素都比a[i]小
a[i+1],……，a[r] 中的元素都比a[i]大

我们通过划分完成排序，然后递归的调用该方法处理子文件，每一次划分都会至少使一个元素放到它最终的位置上。

void quick_sort(Item a[], int l, int r)
{
    if(r <= l)
        return;
    Item v = a[r];
    int i = partation(a, l, r);
    quick_sort(a, l, i-1);
    quick_sort(a, i+1, r);
}

1.2 划分的实现过程

1.任选 a[r] 作为划分元素，这个元素在划分后处于它的最终位置上 v = a[r];
2.从数组左端开始扫描，直到找到一个比划分元素大的元素；同时，从数组右侧开始扫描，直到找到一个比划分元素小的元素停止。
3.步骤2中使扫描停止的这2个元素在最终划分数组中的位置是反的，因此交换这2个元
4.继续步骤2和3，保证位于划分元素指针左侧的元素都比 v 小，位于右侧的都比 v 大。
5.当扫描指针相遇时，交换划分元素到它的最终位置，此次划分完成
[注] 以上相等的元素也会被交换，后面会有改进算法处理重复元素

int partation(Item a[], int l, int r) //划分函数             
{
    int i = l-1, j = r;
    Item v = a[r];
    for(;;)
    {
        while(less(a[++i], v));
        while(less(v, a[--j]))
            if(j == l) //v是数组中的最小值
                break;
        if(j <= i) //i, j相遇
            break;
        exch(&a[i], &a[j]);
    }
    exch(&a[i], &a[r]); //交换划分元素到它最终位置
    return i;
}