快排
直接用自带的函数实现即可,sort(起点,终点,排列规则(这个可以没有))。
归并
通常会用来求逆序对。
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
\(O(n)\) 的基数排序(位运算版本)
最快的排序方法。
inline void Sort() {
static ll p = 65535;
for (rl i = 1; i <= n; ++i) c[a[i] & p]++;
for (rl i = 1; i <= p; ++i) c[i] += c[i - 1];
for (rl i = n; i >= 1; --i) b[c[a[i] & p]--] = i;
memset(c, 0, sizeof c);
for (rl i = 1; i <= n; ++i) c[(a[b[i]] >> 16) & p]++;
for (rl i = 1; i <= p; ++i) c[i] += c[i - 1];
for (rl i = n; i >= 1; --i) d[c[(a[b[i]] >> 16) & p]--] = b[i];
for (rl i = 1; i <= n; ++i) b[i] = d[i];
}
排完序后 b 中是排好的序列。