快速排序求k小归并排序逆序数

本文主要是介绍快速排序求k小归并排序逆序数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

快速排序

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 100005;
int n,k,a[maxn],b[maxn],vis[maxn];void qsort(int l,int r)
{int i = l,j = r;int mid = a[(l + r) >> 1];int m = (l + r) >> 1;while(i <= j){while(a[i] < mid)i++;while(a[j] > mid)j--;if(i <= j){swap(a[i],a[j]);i++;j--;}}if(j > l)qsort(l,j);if(i < r)qsort(i,r);
}int main()
{scanf("%d%d",&n,&k);for(int i = 1;i <= n;i++)scanf("%d",&a[i]);qsort(1,n);printf("%d\n",a[k]);return 0;
}

快速排序求第 $k$ 小

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 1e5 + 7;
int a[maxn];
int vis[maxn];
int n,k;
int qsort(int l,int r) {if(l == r && l == k) return a[l];if(l < r) {int i = l,j = r,p = a[l];while(i < j) {while(i < j && a[j] > p) j--; //从右向左找到一个小于等于基准书的数if(i < j) swap(a[i],a[j]);while(i < j && a[i] <= p) i++;if(i < j) swap(a[i],a[j]);}if(i == k) return a[k];else if(i > k) return qsort(l,i - 1);else return qsort(i + 1,r);}return -1;
}
int main() {scanf("%d%d",&n,&k);int cnt = 0;for(int i = 1;i <= n;i++) {int x;scanf("%d",&x);a[++cnt] = x;}if(cnt < k) printf("NO RESULT\n");else printf("%d\n",qsort(1,cnt));return 0;
}

快速排序求前k小的另一种写法

class Solution {
public:void Qsort(vector<int>&a,int l,int r,int k) {if(l > r) return;int val = a[(l + r) >> 1];int i = l,j = r;while(i <= j) {while(i <= r && a[i] < val) {i++;}while(j >= l && a[j] > val) {j--;}if(i <= j) {swap(a[i],a[j]);i++;j--;}}if(j >= k) {Qsort(a,l,j,k);} else if(i <= k) {Qsort(a,i,r,k);}}vector<int> smallestK(vector<int>& arr, int k) {Qsort(arr,0,arr.size() - 1,k);sort(arr.begin(),arr.begin() + k);return vector(arr.begin(),arr.begin() + k);}
};

归并排序
就是合并两个有序序列，每次取左右两边小的数加入新数组，合并后的新序列也有序。子序列也是相同的求法。
求逆序数的话，就是当更小的数是右半部分时，加上mid - i + 1，代表左半部分有这么多数大于右半部分那个数。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;const int maxn = 5e5 + 7;int a[maxn],b[maxn];ll merge(int l,int r)
{if(l == r)return 0;ll ans = 0;int mid = (l + r) >> 1;ans += merge(l,mid);ans += merge(mid + 1,r);int i = l,j = mid + 1,k = l;while(i <= mid || j <= r){if(i > mid || (j <= r && a[i] > a[j])){b[k++] = a[j++];ans += mid - i + 1;//逆序数}else{b[k++] = a[i++];}}for(int p = l;p <= r;p++)a[p] = b[p];return ans;
}int main()
{int n;scanf("%d",&n);for(int i = 1;i <= n;i++)scanf("%d",&a[i]);merge(1,n);for(int i = 1;i <= n;i++)printf("%d ",a[i]);return 0;
}