Chinaunix

标题: 开了一下脑洞，假如数值会溢出，该如何排序？ [打印本页]

作者: wait_rabbit 时间: 2015-03-18 20:25
标题: 开了一下脑洞，假如数值会溢出，该如何排序？

有 256 个箱子，箱子上的数字分别是 0 - 255。现在每次随机抽出一个箱子，并且以第 1 个箱子为最小，箱子的“大小”以 1 递增。

比如我第一个箱子抽出是 251，那么排序结果应该是：

251，252，253，254，255，0，1，2，3， …… 248，249，250

复制代码

如果第一个箱子是 5，那么排序结果应该是：

5，6，7，8，…… 253，254，255，0，1，2，3，4

复制代码

有啥好点的算法没？

作者: windoze 时间: 2015-03-18 20:41
用这个表达式的结果排序：(x+256-n)%256
x是每次抽出来的数，n是你第一次抽出来的数

作者: wait_rabbit 时间: 2015-03-18 21:01
回复 2# windoze

这个可以有，相当于平移了一下 x 轴。

作者: folklore 时间: 2015-03-18 21:55
>>有 256 个箱子，箱子上的数字分别是 0 - 255。现在每次随机抽出一个箱子，并且以第 1 个箱子为最小，箱子的“大小”以 1 递增。

直接输出结果即可，无须排序。～！复杂度定数256

作者: hellioncu 时间: 2015-03-19 08:56
unsigned char n = firstNum;

for (int i = 0; i < 256; ++i)
printf("%u ", n++);

作者: 流氓无产者 时间: 2015-03-19 09:29

hellioncu 发表于 2015-03-19 08:56
unsigned char n = firstNum;

for (int i = 0; i < 256; ++i)

wk,还是你看懂了

作者: wait_rabbit 时间: 2015-03-19 09:36

folklore 发表于 2015-03-18 21:55
>>有 256 个箱子，箱子上的数字分别是 0 - 255。现在每次随机抽出一个箱子，并且以第 1 个箱子为最小，箱子 ...

现在老板给你 2^128个箱子，只抽100个进行排序。看不炒你的鱿鱼。

作者: wait_rabbit 时间: 2015-03-19 09:47
回复 5# hellioncu

现在只随机抽50个箱子。作弊的直接炒鱿鱼。

作者: hellioncu 时间: 2015-03-19 09:51

wait_rabbit 发表于 2015-03-19 09:47
回复 5# hellioncu

现在只随机抽50个箱子。作弊的直接炒鱿鱼。

啥意思？不懂你到底要啥

作者: wait_rabbit 时间: 2015-03-19 09:54
本帖最后由 wait_rabbit 于 2015-03-19 09:58 编辑

回复 9# hellioncu

比如现在只抽了 5 个箱子，抽出来的顺序是：

20，9，255，200，3

复制代码

那么“递增”排序后的如下：

20，200，255，3，9

复制代码

作者: hellioncu 时间: 2015-03-19 10:05

wait_rabbit 发表于 2015-03-19 09:54
回复 9# hellioncu

比如现在只抽了 5 个箱子，抽出来的顺序是：那么“递增”排序后的如下：

按 (unsigned char)(x － 20) 的大小排序

作者: wait_rabbit 时间: 2015-03-19 10:09
回复 11# hellioncu

嗯，沙发就是你说的这样。

我本来是想可以临时提升成一个16位数来算，不过还是你俩这种好。

作者: yulihua49 时间: 2015-03-19 12:25

wait_rabbit 发表于 2015-03-18 20:25
有 256 个箱子，箱子上的数字分别是 0 - 255。现在每次随机抽出一个箱子，并且以第 1 个箱子为最小，箱子 ...

方法没什么不同，只不过用了特别的比较器，见2楼。
这个叫“循环数”，有专门的算法。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)