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

排序算法

---

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]); //交换划分元素到它最终位置，当指针相遇时a[i],已被检测过，大于v
    return i;
}

划分过程是不稳定的，因为每个元素都有可能被移到大量和它相等的元素（未经检测到）的后面。至今，没有基于数组的快速排序时稳定的。

2. 快速排序算法的性能分析

2.1.最坏情况： $O(\frac{N^2}{2})$次比较

如果调用一个大小为N的有序文件，那么所有的划分都将退化，程序会调用自身N次，每次调用减少一个元素（左侧N-1个，右侧1个……）；

$$N + (N-1) +(N-2) + …… + 2 + 1 = \frac{(N+1)N}{2}$$

2.2 最好情况： $O(Nlg{N})$次比较

如果每次划分都能够恰好把文件分割成大小相等的两部分，即满足分治法
递归树的深度是$lgN$,每层的比较$O(N)$

$$T(N) = 2T(N/2)+N$$
上式中最后一项的$f(N) = N$是用于分解问题的代价（次数）
由主定理的情形2，$f(N)=N=N^{log_22}log^0N$
所以 $$T(N) = N^{log_22}*log^1N=NlgN$$

2.3 平均情况 $O(NlgN)$次比较

直观来看就是，最好情况和最坏情况每层交替出现
在一个差的划分后接一个好的划分,以下配图《算法导论》P99

参考资料

1.《算法：C语言实现》P192
2.《算法导论》P98
3. 主定理：https://www.zybuluo.com/quinn/note/77106