一步一步学习数据结构和算法(二) O(nlogn) 的排序算法

作者: mlya | 来源:发表于2019-06-13 18:22 被阅读12次

$O(nlogn)$ 排序算法

文中使用的图片来自慕课网课程算法与数据结构

本章介绍的算法都是时间复杂度为 $O(nlogn)$ 级别的算法.

归并排序 (Merge Sort)

归并排序算法思路: 将待排序数组分成两部分, 对每一部分进行排序, 然后再将两部分合并. 其中, 对于每一部分的排序, 又可以继续利用归并排序来完成.

image-20190527170913971

归并排序的分析

我们可以看出, 在有三个元素的时候, 我们分成了三个层级后, 每一个子序列中就只有一个元素了 (8 个元素, 每次二分, $log_2(8) = 3$ 次后就完成划分).

归并的过程

image-20190527171729722

归并的过程需要额外开辟一个同等大小的空间, 使用三个指针来完成归并.

下方表示待归并的数组, 上方用于存储最终归并的结果. 蓝色指针指向下一个待归位的位置, 两个橙色指针分别指向两个待归并数组中下一个带归位的元素, 每一次比较两个橙色指针所指向的元素大小, 选择较小的那个元素填入蓝色指针位置, 并将蓝色指针后移一位, 同时将该橙色指针也后移一位, 知道完成归并.

这一步归并的时间复杂度为 $O(n)$ 级别, 需要完成归并的次数为 $O(logn)$ , 算法总体的时间复杂度为 $O(nlogn)$ .

归并排序的递归实现

// arr 的 [l, mid] 和 [mid + 1, r] 合并
template<typename T>
void __merge(T arr[], int l, int mid, int r) {
    T aux[r - l + 1];
    for (int i = l; i <= r; ++i) {
        aux[i - l] = arr[i];
    }
    int i = l;
    int j = mid + 1;
    for (int k = l; k <= r; k++) {
        if (i > mid) {
            arr[k] = aux[j - l];
            j++;
        } else if (j > r) {
            arr[k] = aux[i - l];
            i++;
        } else if (aux[i - l] < aux[j - l]) {
            arr[k] = aux[i - l];
            i++;
        } else {
            arr[k] = aux[j - l];
            j++;
        }
    }
}

// 递归使用归并排序, 对 arr[l, ..., r] 的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r) {
    if (l >= r) {
        return;
    } else {
        int mid = (l + r) / 2;
        __mergeSort(arr, l, mid);
        __mergeSort(arr, mid + 1, r);
        __merge(arr, l, mid, r);
    }
}

template<typename T>
void mergeSort(T arr[], int n) {
    __mergeSort(arr, 0, n - 1);
}

改进1

增加了判断, 只在 arr[mid] > arr[mid + 1] 的情况下才进行 merge.

// 递归使用归并排序, 对 arr[l, ..., r] 的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r) {
    if (l >= r) {
        return;
    } else {
        int mid = (l + r) / 2;
        __mergeSort(arr, l, mid);
        __mergeSort(arr, mid + 1, r);
        if (arr[mid] > arr[mid + 1]) {
            __merge(arr, l, mid, r);
        }
    }
}

改进2

并不需要递归到底, 在只有 16 个元素的时候, 使用插入排序进行排序.

// 递归使用归并排序, 对 arr[l, ..., r] 的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r) {
//    if (l >= r) {
//        return;
//    }
    if (r - l <= 15) {
        insertionSort(arr, l, r);
        return;
    } else {
        int mid = (l + r) / 2;
        __mergeSort(arr, l, mid);
        __mergeSort(arr, mid + 1, r);
        if (arr[mid] > arr[mid + 1]) {
            __merge(arr, l, mid, r);
        }
    }
}

归并排序的自底向上实现

template<typename T>
void mergeSortBU(T arr[], int n) {
    // size = 1, 2, 4, 8, .... n
    for (int size = 1; size <= n; size += size) {

        for (int i = 0; i < n - size; i += size + size) {
            // merge [i, i + size]
            __merge(arr, i, i + size - 1, min(i + size + size - 1, n - 1));
        }
    }
}

自底向上的归并实现也非常简单, 设定 size 不断增大, 每一次迭代, 将两个 size 大小的元素进行归并, 直到 size 大于等于 n/2 小于等于 n.

快速排序

快速排序的基本思路

image-20190604191540979

快速排序的基本思路如上图所示, 选定一个元素, 使得该元素处在排序后的正确位置, 即, 在上图中, 4 左边的元素都是小于 4 的, 4 右边的元素都是大于 4 的.

要完成这个过程, 快速排序中的一个重要的步骤是 Partition 的过程.

image-20190604191846878

我们选定第一个元素 v, 在当前考察过程中, 有三个下标点需要注意, l 表示我们所选定元素位置, j 左边的元素小于 v, j 右边的元素大于 v, i 表示我们要考察的下一个元素. 即, arr[l+1, j] < v, arr[j+1, i-1] > v.

当我们考察下一个元素 e 时, 比较 e 和 v 的大小, 我们需要考虑两种情况, 当 e 大于 v 时, 直接将 i++ 即可; 当 e 小于 v 时, 交换 arr[i] 和 arr[j], 然后 i++; j++.

当遍历完成后, 交换 arr[l] 和 arr[j], 即完成了 partition 的过程.

快速排序的递归实现

可以使用递归操作完成快速排序.

递归的终止条件为 l >= r, 即排序的子集中只有一个元素.

每一次递归, 完成 partition 操作, 并以 partition 完成后的中间值点作为分界点, 对左半边和右半边分别进行快速排序, 直到排序完成.

// 返回 p, 为完成快速排序 partition 操作后, 中间元素的位置.
template<typename T>
int __partition(T arr[], int l, int r) {
    T v = arr[l];
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < v) {
            swap(arr[++j], arr[i]);
        }
    }
    swap(arr[l], arr[j]);
    return j;
}

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);
}

优化1

我们不需要递归到底, 在子序列较小时, 可以使用插入排序来进行优化.

template<typename T>
void __quickSort(T arr[], int l, int r) {
//    if (l >= r) {
//        return;
//    }
    if (r - l <= 15) {
        insertionSort(arr, l, r);
        return;
    }

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

优化2

上面的快速排序算法存在问题, 对于完全有序的数组, 其退化成为 $O(n^2)$ 的算法. 原因是我们每一次选定第一个元素作为参考值完成 partition 操作, 相当于是将原数组分成两部分, 对于近乎有序的数组, 这两部分是极不平衡的. 那么最终我们的算法生成的树的深度是非常大的, 当数组完全有序时, 树的深度是 $n$ , 因此会退化为 $O(n^2)$ 的算法.

解决这个问题也非常简单, 我们只需要随机参考值即可, 这样, 退化为 $O(n^2)$ 的算法的概率就非常小.

// 返回 p, 为完成快速排序 partition 操作后, 中间元素的位置.
template<typename T>
int __partition(T arr[], int l, int r) {
    // 随机选择元素
    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < v) {
            swap(arr[++j], arr[i]);
        }
    }
    swap(arr[l], arr[j]);
    return j;
}

优化3: 双路快速排序

当数组中存在大量相同元素时, 我们上面 partition 的逻辑会将大量元素放在同一边中, 使得两边极度不平衡, 降低算法性能.

可以采用如下方法来解决该问题.

image-20190604204852345

将两部分放在数组的两边, 分别从两边进行生长, 当左边元素大于等于 v 时, 右边元素小于等于 v 时, 交换 arr[i] 和 arr[j]. 然后继续增长.

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--]);
    }

    swap(arr[l], arr[j]);
    return j;
}

优化4: 三路快速排序

image-20190605110914806

三路快速排序将数组分成三部分, 小于 v, 等于 v 和大于 v.

e == v: 只需要 i++ 即可.
e < v: 将 arr[i] 和 arr[lt+1] 交换, 然后 lt++, i++.
e > v: 将 arr[i] 和 arr[gt-1] 交换, 然后 gt--.

image-20190605112121939

停止条件是 i == gt, 结束时, 交换 arr[lt] 和 arr[l] 的元素即可.

image-20190605112407313

归并排序和快速排序的衍生问题

归并排序和快速排序都使用了分治算法的思想.

分治算法:

将原问题分解成结构相同的子问题, 进而得到解决.

归并排序关键点在于合的问题. 快速排序关键点在于分的过程.

逆序对

image-20190606093434464

上面的数组中, 2, 3 为顺序对, 2, 1, 为逆序对.

逆序对的数量可以衡量数组的有序程度.

可以使用归并排序的思路来完成逆序对的计算:

image-20190606105050984

对于每一个左右两边有序的数组, 我们只需要比较左右两边对应的元素的大小, 因为是有序的, 如果左边元素比右边对应元素大, 那么左边该元素之后的所有元素都与右边的这个元素构成逆序对.

//
// Created by dcr on 2019-06-06.
//
#include <algorithm>
#include "TestHelper.h"

// arr[l, mid], arr[mid + 1, r]
template<typename T>
long long __count(T arr[], int l, int mid, int r) {

    T aux[r - l + 1];

    for (int i = l; i <= r; i++) {
        aux[i - l] = arr[i];
    }

    int i = l;
    int j = mid + 1;
    long count = 0;
    for (int k = l; k < r; k++) {
        if (i > mid) {
            arr[k] = aux[j++ - l];
            continue;
        } else if (j > r) {
            arr[k] = aux[i++ - l];
        } else if (aux[i - l] > aux[j - l]) {
            arr[k] = aux[j++ - l];
            count += (long long) (mid - i + 1);
        } else {
            arr[k] = aux[i++ - l];
        }
    }
    return count;
}

template<typename T>
int inversionCount(T *arr, int n) {
    int count = 0;
    // size = 1, 2, 4, 8, ...
    for (int size = 1; size <= n; size += size) {
        for (int i = 0; i < n - size; i += size + size) {
            count += __count(arr, i, i + size - 1, std::min(i + size + size - 1, n - 1));
        }
    }
    return count;
}

int main() {
    int n = 100;

    // 测试1: 测试随机数组
    cout << "Test Inversion Count for Random Array, n = " << n << " :" << endl;
    int *arr = TestHelper::generateRandomArray(n, 0, n);
    cout << inversionCount(arr, n) << endl << endl;

    delete[] arr;
    arr = nullptr;

    // 测试2: 测试完全有序的数组
    // 结果应该为0
    cout << "Test Inversion Count for Ordered Array, n = " << n << " :" << endl;
    arr = TestHelper::generateOrderedArray(n);
    cout << inversionCount(arr, n) << endl << endl;
    delete[] arr;

    // 测试3: 测试完全逆序的数组
    // 结果应改为 N*(N-1)/2
    cout << "Test Inversion Count for Inversed Array, n = " << n << " :" << endl;
    arr = TestHelper::generateInversedArray(n);
    cout << inversionCount(arr, n) << endl;
    delete[] arr;
}

取出数组中第 i 大的元素

该问题的退化问题是取出数组中的最大 (最小) 元素, 我们只需要遍历一遍数组即可, 时间复杂度为 $O(n)$ .

对于取出数组中第 $n$ 大元素的要求:

排序: 复杂度为 $O(nlogn)$
使用快排的思想, 每次归位一个元素, 看一下这个元素的位置, 比较我们要找的元素是在该元素右边还是左边, 进而对子数组重新进行 partition 操作, 直到找到我们所需的元素.

//
// Created by dcr on 2019-06-06.
//


#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iostream>
#include "TestHelper.h"
#include "SortTestHelper.h"
#include "Sort.h"

using namespace std;

int __topK(int arr[], int l, int r, int k_pos) {


    // partition
    std::swap(arr[l], arr[rand() % (r - l + 1) + l]);
    int v = arr[l];

    int lt = l;
    int gt = r + 1;
    int i = l + 1;

    while (i < gt) {

        if (arr[i] == v) {
            i++;
        } else if (arr[i] < v) {
            std::swap(arr[i++], arr[++lt]);
        } else if (arr[i] > v) {
            std::swap(arr[i], arr[--gt]);
        }
    }
    std::swap(arr[l], arr[lt]);
    if (k_pos >= lt && k_pos <= i - 1) {
        return arr[i - 1];
    } else if (i <= k_pos) {
        return __topK(arr, gt, r, k_pos);
    } else {
        return __topK(arr, l, lt - 1, k_pos);
    }
}

int topK(int arr[], int n, int k) {
    srand(time(nullptr));
    int k_pos = n - k;
    int m = __topK(arr, 0, n - 1, k_pos);
    return m;
}

int main() {
    int n = 100;
    int k = 3;

    // 测试1: 测试随机数组
    cout << "Top " << k << " for Random Array, n = " << n << " :" << endl;
    int *arr = TestHelper::generateRandomArray(n, 0, n);
    cout << topK(arr, n, 3) << endl << endl;

    quickSort3Ways(arr, n);

    cout << "True value is: " << arr[n - k] << endl;
    SortTestHelper::printArray(arr, n);


    delete[] arr;
}

一步一步学习数据结构和算法(二) O(nlogn) 的排序算法

$O(nlogn)$ 排序算法

归并排序 (Merge Sort)

归并排序的分析

归并的过程

归并排序的递归实现

改进1

改进2

归并排序的自底向上实现

快速排序

快速排序的基本思路

快速排序的递归实现

优化1

优化2

优化3: 双路快速排序

优化4: 三路快速排序

归并排序和快速排序的衍生问题

逆序对

取出数组中第 i 大的元素

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构和算法

一步一步学习数据结构和算法