NO IMAGE

1.快速排序

 

#include <iostream>
using namespace std;
const int MAXN = 2e5   10;
int arr[MAXN];
int len;
void qsort(int arr[], int fst, int lst)
{
int i = fst, j = lst;
int mid = arr[(i   j) / 2];
while(i <= j)
{
while(arr[i] < mid) //更改符號換遞減序
i   ;
while(arr[j] > mid) //同上
j --;
if(i <= j)
{
swap(arr[i], arr[j]);
i   ; j --;
}
}
if(i < lst)
qsort(arr,i, lst);
if(fst < j)
qsort(arr,fst, j);
}
int main()
{
ios::sync_with_stdio(false);
cin>>len;
for(int i = 0; i < len; i  )
cin>>arr[i];
qsort(arr, 0, len - 1);
for(int i = 0; i < len; i  )
cout<<arr[i]<<' ';
cout<<endl;
return 0;
}

 

2.歸併排序

求逆序數

#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 1e5   10;
ll arr[MAXN];
ll brr[MAXN];
ll ans = 0;
ll N, x, y; 
void merge_sort(ll arr[], ll x, ll y, ll brr[])
{
if(y - x > 1)
{
int m = x   (y - x) / 2;
int p = x, q= m, i = x;
merge_sort(arr, x, m, brr);
merge_sort(arr, m, y, brr);
while(p < m || q < y)
{
if(q >= y || (p < m && arr[p] <= arr[q]))
{
brr[i  ] = arr[p  ]; 
}
else
{
brr[i  ] = arr[q  ];
ans  = m - p; //求逆序數
}
}
for(i = x; i < y; i  )
arr[i] = brr[i];
}
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>N)
{
ans = 0;
for(int i = 0; i < N; i  )
cin>>arr[i];
merge_sort(arr, 0, N, brr);
cout<<ans<<endl;  
}
return 0;
}