比较不需要时间时进行排序
我想在这个成本模型下对数组A进行排序：
- 对于任何值x，形式Ai =x的赋值成本为1。此外，Ai = Aj的成本为1。
- 其他操作(如for x= A我的比较和赋值)的成本为0。
问题：
- 给出排序数组A所需的最坏情况时间的下限。你的答案应该是n的精确表达式，而不是使用渐近表示法。
- 描述一个使用O(n)空间的排序算法。运行时应该与1中给出的下限完全匹配(准确，而不是渐近)。
- 描述一种对此成本模型最优的就地排序算法。运行时应该与1中给出的边界完全匹配(准确，而不是渐近)。
我的尝试：
- 这是因为，在最坏的情况下，数组中的n个元素位于它们不应该存在的索引中。因此，需要n个赋值才能按排序顺序得到数组。
- 我在psudo代码中的算法： def weird_sort(A)：B=数组相同大小的an = bools数组(默认为True)相同大小的A对于i在范围内(0，A.size)：min =c中的第一个索引，对于j在范围内为真(0，A.size)：if (Aj < Amin)和(Cj)：min =j Bi = Amin Ci = False A=B
我相信这完全需要n个时间来运行，因为我们将任何东西分配到A中的唯一时间是在最后一行，其中我们将B的内容复制到A中。
- 不知道从哪里开始。在我看来，为了保持一切就绪，我们必须在数组A中交换东西，但我不知道如何使用n/2交换来排序数组。有人能让我朝着正确的方向前进吗？你也能仔细检查一下我的答案吗？
回答 2
Stack Overflow用户
发布于 2017-10-21 17:59:39
我考虑内部允许O(1)附加变量，因为否则我认为这是不可能的
首先让我们解决子问题:给定i，找到i-th位置上的数字。使用蛮力是可能的，因为比较是免费的。
现在复制第一个元素(到附加变量)，找到最小的元素并把它放在位置1。现在这个元素位于i位置。让我们找到应该在位置i上的元素，然后在这里复制它(假设它在j位置上)，现在查找属于位置j的元素，等等。最后我们找到了我们最初复制的元素，并把它放回去。因此，我们使用k分配(在循环结构中)将k变量设置到它们的位置。现在，对所有其他元素也这样做。您不能记住每个变量是否放在它的位置上，但是您可以检查它是否是免费的。
如果A中有相同的元素，则应该更仔细地进行，但仍应起作用
Stack Overflow用户
发布于 2017-10-23 00:21:44
虽然在讨论高效排序算法时，我们通常倾向于讨论快速排序，但这类算法是对比较次数进行优化的。
然而，其他算法则尝试优化内存访问的数量(如您的情况)。其中一些算法被称为缓存遗忘算法(不要对特定的内存层次结构参数进行假设)和缓存感知算法(它们是针对特定的内存层次结构进行调优的)。您可以找到这种类型的多个算法，因此您可能会对它们感兴趣。
例如，的PhD论文讨论了缓存遗忘算法，并提出了分布排序，它将数据部分地按子组排序，这些子组可能适合内存层次结构的较低分区。
分发排序使用
O(n ln(n))工作，并导致O(1+ (L/n)*(1+logz(n))缓存丢失对n个元素进行排序。
其中L是缓存库的大小，z是缓存本身的大小。性能模型仅假设只有一个缓存级别，尽管由于不经意属性，它适应了所有缓存级别。
基本概念是，分配成本取决于元素放置在内存层次结构中的位置。
https://stackoverflow.com/questions/46869506
复制
腾讯云开发者
