目录

 

归并排序：

完整代码：

快速排序：

---

归并排序：

思路：进行二分，然后合并。对于合并的两个模块，每一个模块必定已排好，因为是排完才合并。

例如2 4 6 | 1 3 7；双“指针”，一个指向左边、一个指向右边。

右边1<左边2  1进入b数组 此时2 4 6|3 7  b={1}；右边3>左边2  2进入b数组 此时4 6|3 7    b={1,2}

……

以此类推。

由此发现，右边的进入时，左边剩下了多少就有多少逆序对，并且合并回溯过程中，每一个数都会和它前面的数进行分组(就是这里的左右)。

所以，只需在需要将右边数加入时加上这条语句即可ans += (ll)(mid-p1+1);mid时最后一个左组元素的下标。

注意：等号的时候让左组进入，因为相等这不是逆序对。

void _merge(int l,int mid,int r){ int p1 = l,p2 = mid+1; for(int i = l;i <= r;i++){ if(((a[p1] <= a[p2])||(p2 > r))&&p1<=mid){ b[i] = a[p1++]; }//等号无所谓，这里为了求逆对数，相等的情况让前面的先进去，主要靠后面进行求逆对数 else { b[i] = a[p2++]; } } for(int i = l;i <= r;i++) a[i] = b[i]; return ; } void erfen(int l,int r){ int mid = (l+r)>>1; if(l < r){ erfen(l,mid); erfen(mid+1,r); } _merge(l,mid,r); return ; }

完整代码：

#include<algorithm> #include<iostream> #include<cstring> #include<string> #include<cstdlib> #include<map> #include<cmath> #include<vector> using namespace std; typedef long long ll; const int maxn = 1e6+50; ll a[maxn]; ll b[maxn]; ll ans; void _merge(int l,int mid,int r){ int p1 = l,p2 = mid+1; for(int i = l;i <= r;i++){ if(((a[p1] <= a[p2])||(p2 > r))&&p1<=mid){ b[i] = a[p1++]; }//等号无所谓，这里为了求逆对数，相等的情况让前面的先进去，主要靠后面进行求逆对数 else { b[i] = a[p2++]; ans += (ll)(mid-p1+1); } } for(int i = l;i <= r;i++) a[i] = b[i]; return ; } void erfen(int l,int r){ int mid = (l+r)>>1; if(l < r){ erfen(l,mid); erfen(mid+1,r); } _merge(l,mid,r); return ; } int main(){ int n; cin >> n; for(int i = 0;i < n;i++) cin >> a[i]; ans = 0; erfen(0,n-1); cout << ans << endl; return 0; }

快速排序：

找到一个基准点，小于它的在左侧，大于它的在右侧，然后递归对两侧同样执行。

void q_sort(int l,int r){ int i = l,j = r; int mid = (l+r)>>1; int x = a[mid]; while(i <= j){ while(a[i] < x) i++; while(a[j] > x) j--; if(i <= j){ swap(a[i],a[j]); i++;j--; } } if(l < j) q_sort(l,j); if(i < r) q_sort(i,r); }

寻找第k小数，那么就进行改进。

如果找到了一个数，基准点位置最后在….x…..，如果x<k的话，左侧肯定不会是第k小数，都没有k个数，左侧不必再排序，砍掉一半。如果x>k的话，右侧肯定不会是第k小数，因为左侧多余k个数，右侧都大于左侧，所以肯定在左侧。

void q_sort(int l,int r){ int i = l,j = r; int mid = (l+r)>>1; int x = a[mid]; while(i <= j){ while(a[i] < x) i++; while(a[j] > x) j--; if(i <= j){ swap(a[i],a[j]); i++;j--; } } if(k == i-1){ printf("%d\n",a[k]); return ; } else if(k < i-1){ q_sort(l,i-1); } else q_sort(i,r); }