计数排序
基数排序
桶排序
离散化
1 FOR(i,1,n) tp[i]=a[i]; 2 sort(tp+1,tp+n+1); 3 tot=unique(tp+1,tp+n+1)-tp-1; 4 FOR(i,1,n) a[i]=lower_bound(tp+1,tp+tot+1)-tp;
动态求区间中位数：对顶堆
第k大数O（n）
逆序对
1 // 归并排序求逆序对 2 void merge(int l, int mid, int r) { 3 // 合并a[l~mid]与a[mid+1~r] 4 // a是待排序数组, b是临时数组, cnt是逆序对个数 5 int i = l, j = mid + 1; 6 for (int k = l; k <= r; k++) 7 if (j > r || i <= mid && a[i] < a[j]) b[k] = a[i++]; 8 else b[k] = a[j++], cnt += mid - i + 1; 9 for (int k = l; k <= r; k++) a[k] = b[k]; 10 }