快速排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void position(int q[], int l, int r){
if (l >= r) return ; // 边界
int x = q[l], i = l-1, j = r+1;
while(i < j) {
while (q[++i] < x); // 从左往右扫描
while (q[--j] > x); // 从右往左扫描
if(i < j) {
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
position(q, l, j); // 对左区间排序
position(q, j + 1, r); // 对右区间排序
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &q[i]);
position(q, 0, n-1);
for(int i = 0; i < n; i++)
printf("%d ", q[i]);
return 0;
}
归并排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;
int n, a[N], temp[N];
void position(int a[], int l, int r){
if(l >= r) return ;
int mid = l + r >> 1;
// 递归
position(a, l, mid), position(a, mid+1, r);
int k = 0, i = l, j = mid+1;
// 归并
while(i <= mid && j <= r)
if(a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
// 收尾
while(i <= mid) temp[k++] = a[i++];
while(j <= r) temp[k++] = a[j++];
// 整合成一个有序序列
for(i = l, j = 0; i <= r; i++, j++)
a[i] = temp[j];
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
position(a, 0, n-1);
for(int i = 0; i < n; i++) {
cout << a[i] << " ";
}
return 0;
}
解法:
- 区间[L, R] => [L, mid] 和 [mid + 1, R]
- 递归排序[L, mid] 和 [mid + 1, R]
- 归并,将左右两个有序序列合并成一个有序序列
归并排序----逆序对的数量
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, q[N], temp[N];
LL position(int l, int r){
if(l >= r) return 0;
int mid = l + r >> 1;
LL teg = position(l, mid) + position(mid+1, r);
int k = 0, i = l, j = mid+1;
while(i <= mid && j <= r){
if(q[i] <= q[j])
temp[k++] = q[i++];
else {
temp[k++] = q[j++];
teg += mid - i +1 ;
}
}
while(i <= mid)
temp[k++] = q[i++];
while(j <= r)
temp[k++] = q[j++];
for(i = l, j = 0; i <= r; i++, j++)
q[i] = temp[j];
return teg;
}
int main() {
cin >> n;
for(int i = 0; i < n; i++)
cin >> q[i];
cout << position(0, n-1) << " ";
return 0;
}
思路:
使用归并排序解题时,逆序对分为三种情况:全在左区间;全在右区间;一个在左区间一个在右区间。对于第三种情况,当左区间(已排序)的一个数i刚好大于右区间的一个数j,那么mid+1 >= i 的数都大于j,就可以得出teg = mid - i + 1.