中国空间站建造历程,中卫网站设计在哪里,提升学历一般多少钱,WordPress 页码固定在此之前我们已经介绍过归并排序和快速排序#xff1a;浅谈归并排序与快速排序#xff0c;但其中的实现都是基于递归的。本文将重新温故这两种算法并给出基于迭代的实现。 目录 1. 归并排序1.1 基于递归1.2 基于迭代 2. 快速排序2.1 基于递归2.2 基于迭代 1. 归并排序
1.1 基…在此之前我们已经介绍过归并排序和快速排序浅谈归并排序与快速排序但其中的实现都是基于递归的。本文将重新温故这两种算法并给出基于迭代的实现。 目录 1. 归并排序1.1 基于递归1.2 基于迭代 2. 快速排序2.1 基于递归2.2 基于迭代 1. 归并排序
1.1 基于递归
归并排序的核心是二路归并实现二路归并需要一个额外的辅助数组因此空间复杂度是 O ( n ) O(n) O(n)。
void merge(vectorint a, int l, int mid, int r, vectorint tmp) {int i l, j mid 1, k l;while (i mid j r) {if (a[i] a[j]) tmp[k] a[i];else tmp[k] a[j];}while (i mid) tmp[k] a[i];while (j r) tmp[k] a[j];for (int i l; i r; i) a[i] tmp[i];
}该函数会对数组 a 的 [l, mid] 和 [mid 1, r] 两部分进行二路归并其中辅助数组 tmp 的大小与 a 相同。
有了 merge 函数我们就可以很方便的实现归并排序了
void merge_sort(vectorint a, int l, int r, vectorint tmp) {if (l r) return;int mid l r 1;merge_sort(a, l, mid, tmp), merge_sort(a, mid 1, r, tmp);merge(a, l, mid, r, tmp);
}1.2 基于迭代
很明显基于递归的实现是自顶向下的而基于迭代的实现是自底向上的。
我们可以先枚举区间长度再枚举区间左端点。一开始每个区间的长度是 1 1 1我们每次对相邻的两个区间进行二路归并每归并一次区间的长度就是原先的两倍所以枚举区间长度时变量 len 的更新方式为 len * 2。
对于区间左端点每合并完两个区间后左端点就要更新成下下个区间如下图所示 还需保证 mid n - 1即 l n - len。
void merge_sort(vectorint a) {int n a.size();vectorint tmp(n);for (int len 1; len n; len * 2) {for (int l 0; l n - len; l 2 * len) {int mid l len - 1;int r min(l 2 * len - 1, n - 1);merge(a, l, mid, r, tmp);}}
}归并排序的时间复杂度是 O ( n log n ) O(n\log n) O(nlogn)无论是递归还是迭代空间复杂度都是 O ( n ) O(n) O(n)。
2. 快速排序
2.1 基于递归
void quick_sort(vectorint a, int l, int r) {if (l r) return;int mid l r 1;int i l - 1, j r 1, x a[mid];while (i j) {while (a[i] x);while (a[--j] x);if (i j) swap(a[i], a[j]);}quick_sort(a, l, j), quick_sort(a, j 1, r);
}2.2 基于迭代
void quick_sort(vectorint a, int l, int r) {if (l r) return;stackpairint, int stk;stk.emplace(l, r);while (!stk.empty()) {auto [l, r] stk.top();stk.pop();if (l r) {int mid l r 1;int i l - 1, j r 1, x a[mid];while (i j) {while (a[i] x);while (a[--j] x);if (i j) swap(a[i], a[j]);}stk.emplace(l, j);stk.emplace(j 1, r);}}
}时间复杂度是 O ( n log n ) O(n\log n) O(nlogn)空间复杂度是 O ( log n ) O(\log n) O(logn)。
