)
排序算法
文中使用的图片来自慕课网课程算法与数据结构
本章介绍的算法都是时间复杂度为 级别的算法.
归并排序 (Merge Sort)
归并排序算法思路: 将待排序数组分成两部分, 对每一部分进行排序, 然后再将两部分合并. 其中, 对于每一部分的排序, 又可以继续利用归并排序来完成.
归并排序的分析
我们可以看出, 在有三个元素的时候, 我们分成了三个层级后, 每一个子序列中就只有一个元素了 (8 个元素, 每次二分, 次后就完成划分).
归并的过程
归并的过程需要额外开辟一个同等大小的空间, 使用三个指针来完成归并.
下方表示待归并的数组, 上方用于存储最终归并的结果. 蓝色指针指向下一个待归位的位置, 两个橙色指针分别指向两个待归并数组中下一个带归位的元素, 每一次比较两个橙色指针所指向的元素大小, 选择较小的那个元素填入蓝色指针位置, 并将蓝色指针后移一位, 同时将该橙色指针也后移一位, 知道完成归并.
这一步归并的时间复杂度为 级别, 需要完成归并的次数为
, 算法总体的时间复杂度为
.
归并排序的递归实现
// 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.
快速排序
快速排序的基本思路
快速排序的基本思路如上图所示, 选定一个元素, 使得该元素处在排序后的正确位置, 即, 在上图中, 4 左边的元素都是小于 4 的, 4 右边的元素都是大于 4 的.
要完成这个过程, 快速排序中的一个重要的步骤是 Partition 的过程.
我们选定第一个元素 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
上面的快速排序算法存在问题, 对于完全有序的数组, 其退化成为 的算法. 原因是我们每一次选定第一个元素作为参考值完成 partition 操作, 相当于是将原数组分成两部分, 对于近乎有序的数组, 这两部分是极不平衡的. 那么最终我们的算法生成的树的深度是非常大的, 当数组完全有序时, 树的深度是
, 因此会退化为
的算法.
解决这个问题也非常简单, 我们只需要随机参考值即可, 这样, 退化为 的算法的概率就非常小.
// 返回 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 的逻辑会将大量元素放在同一边中, 使得两边极度不平衡, 降低算法性能.
可以采用如下方法来解决该问题.
将两部分放在数组的两边, 分别从两边进行生长, 当左边元素大于等于 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: 三路快速排序
三路快速排序将数组分成三部分, 小于 v, 等于 v 和大于 v.
-
e == v: 只需要i++即可. -
e < v: 将arr[i]和arr[lt+1]交换, 然后lt++,i++. -
e > v: 将arr[i]和arr[gt-1]交换, 然后gt--.
停止条件是 i == gt, 结束时, 交换 arr[lt] 和 arr[l] 的元素即可.
归并排序和快速排序的衍生问题
- 归并排序和快速排序都使用了分治算法的思想.
分治算法:
将原问题分解成结构相同的子问题, 进而得到解决.
- 归并排序关键点在于合的问题. 快速排序关键点在于分的过程.
逆序对
上面的数组中, 2, 3 为顺序对, 2, 1, 为逆序对.
逆序对的数量可以衡量数组的有序程度.
可以使用归并排序的思路来完成逆序对的计算:
对于每一个左右两边有序的数组, 我们只需要比较左右两边对应的元素的大小, 因为是有序的, 如果左边元素比右边对应元素大, 那么左边该元素之后的所有元素都与右边的这个元素构成逆序对.
//
// 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 大的元素
该问题的退化问题是取出数组中的最大 (最小) 元素, 我们只需要遍历一遍数组即可, 时间复杂度为 .
对于取出数组中第 大元素的要求:
- 排序: 复杂度为
- 使用快排的思想, 每次归位一个元素, 看一下这个元素的位置, 比较我们要找的元素是在该元素右边还是左边, 进而对子数组重新进行 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;
}
