实现Thanos排序算法
实现Thanos排序算法
提问于 2019-03-26 10:21:32
排序算法如下所示：
当列表未被排序时，抓取所有项目的一半(从列表中删除它们)。继续，直到列表被排序或只剩下一项(默认情况下是排序的)。这种排序算法可能会根据实现给出不同的结果。
项目删除过程由实现来决定，但在项目删除过程一次通过之后，列表应该是之前的一半。您的算法可能决定删除列表的前半部分或列表、列表的后半部分、所有奇数项、所有偶数项，每次删除一个，直到列表的长度减半，或任何未提及的项。
输入列表可以包含任意数量的项(在合理范围内，假设最多有1000个项)，而不仅仅是2^n项的完全可除列表。如果列表是奇数，则必须删除(n+1)/2或(n-1)/2项，要么硬编码，要么在运行时随机决定。你自己决定:如果宇宙中有一堆奇怪的生物，萨诺斯会怎么做？
如果没有任何项比以前的任何项小，则对列表进行排序。重复项可能发生在输入中，也可能发生在输出中。
您的程序应该接受一个整数数组(通过stdin或作为参数，无论是单个项还是数组参数)，并返回排序数组(或将其打印到stdout)。
示例：
// A sorted list remains sorted
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
// A list with duplicates may keep duplicates in the result
[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item
[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] -> [3] // Removing the first half
[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half[1, 2, 4, 3, 5]可以给出不同的结果：
// Removing every second item:
[1, 2, 4, 3, 5] -> [1, 4, 5]或者：
// Removing the first half of the list
[1, 2, 4, 3, 5] -> [3, 5] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [4, 3, 5] -> [3, 5] // With (n-1)/2 items removed或者：
// Removing the last half of the list
[1, 2, 4, 3, 5] -> [1, 2] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [1, 2, 4] // With (n-1)/2 items removed或者：
// Taking random items away until half (in this case (n-1)/2) of the items remain
[1, 2, 4, 3, 5] -> [1, 4, 3] -> [4, 3] -> [4]回答 23
Code Golf用户
发布于 2019-03-26 19:27:00
布氏对数 (v2)，6字节
≤₁|ḍt↰这是一个函数提交。从左边输入，像往常一样输出到右边。( TIO链接使用一个命令行参数，它自动将函数包装成一个完整的程序，这样您就可以看到它在运行。)
解释
≤₁|ḍt↰
≤₁ Assert that {the input} is sorted {and output it}
| Handler for exceptions (e.g. assertion failures):
ḍ Split the list into two halves (as evenly as possible)
t Take the last (i.e. second) half
↰ Recurse {and output the result of the recursion}奖金循环
≤₁|⊇ᵇlᵍḍhtṛ↰这张照片是随机的，不是吗？下面是程序的一个版本，它随机选择幸存的元素(同时确保在每一轮中有一半存活)。
≤₁|⊇ᵇlᵍḍhtṛ↰
≤₁ Assert that {the input} is sorted {and output it}
| Handler for exceptions (e.g. assertion failures):
⊇ᵇ Find all subsets of the input (preserving order)
lᵍ Group them by length
ḍht Find the group with median length:
t last element of
h first
ḍ half (split so that the first half is larger)
ṛ Pick a random subset from that group
↰ Recurse如果我们能重新排序元素，这会更短，但是为什么排序算法会这样做呢？
页面原文内容由Code Golf提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codegolf.stackexchange.com/questions/182221
复制相关文章
相似问题
腾讯云开发者
