快速排序的一种实现

![qsort][]

背景

什么是快速排序呢?
这个需要先说说一般的排序.
最常见的排序是冒泡排序了, 但是这个排序的时间复杂度是 O(n\^2) 的.
大概意思就是如果有n个数要排序, 就需要 n*n 的时间.
n 比较小的话, 还可以接受, 但是n很大后, 时间久很久了.

那快速排序的复杂度是多少呢? 是 O(n * log(n))
log 是什么概念呢? 大概就是你需要 10\^m 时间才可以排完序, 我只需要大概不到 4 * m 时间就排完序.

快速排序的原理

快排的原理很简单, 把带排序的序列分成两组, 比如左边和右边两组, 而且右边的任何一个数需要不小于左边的所有数.
意思就是右边的数字比左边的数字大.
然后就可以单独对左边和右边的序列单独排序了.

假设长度为 n 的序列排序需要 f(n) 时间, 则使用这个方法的复杂度就是 f(n) = n + 2 * f(n/2).
其中 f(n/2) 大家都可以明白, n 是由于需要给n个数分组, 分组时需要遍历n个数字的.

这里就有个问题了.
怎么对n个数字分组呢?
策略就是选择一个比较因子来当做分界线.
简单的策略就是选择第一个数字当做分界线, 小于第一个的属于左边, 大于等于第一个的属于右边的.
不过这时, 遇到精心构造的数据时, 复杂度有可能就变成 O(n\^2) 了.
什么情况呢? 就是有序的时候呗.

那又没有一种方法, 怎么编数据, 复杂度就可以良好的保持在 O(n * log(n)) 呢?
有的, 那就是随机选择一个比较因子.
关于随机的方法有很多, 后面会说集中比较理想的比较因子.

简单的实现

为什么说是简单的实现呢?
因为我就是选择第一个当做比较因子的.

我们要实现一个函数f(left, right).
这个函数输入时序列的起始位置(left)和结束位置(right).
结束运行的时候, 这个序列需要达到有序.

首先我们开始对这个序列进行分组.

初始状态

首先需要分组的序列(初始状态)是这个样子

key = a[left]
key, a[left+1], ...,a[ right]

目标状态

我们的目标状态时这个样子

a[left],..., a[pos] = key, ..., a[right]

并且key左边的数字都不大于key, key 右边的数字都不小于key.

递归

然后这个时候我们再调用两个子序列, 整个序列就达到了有序的状态.

f(left, pos-1);
f(pos+1, right);

递归出口

出口很简单, left 大于等于 right 的时候.

if(left >= right){
    return;
}

分组

看了上面的代码, 可以看出, 快排的核心就是对序列进行分组.

我们使用 i = left 和 j = right 来标记待分组的序列. 用 key = a[left] 来表示比较因子.

大家可以回头看看上面的分组目标, 然后一般使用递归的方法实现目标.
什么意思呢? 现在的状态时 [i,j] 不满足目标, 比较因子是 i位置的值.
如果状态达到 [i,i] 时, j=i, 那么就满足目标了.

第一步是从右边往左边比较, 找到第一个小于 key 的位置.

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

循环结束时处于这么一个状态

a[i] = key, a[i+1], ..., a[new-j], a[new-j + 1], .., a[old-j]

其中, [i, new-j] 是不满足目标的, 而 [new-j + 1, old-j] 是满足目标的.

而且循环结束的时候有两种情况.

1. i == j
2. a[j] <= key

对于第一种情况, i 右边的值都大于 a[i] = key, 所以整个序列都满足目标了, 分组结束.

对于第二种情况, 我们需要做的是将 a[j] 放到 i 的位置.

则状态变成如下状态

a[i] = key, a[i+1], ..., a[new-j],   a[new-j + 1], .., a[old-j]

=>

a[new-j],   a[i+1], ..., a[i] = key, a[new-j+1],   ... ,a[old-j]

这时可以发现 a[new-j] 和 a[new-j +1],…,a[old-j] 都是满足状态的, 不满足状态的是

a[i+1],..., a[i] = key

此时我们可以再从左向右找到第一个大于key的值的位置.

while(a[i] <= key && i < j) {
    i++;
}

循环结束的时候又是有两种情况.

1. i== j
2. a[i] > key

循环结束时状态如下

a[old-i+1],...,  a[j] = key

=> 

a[old-i+1], ..., a[new-i - 1], a[new-i], ...,  a[j] = key

而且 a[old-i+1], ..., a[new-i - 1]是满足目标的.

第一种情况还是可以结束分组了.
第二种情况和从右向左类似, 交换比较因子和a[i]即可.

a[old-i+1], ..., a[new-i - 1], a[new-i],   ..., a[j - 1], a[j] = key

=>

a[old-i+1], ..., a[new-i - 1], a[j] = key, ..., a[j - 1], a[new-i]

然后这个时候, 我们需要分组的子序列又变成下面的样子了, 和初始状态很类似.

a[i] = key, ..., a[j - 1]

所以对这个序列按上面的方式递归处理即可.

使用循环的代码如下

int i = l, j = r;
int  key;

key = a[i];
while(i < j) {
    // a[i] = key
    while(a[j] >= key && i < j) {
        j--;
    }

    //  a[j] < key a[i] = key
    if(i < j) {
        swap(a[i], a[j]);
        i++;
    }
    
    // a[j] = key
    while(a[i] <= key && i < j) {
        i++;
    }

    //  a[i] > key a[j] = key
    if(i < j) {
        swap(a[i], a[j]);
        j--;
    }
}

简单优化

为了方便大家理解, 所以把上面的逻辑过程写的冗余了一些.
大家有没有发现其实交换是没有必要的.
我们比较的是 key 值, 第一次循环的时候不会超过i, 第一次交换把 j 的值付给 i. 实际上没有使用 a[i] = key.
第二次循环的时候不会超过j, 然后交换的时候把 i 的值 付给 j. 实际上没有使用a[j] = key.

既然 key 值的那个位置一直没有使用, 那是不是就不需要交换了, 直接赋值就行了.
最后的时候交换一下.

代码如下

int i = l, j = r;
int  key = a[i];
while(i < j) {
    // a[i] not use
    while(a[j] >= key && i < j) {
        j--;
    }

    //  a[j] < key a[i] = key
    if(i < j) {
        a[i] = a[j];
        i++;
    }
    // a[j] not use
    while(a[i] <= key && i < j) {
        i++;
    }

    //  a[i] > key a[j] = key
    if(i < j) {
        a[j] = a[i];
        j--;
    }
}
assert(i ==j);
a[i] = key;

完整实现

完整实现请参考我的 [github][github-qsort]

比较因子

前言说了, 比较因子选择不好, 会被精心构造的数据卡住, 所以我们需要一个好的方案来决定选择因子.

这里我想到几个可行的方案.

随机选择位置

这个大家都知道, 且很多人都是用这个方法选择比较因子的.
而且如果你使用这个方法的话, 可以很容易用我上面的代码改造成这种方式的代码.
简单的说就是选择一个位置, 和第一个位置交换就行了.

所有数的平均值

由于每层递归我们需要分组, 如果分组的时候我们得到左边和右边数字的和, 则可以得到分组的平均数, 然后用这个平均数当做比较因子.
不足就是只能对那些有平均数的类型排序.

最值平均值

所有数平均值的一个简化版本.

最值随机值

这个就更随机了, 根据最大值和最小值, 在这个区间内随机挑一个数字当做key值.

当然最常用的还是选择第一个位置或者随机选择一个位置当做key值.