提交记录 9620
提交时间 |
评测时间 |
2019-06-20 15:47:05 |
2020-08-01 01:41:20 |
#include <string.h>
#include <algorithm>
void LSD_Radix_Sort(unsigned *a, int n) {
unsigned _b[n];
unsigned *b = _b;
int cnt[256];
for (int i = 0; i < 32; i += 8) {
memset(cnt, 0, sizeof(cnt));
for (int j = 0; j < n; j++) cnt[(a[j] >> i) & 255]++;
for (int j = 1; j < 256; j++) cnt[j] += cnt[j - 1];
for (int j = n - 1; j >= 0; j--) b[--cnt[(a[j] >> i) & 255]] = a[j];
std::swap(a, b);
}
}
void MSD_Binary_Sort(unsigned *a, int n, int bit = 31) {
if (n <= 100000) return LSD_Radix_Sort(a, n), void();
if (n <= 1 || bit < 0) return;
unsigned *ed = a + n;
unsigned *p = a;
while (p < ed) {
if ((*p >> bit) & 1u) {
--ed;
std::swap(*p, *ed);
} else {
++p;
}
}
--bit;
MSD_Binary_Sort(a, p - a, bit);
MSD_Binary_Sort(p, n - (p - a), bit);
}
void sort(unsigned *a, int n) {
MSD_Binary_Sort(a, n);
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 88.6 us | 88 KB | Accepted | Score: 100 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2024-04-18 14:15:10 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用