logo标签列表

块排序算法

sortingmergesort
8
从维基百科关于块排序的页面（http://en.wikipedia.org/wiki/Sorting_algorithm）中，我了解到块排序通过将初始数组分成长度为16的小子数组，在O(n)时间内对所有这些子数组进行排序，然后以一种我无法理解的方式合并所有这些块。

例如，考虑一个长度为16的数组，将其分成4个块，每个块的长度为4，对这些块进行排序，我们得到：
10 1 8 3 4 19 20 13 14 17 8 9 12 18 7 20
10 1 8 3 ----- 4 19 20 13 ----- 14 17 8 9 ----- 12 18 7 20
1 3 8 10 ----- 4 13 19 20 ----- 8 9 14 17 ----- 7 12 18 20

请问有人能解释一下合并步骤的工作原理吗？

1
维基百科关于块排序的文章已经更新。为了保持排序的稳定性，使用两组唯一元素作为工作空间，并与被合并的元素交换，以便排序就地完成。由于这些组包含唯一元素，因此无论在合并步骤中将唯一值交换到哪里，都将保持稳定性。该算法的改进版本可以在github block sort上找到。 - rcgldr
2个回答
0
通常，归并排序会进一步将数组分成大小为2的块。为了合并，它创建指向两个块开头的指针并比较它们的值。它选择较小的值并增加相应的指针。
1 4 5 ...
^
2 3 4 ...
^

选择1，因为它更小，并更新指针。
1 4 5 ...
  ^
2 3 4 ...
^

选2个

1 4 5 ...
  ^
2 3 4 ...
  ^

选择3等等....

这些值被放在一个数组中，该数组将与使用相同技术创建的另一个数组进行比较。它会一直进行下去，合并直到所有成员都被排序。我没有考虑在真正的合并算法中可以进行的无尽优化。

0
块排序合并的第一件事是提取缓冲区。这是我唯一了解很多的事情，它开始于此。找到数组长度的平方根，并在开头和结尾找到那么多个独特的值。使用旋转或反转，您可以将它们全部放在开头和结尾。然后，我不知道如何合并其他东西。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接