提交记录 9621


用户 题目 状态 得分 用时 内存 语言 代码长度
wys 1001. 测测你的排序 Accepted 100 4.939 s 391020 KB C++ 837 B
提交时间 评测时间
2019-06-20 15:47:11 2020-08-01 01:41:27
#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);
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #14.939 s381 MB + 876 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 16:12:34 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用