摘自 Acwing
归并排序
- #include <iostream>
- using namespace std;
- const int N = 1e5 + 10;
- int n;
- int q[N], tmp[N];
- void merge_sort(int q[], int l, int r)
- {
- if (l>= r)
- return;
- int mid = l + r>> 1;
- merge_sort(q, l, mid), merge_sort(q, mid + 1, r); // recurse until
- int k = 0, i = l, j = mid + 1;
- while (i <= mid && j <= r) // two pointer
- {
- if (q[i] <= q[j])
- tmp[k++] = q[i++];
- else
- tmp[k++] = q[j++];
- }
- while (i <= mid) // remaining of left part
- tmp[k++] = q[i++];
- while (j <= r)
- tmp[k++] = q[j++]; // remaining of right part
- for (i = l, j = 0; i <= r; i++, j++) // place them in the correct location
- q[i] = tmp[j];
- }
- int main()
- {
- scanf("%d", &n);
- for (int i = 0; i <n; ++i)
- scanf("%d", &q[i]);
- merge_sort(q, 0, n - 1);
- for (int i = 0; i < n; ++i)
- printf("%d", q[i]);
- return 0;
- }
N: 最大数组长度 (+10 防止溢出)
n: 数组长度
q: 原未排序数组 -> 排好序数组
tmp: 当前分离的两部分通过双指针找到的排好序的数组 (类似选择排序)
每次得到 tmp 之后要把它放到正确的 q 的位置, 所以加了 26 - 27 行
快速排序
- #include <iostream>
- using namespace std;
- const int N = 1e5 + 10;
- int n;
- int q[N];
- void quick_sort(int q[], int l, int r)
- {
- if (l>= r)
- return;
- int x = q[(l + r) / 2], i = l - 1, j = r + 1;
- while (i <j)
- {
- while (q[++i] < x);
- while (q[--j]> x);
- if (i <j) swap(q[i], q[j]);
- }
- quick_sort(q, l, j);
- quick_sort(q, j + 1, r);
- }
- int main()
- {
- scanf("%d", &n);
- for (int i = 0; i < n; ++ i)
- scanf("%d", &q[i]);
- quick_sort(q, 0, n - 1);
- for (int i = 0; i < n; ++ i)
- printf("%d", q[i]);
- return 0;
- }
N: 最大数组长度 (+10 防止溢出)
n: 数组长度
q: 原未排序数组 -> 排好序数组
x:partition point
i 和 j: 最左和最右的指针 (类似 selection sort)
与 merge sort 不同的是先排序再递归, 首先使用双指针把小于 x 的和大于 x 的放在 x 的左边和右边 (一样的既在左边也可以在右边, 所以算法不稳定)
partition 的位置既可以是最左边, 右边, 中间, 也可以是随机的, 平均的是见复杂度是 O(n)
来源: http://www.bubuko.com/infodetail-3360215.html