高级排序算法（二）

快速排序（Quick Sort）

算法思想：在待排序表L[1...n]中任取一个元素pivot作为基准，通过一趟排序将带排序表划分为独立的两部分L[1...k-1]和L[k+1...n]，使得L[1...k-1]中所有元素小于pivot，L[k+1...n]中所有元素大于或等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一趟快速排序。而后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了最终的位置上。

算法演示：

快速排序

基本代码如下：

// 对arr[l...r]部分进行partition操作
// 返回p，使得arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
template<typename T>
int __partition(T arr[], int l, int r) {

    T v = arr[l];

    // arr[l+1...j] < v; arr[j+1...i) > v
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < v) {
            swap(arr[j + 1], arr[i]);
            j++;
        }
    }
    swap(arr[l], arr[j]);
    return j;
}

// 对arr[l...r]部分进行快速排序
template<typename T>
void __quickSort(T arr[], int l, int r) {

    if (l >= r)
        return;

    int p = __partition(arr, l, r);
    __quickSort(arr, l, p - 1);
    __quickSort(arr, p + 1, r);
}

template<typename T>
void quickSort(T arr[], int n) {

    __quickSort(arr, 0, n - 1);
}

好了，按照惯例我们将同时调用快速排序和归并排序进行测试，看看哪种算法的运行效率更高，其结果如下（随机数据）：

Quick Sort : 0.029 s
Merge Sort : 0.03 s

我们从结果中发现快速排序算法的运行效率与优化后的归并排序算法的效率不相上下。不知大家有没有发现归并排序算法前“优化后”这三个字加粗显示，这么做其实是为了想告诉大家，我们的快速排序算法还有优化的空间，而归并排序算法已是目前最优的结果。

那么，我们将怎么样优化快速排序呢？我们先回想一下对归并排序的优化操作，在归并排序算法中，我们针对数据较少时采用插入排序，类似的，我们也可以进行这样的操作。

有一个重要的问题，我们始终忽略了。这就是我们没有测试在近乎有序的随机数据情况下，两种排序算法的运行效率。大家若学习过数据结构这门课程就会知道，快速排序有个致命的缺陷——在处理近乎有序的随机数据时，其时间复杂度会变为O(n²)。

为什么会成这种结果呢？这是因为我们在对待排序表进行划分时，不像归并排序算法一样一分为二，而是先找到一个元素pivot作为基准，使得待排序列表在基准之前的元素均小于它，在基准后面的元素均大于它。当快速排序算法处理近乎有序的随机数据时，这种划分操作就会类似于冒泡排序算法的处理操作，所以在这种情况下时间复杂度就变为O(n²)。

为了解决这种问题，我们就不再采用选用待排序表第一个元素作为基准（请大家不要被严奶奶版的数据结构中快速排序算法的讲解所束缚，推荐在学习数据结构时翻阅“黑皮书”对数据结构做进一步了解），而选用待排序列表中尽可能中间的元素作为基准，即随机选择一个数。（注：这里不过多叙述其原因，具体请参考算法导论或“黑皮”版数据结构与算法分析。）

改进后的快速排序算法基本代码如下：

// 对arr[l...r]部分进行partition操作
// 返回p，使得arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
template<typename T>
int __partition(T arr[], int l, int r) {

    swap(arr[l], arr[rand() % (r - l + 1) + l]);

    T v = arr[l];

    // arr[l+1...j] < v; arr[j+1...i) > v
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < v) {
            swap(arr[j + 1], arr[i]);
            j++;
        }
    }
    swap(arr[l], arr[j]);
    return j;
}

// 对arr[l...r]部分进行快速排序
template<typename T>
void __quickSort(T arr[], int l, int r) {

    if (l >= r)
        return;

    int p = __partition(arr, l, r);
    __quickSort(arr, l, p - 1);
    __quickSort(arr, p + 1, r);
}

template<typename T>
void quickSort(T arr[], int n) {

    srand(time(NULL));
    __quickSort(arr, 0, n - 1);
}

让我们看看运行的结果吧（近乎有序的随机数据）。

Quick Sort : 0.035 s
Merge Sort : 0.005 s

我们发现快速排序算法的运行效率虽比上归并排序，但其性能已经远远好于优化前的性能。

除此之外，我们的快速排序还可进行优化。例如在含有大量重复数据的情况下，我们的快速排序算法的运行效率依旧不高。这里我们向大家展示一下快速排序算法的龟速！

首先，我们按如下代码修改main()中的代码：

int main() {

    int n = 100000;
    int *arr_1 = SortTestHelper::generateRandomArray(n, 0, 10);
    int *arr_2 = SortTestHelper::copyIntArray(arr_1, n);

    SortTestHelper::testSort("Quick Sort", quickSort, arr_1, n);
    SortTestHelper::testSort("Merge Sort", mergeSort, arr_2, n);

    delete[] arr_1;
    delete[] arr_2;
    return 0;
}

然后我们运行程序，看看其运行结果：

Quick Sort : 1.459 s
Merge Sort : 0.017 s

在处理含有大量重复数据时，快速排序算法的运行效率可称为龟速啊！这是因为我们在对待排序表进行划分操作时，由于数据中含有大量的重复数据，会有很大概率上将待排序表划分得极度不平衡，从而导致快速排序算法退化为时间复杂度为O(n²)。

那么对于这种情况，我们优化思路的算法演示为：

实际上，图中两侧的数据应该是如下图所示：

二路快速排序

优化的基本代码如下：

// 对arr[l...r]部分进行partition操作
// 返回p，使得arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
template<typename T>
int __partition2(T arr[], int l, int r) {

    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];

    // arr[l+1...i) <= v; arr(j...r] >= v
    int i = l + 1, j = r;
    while (true) {
        while (i <= r && arr[i] < v) i++;
        while (j >= l + 1 && arr[j] > v) j--;
        if (i > j) break;
        swap(arr[i], arr[j]);
        i++;
        j--;
    }
    swap(arr[l], arr[j]);
    return j;
}

// 对arr[l...r]部分进行快速排序
template<typename T>
void __quickSort2(T arr[], int l, int r) {

    if (l >= r)
        return;

    int p = __partition2(arr, l, r);
    __quickSort2(arr, l, p - 1);
    __quickSort2(arr, p + 1, r);
}

template<typename T>
void quickSort2(T arr[], int n) {

    // 设置当前的时间值为种子,那么种子总是变化的，所以以该种子产生的随机数总是变化的
    srand(time(NULL));
    __quickSort2(arr, 0, n - 1);
}

那我们来看看这次优化后的结果吧。

Quick Sort : 1.487 s
Merge Sort : 0.018 s
Quick Sort 2 : 0.016 s

通过这次优化，我们的快速排序算法的运行效率有了显著地提升。实际上，我们将这种方式的快速排序算法称之为双路快速排序算法。除此之外，在处理含有大量重复数据的数据时，我们还有一个更为经典的快速排序算法，通常我们将其称为三路快速排序算法。

其实这个排序算法的思路很简单，其算法演示如下图所示：

三路快速排序

三路快速排序算法的基本代码如下：

// 三路快速排序
// 将arr[l...r]分为 < v; == v; > v 三部分
// 之后递归对 < v; > v 两部分进行三路快速排序
template<typename T>
void __quickSort3(T arr[], int l, int r) {

    if (l >= r)
        return;

    // partition操作
    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];

    // arr[l+1...lt] < v
    int lt = l;
    // arr[gt...r] > v
    int gt = r + 1;
    // arr[lt+1...i) == v
    int i = l + 1;

    while (i < gt) {
        if (arr[i] < v) {
            swap(arr[i], arr[lt + 1]);
            lt++;
            i++;
        } else if (arr[i] > v) {
            swap(arr[i], arr[gt - 1]);
            gt--;
        } else {
            // arr[i] == v
            i++;
        }
    }
    swap(arr[l], arr[lt]);

    __quickSort3(arr, l, lt - 1);
    __quickSort3(arr, gt, r);
}

template<typename T>
void quickSort3(T arr[], int n) {

    // 设置当前的时间值为种子,那么种子总是变化的，所以以该种子产生的随机数总是变化的
    srand(time(NULL));
    __quickSort3(arr, 0, n - 1);
}

好了，我们调用一些三路快速排序算法并运行程序，其结果如下：

Quick Sort : 1.393 s
Merge Sort : 0.018 s
Quick Sort 2 : 0.015 s
Quick Sort 3 : 0.006 s