快速排序优化

转载自：http://blog.csdn.net/wzy_1988/article/details/8043168

前言

今天要重写之前的快排算法，重新翻看自己之前的博客，总是会有稚嫩的感觉，这是好事，说明我一直在进步！

快排是分治策略很好的应用，IT面试大部分都会考察你对快排算法的掌握，博主面试阿里巴巴、创新工厂均在快排算法上有涉及，这里记录一下

算法思想

快速排序采用了一种分治策略，学术上称之为分治法（Divide-and-Conquer Method）

分治的基本思想

将原问题分解成若干个规模更小但是结构跟原问题相似的子问题。递归的解决这些子问题，然后将这些子问题的解合并为原问题的解

快排的思想

设当前需要排序的数组为int A[bt...ed]

分解：
在A[]中任选一个记录作为基准（pivot），以pivot为基准将数组A划分为两个小的数组A[bt...pivot-1]和A[pivot+1...ed],并使左边的数组元素均小于等于pivot，右边数组元素均大于等于piovt。此时，pivot处于正确的位置上，它不需要再参加后续的排序

求解：
递归的调用快速排序，对A[bt...pivot-1]和A[pivot+1...ed]进行快速排序

组合：
跟归并排序不同，因为每次调用快速排序，左右两个数组均已有序，因此对于快速排序来说，组合是一个空操作

实现代码（C语言）

快排用c实现其实可以直接调用系统的qsort函数，自己写compare比较函数即可，在php里是调用usort函数，但是面试考察大部分都是不能调用系统函数的，所以这里提供一下代码，供参考：

/**
 * 基准点排序
 *
 * T = O(n)
 *
 */
int pivotLoc(int *arr, int bt, int ed)
{
    int stand;

    stand = arr[bt];

    while (bt < ed) {
        while (bt < ed && arr[ed] >= stand)   ed --;
        if (bt < ed) arr[bt ++] = arr[ed];

        while (bt < ed && arr[bt] <= stand)   bt ++;
        if (bt < ed) arr[ed --] = arr[bt];
    }

    arr[bt] = stand;

    return bt;
}

/**
 * 快排入口代码，递归策略
 *
 * T = O(nlogn)
 *
 */
void quickSort(int *arr, int bt, int ed)
{
    int pivot;

    if (bt < ed) {
        pivot = pivotLoc(arr, bt, ed);
        quickSort(arr, bt, pivot - 1);
        quickSort(arr, pivot + 1, ed);
    }
}

优化

快排的平均时间复杂度是O(nlogn),但是考虑一下最坏的情况：

假设给定的排序序列是逆序，例如5、4、3、2、1,然后用上述快排代码进行从小到大排序，很明显，快排从O（nlogn）降到了O(n^2)，如何避免这种情况呢？

解答：基准点的随机选取，我这里每次采用mid作为基准点

/**
 * 快排优化，随机选取基准点
 *
 */
void optimizeSort(int *arr, int bt, int ed)
{
    int mid = bt + ((ed - bt) >> 1);

    // 不使用额外空间，进行两数互换
    if (arr[bt] != arr[mid]) {
        arr[bt] = arr[bt] ^ arr[mid];
        arr[mid] = arr[bt] ^ arr[mid];
        arr[bt] = arr[bt] ^ arr[mid];
    }
}

/**
 * 基准点排序
 *
 * T = O(n)
 *
 */
int pivotLoc(int *arr, int bt, int ed)
{
    int stand;

    // 快排优化
    if (bt < ed) {
        optimizeSort(arr, bt, ed);
    }

    stand = arr[bt];

    while (bt < ed) {
        while (bt < ed && arr[ed] >= stand)   ed --;
        if (bt < ed) arr[bt ++] = arr[ed];

        while (bt < ed && arr[bt] <= stand)   bt ++;
        if (bt < ed) arr[ed --] = arr[bt];
    }

    arr[bt] = stand;

    return bt;
}

/**
 * 快排入口代码，递归策略
 *
 * T = O(nlogn)
 *
 */
void quickSort(int *arr, int bt, int ed)
{
    int pivot;

    if (bt < ed) {
        pivot = pivotLoc(arr, bt, ed);
        quickSort(arr, bt, pivot - 1);
        quickSort(arr, pivot + 1, ed);
    }
}