快速排序
题目 Luogu P1177 将读入的 N 个数从小到大排...
Luogu P1177
将读入的N个数从小到大排序后输出
第一行为一个正整数N。
第二行包含N个空格隔开的正整数ai ,为你需要进行排序的数。
将给定的N个数从小到大输出,数之间空格隔开,行末换行且无空格。
对于20%的数据,有1≤N≤103;
对于100%的数据,有1≤N≤105 ,1≤ai≤109。
输入
5
5 2 4 5 1
输出
1 2 4 4 5
归并排序主要利用分治思想,时间复杂度为O(nlogn)。
int n, a[100010], b[100010]; /* 此处a,b为辅助数组 */
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); /* 递归拆分 */
int i = l, j = mid + 1, k = l; /* 合并 */
while(i <= mid && j <= r){
if(a[i] <= a[j]) b[k++] = a[i++];
else b[k++] = a[j++];
}
while(i <= mid) b[k++] = a[i++];
while(j <= r) b[k++] = a[j++];
for(i = l; i <= r; i++) a[i] = b[i];
}
划分
合并:
1. i,j 分别指向a的左右段起点,k指向b的起点。
2. 枚举a数组,如果左数≤右数,把左数放入b数组,否则,把右数放入b数组。
3. 把左段或右端剩余的数放入b数组。
4. 把b数组的当前段复制回a数组。
快速排序 | 归并排序 | |
---|---|---|
分治 | 先交换后拆分 | 先拆分后交换 |
稳定性 | 不稳定 | 稳定 |
#include <iostream>
using namespace std;
int n, a[100010], b[100010];
void merge_sort(int l, int r){
if(l >= r) return;
int mid = (l + r) >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = l;
while(i <= mid && j <= r)
if(a[i] <= a[j]) b[k++] = a[i++];
else b[k++] = a[j++];
while(i <= mid) b[k++] = a[i++];
while(j <= r) b[k++] = a[j++];
for(i = l; i <= r; i++) a[i] = b[i];
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
merge_sort(0, n - 1);
for(int i = 0; i < n; i++) printf("%d ", a[i]);
return 0;
}