【每日算法】快速排序及其应用

快速排序

快排的最坏运行时间为O（n^2），平均运行时间为O(n logn)，且隐含的常数因子很小，能够进行就地排序。

快排基于分治模式，其基本思想：

分解：从序列中取出一个数作为基准数，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边，从而得到两个子序列。

解决：递归调用快速排序，对两个子序列进行排序。

合并：因为子序列是就地排序的，所以合并不需要任何操作。

伪代码：

quickSort(arr, l, r)
    if l < r
        then 
            p = partition(arr, l, r)
            quickSort(arr, l, p-1)
            quickSort(arr, p+1, r)

我们只需调用：

quickSort(arr, 0, length(arr)-1)

上面代码中，关键是partition的过程：

1. 选择基准元素（有多种版本：选择首尾元素or选择中间元素or随机选择等等）；
2. 顺序扫描一遍数组，将比基准元素小的就地交换到前面；
3. 将基准元素放到中间；
4. 返回分界点下标。

举个例子arr[0…8]：

3 4 2 7 9 6 5 1 8

我们选取最后一个元素为基准元素：

x = arr[r] = arr[8] = 8;

设置一个下标，表示有序数组最右端的下标：

i = l-1 = 0-1 = -1;   //此时有序数组为空

接下来从左往右扫描一遍，将小于等于x的元素交换到有序数组的末尾：

for j = l to r-1
    if arr[j] <= x
        i = i+1;
        exchange(arr[i], arr[j]);

数组arr的变化如下：

j = 0, i = 0：
3 4 2 7 9 6 5 1 8

j = 1, i = 1：
3 4 2 7 9 6 5 1 8

j = 2, i = 2：
3 4 2 7 9 6 5 1 8

j = 3, i = 3：
3 4 2 7 9 6 5 1 8

j = 4, i = 3：
3 4 2 7 9 6 5 1 8

j = 5, i = 4：
3 4 2 7 6 9 5 1 8

j = 6, i = 5：
3 4 2 7 6 5 9 1 8

j = 7, i = 6：
3 4 2 7 6 5 1 9 8

一遍扫描完毕，需要将基准元素放置到交界处，只需要将基准元素与有序数组最后一个元素的下一个元素交换即可（该元素大于基准元素，所以可以交换）：

exchange(arr[i+1], arr[r]);

最后，返回分界点的下标：

return i+1;

下面我们整合上面的伪代码，用c++实现：

void quickSort(int arr[], int l, int r)
{
    if (l < r)
    {
        int p = partition(arr, l, r);
        quickSort(arr, l, p-1);
        quickSort(arr, p+1, r);
    }
}

int partition(int arr[], int l, int r)
{
    int x = arr[r];
    int i = l-1;
    for (int j = l; j < r; ++j)
    {
        if (arr[j] <= x)
        {
            ++i;
            exchange(arr[i], arr[j]);
        }
    }
    exchange(arr[i+1], arr[r]);
    return i+1;
}

void exchange(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

之后对于长度为length的数组arr，只需调用：

if (NULL != arr && 0 != length)
{
    quickSort(arr, 0, length-1);
}

如果想用随机的基准元素，则在划分时调用以下函数：

int rand_partition(int arr[], int l, int r)
{
    int i = random(l, r);
    exchange(arr[i], arr[r]);
    return partition(arr, l, r);
}

参考资料： 《算法导论》

实际上，快排有很多实现版本，这里推荐一篇我之前看过的比较不错的文章：

http://blog.csdn.net/morewindows/article/details/6684558

快排的变形

快排除了排序之外，还有一些变形的应用，这里我将举一两例来说明。

寻找第k大的数字

给定一个数组arr和一个数字k，求数组中第k大的数字。

分析：

寻找第k大的数字，首先我们想到，如果数组是有序的就好办多了。

所以最直接的做法是：先排序，之后返回第k位的数字，时间复杂度为O(n log n)。

在面试中，最直观的算法通常并不能让人满意。

我们排序的目的是为找第k大的数，其中有一些排序实际上是不必要的。回想我们的快速排序，选出一个基准元素x，小于等于x的放左边，大于x的放右边。因此，如果左边的数的个数大于k，那么要找的数必然在左边，则右边的排序是不必要的；否则，要找的数必然在右边，则左边的排序是不必要的。

利用快速排序这个特性，我们可以有以下O(n)的算法：

bool error = false;
int findTheKthNum(int num[], int length, int k)
{
    error = false;
    if (NULL == num || length <= 0 || k <= 0 || k > length)
    {
        error = true;
        return 0;
    }
    int l = 0, r = length-1;
    int index = partition(num, l, r);
    while (k-1 != index)
    {
        if (k-1 < index)
        {
            r = index-1;
            index = partition(num, l, r);
        }
        else
        {
            l = index+1;
            index = partition(num, l, r);
        }
    }
    return num[k-1];
}

此题还有其他变形：

求数组中出现次数超过一半的数字。

如果所求的数字存在，那么该数字必然是数组中的第length/2大的数，可用上面算法来求解。

需要注意的是，本算法会改变数组中元素的顺序，如果题目要求不能改变数组，那么需要用其他方法。

对于”求数组中出现次数超过一半的数字“，可使用多数投票算法，该算法的思想是：所求数字出现的次数比其他所有数字出现次数之和还要多。基于该思想可实现O(n)的算法，具体请参见另一篇博文：

http://blog.csdn.net/jiange_zh/article/details/50487119

寻找最小的k个数

最朴素的想法仍是排序后输出前面的k个数，但是我们仍然可以用快排的思想来优化。

代码基本跟上面一样，我们用上述代码找出第k大的数之后，数组左边的数（包括第k个数）就是最小的k个数了（需要注意的是，这k个数不一定是排序的）！

参考资料：《剑指offer》

The End。

每天进步一点点，Come on！
(●’?’●)

本人水平有限，如文章内容有错漏之处，敬请各位读者指出，谢谢！