【经典算法】快速排序

与归并排序一样，快速排序使用也使用了分治的思想。下面是对一个典型的子数组A[p,...,r]进行快速排序的三步分治过程：

分解：数组A[p,...,r]被划分成两个（可能为空）子数组A[P,...,q-1]和A[q+1,...,r]，使得A[p,...,q-1]中每个元素都小于等于A[q]，而A[q]也小于等于A[q+1,...,r]中的每个元素。其中，计算下标q也是划分过程的一部分。

解决：通过递归调用快速排序，对子数组啊A[P,...,q-1]和A[q+1,...,r]进行排序。

合并：因为子数组都是原址排序的，所以不需要合并操作：数组A[P,...r]已经有序。

下面是程序实现快速排序：

void QuickSort(int a[], int p, int r) {
    if (p < r) {
        int q = Partition(a, p, r);
        QuickSort(A, p, q - 1);
        QuickSort(A, q + 1, r);
    }
}

数组的划分：

算法的关键部分是Partition过程，它实现了对子数组A[p,...r]的原址重排。快速排序的分治partition过程有两种方法。

1） 两个下标分别从首、尾向中间扫描的方法。

假设每次总是以当前表中第一个元素作为枢纽值（基准）对表进行划分，则必须将表中比枢纽值大的元素向右移动，比枢纽值小的元素向左移动，使得一趟Partition()操作之后，表中的元素被枢纽值一分为二。

int Partition(int a[], int low, int high) {
    int pivot = a[low];
    while (low < high) {
        while (low < high && a[high] >= pivot) --high;
        a[low] = a[high];
        while (low < high && a[low] <= pivot) ++low;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}

2）两个指针索引一前一后逐步向后扫描的方法（算法导论）。

int Partition(int a[], int low, int high) {
    int pivot = a[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (a[low] <= pivot) {
            ++i;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[high]);
    return i+1；
}

注意：上述算法有一个特点，即一次划分后，枢纽左边的相对位置不变。比如，原始序列：[3,8,7,1,2,5,6,4]->[3,1,2,4,7,5,6,8]。枢纽4左边的相对顺序不变，元素3,1,2保持在初始序列中的相对顺序（原序列中为3,...,1,2,...)，某些应用要求序列的一部分保持相对顺序，这时可以考虑此种划分。

快速排序算法的性能分析如下：

空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为⌈log₂(n+1)⌉;最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n)；平均情况下栈的深度为O（log₂n)。因而空间复杂度在最坏情况下为O(n),平均情况下为O(log₂n)。

时间效率：快速排序的运行时间与划分是否对称有关，而后者又与具体使用的划分算法有关。快速排序最坏的情况发生在两个区域分别包含n-1个元素和0个元素时，这种程度的不对称性若发生在每一层递归上，即对应于初始排序表基本有序货基本逆序时，就得到最坏情况下的时间复杂度为O(n²)。

有很多方法可以提高算法的效率。一种方法是当递归过程中划分得到的子序列的规模较小时不要再继续调用快速排序，可以直接采用直接插入排序算法进行后续的排序工作。另一种方法就是尽量选取一个可以将数据中分的枢轴元素。如从序列的头尾以及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素（数据结构与算法分析）；或者随机从当前列表中选取枢轴元素（算法导论），这样做使得最坏情况在实际安排中几乎不会发生。

在最理想状态下，也即Partition()可能做到最平衡的划分中，得到的两个子问题的大小都不可能大于n/2，这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为O(nlog₂n)。好在快速排序平均情况下运行时间与其最佳情况下的运行时间很接近，而不是接近最坏情况下的运行时间。

快速排序是所有内部排序算法中平均性能最优的排序算法。

稳定性：快速排序不是稳定的排序算法。

一、快速排序一次排序的应用

1.一个数组中存储有且仅有大写和小写字母，编写一个函数对数组内的字母重新排列，让小写字母在所有大写字母之前。

void Partition(char a[], int length) {
    if (a == NULL || length <= 0)
        return;
    
    int i = 0;
    for (int j = 0; j <= length - 1; ++j) {
        if (a[j] >= 'a' && a[j] <= 'z') {
            i++;
            char temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
}

2. 给定含有n个元素的整形数组a, 其中包括0元素和非0元素，对数组进行排序，要求：

1）排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相对位置不变。

2）不能使用额外存储空间。、

例如：

输入 0、3、0、2、1、0、0

输出 0、0、0、0、3、2、1

解答：此处要求非零元素排序前后相对位置不变，可以利用快排一次排序的第二种情况。

void Partition(int A[], int p, int r) {int i = r + 1;for (int j = r; j >= p; --j) {if (A[j] != 0) {--i;int temp = A[i];A[i] = A[j];A[j] = temp;}}
}

3. 荷兰国旗问题

将乱序的红白蓝三色小球排列成同颜色在一起的小球组（按照红白蓝排序），这个问题称为荷兰国旗问题。这是因为我们可以将红白蓝小球想象成为条状物，有序排列后正好组成荷兰国旗，用0表示红球，2为篮球，1为白球。

解答：这个问题，类似于快排中partition过程。不过，要用三个指针，一个begin，一中current，一后end，begin与current都初始化指向数组首部，end初始化指向数组尾部。

1. current遍历整个数组序列，current指1时，不交换，current++；

2. current指0时，与begin交换，而后current++，begin++；

3. current指2时，与end交换，而后，current不动，end--。

while (current <= end) {
    if (array[current] == 0) {
        swap(array[current], array[begin]);
        current++;
        begin++;
    } else if (array[current] == 1) {
        current++;
    } else {
        swap(array[current], array[end]);
        end--;
    }
}

二、最小的k个数

输入n个整数，输出其中最小的k个。

例如输入1,2,3,4,5,6,7,8这8个数字，则最小的4个数字为1,2,3,4

解答：分析：这到底最简单的思路莫过于把输入的n个整数排序，这样排在最前面的k个数就是最小的k个数。只是这种思路的时间复杂度为O(nlgn)。我们试着寻找更快的解题思路。

我们设最小的k个数中最大的数为A。在快速排序算法中，我们现在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小的数字都排在他的左边，比选中的数字大的数字都排在它的右边（即快排一次排序）。如果这个选中的数字的下标刚好是k-1（下标从0）开始，那么这个数字（就是A）加上左侧的k-1个数字就是最小的k个数。

如果它的下标大于k-1，那么A应该位于它的左边，我们可以接着在它的右边部分的数组中寻找。可见这是一个递归问题，但是注意我们找到的k个数不一定是有序的。

int Partition(int a[], int p, int r) {
    int pivot = a[r];
    int i = p - 1;
    for (int j = p; j <= r - 1; ++j) {
        if (a[j] <= pivot) {
            ++i;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[r]);
    return i + 1;
}
void GetLeastKNum(int *input, int n, int k) {
    if (input == NULL || n <= 0 || k > n || k <= 0)
        return;

    int start = 0;
    int end = n - 1;
    int index = Partition(input, start, end);
    while (index != k - 1) {
        if (index < k - 1) {
        start = index + 1;
        index = Partition(input, start, end);
        } else {
            end = index - 1;
            index = Partition(input, start, end);
        }
    }

    for (int i = 0; i <= k - 1; ++i) {
        cout << input[i];
    }
    cout << endl;
}

上述方法的时间复杂度是O(n)。