🐗 🎬 👩🏾‍🚀 美国国旗排序 👨🏽‍🏫 🌘 👩🏿‍🔬

要了解这种“多波段”分类的操作原理，以带有三个条纹的标志为例比较容易上手。并且为了轻松处理三色标志，最好先了解一下它在二色示例中的工作方式。 ~~并处理两种颜色...~~

本文是在EDISON的支持下编写的。

我们从事软件的移植和迁移，以及Android和iOS移动应用程序的开发。

我们喜欢算法理论！ ;-)

两色旗

首先，考虑排序数组中的数字仅以两位分配的情况。为了简单起见，我们假设我们有一个零（低阶）和一个（高阶）数组。

因此，我们只有两个“带”：一个将移动最低有效位（零），而另一个将移动最高位（单位）。任何两个颜色的标志都将进行演示。例如，乌克兰的国旗。

这是怎么回事由于在第一阶段尚不知道有多少个零和我们有多少个单位，因此不清楚每个“带”的最终大小。因此，我们在数组的键上放置了两个指针。对于低阶，指针设置为数组的开头，对于高阶，指针设置为结尾。然后，我们从左到右单次遍历数组，并查看每个位元素。

如果在传递过程中某个元素等于最高顺序，则第二个指针会告诉我们该元素的传递位置（我们进行交换）。插入下一个元素的指针向左移动，高级数字的“条”已扩展。

如果它等于最低有效位，则将其指针向右移动一个元素。由于我们只有两位数，因此不必转移元素，因为它已经存在。较年轻类别的“条带”自然变宽了。

结果，两个指向彼此的指针将在一个点上碰撞，并且放电将在其“带”中排序。同时，您将不需要遍历整个数组-当指针在中间的某个地方相遇时，算法将完成其工作。

荷兰国旗问题::荷兰国旗问题

我们使任务稍微复杂化，不考虑两位数，而是考虑三位数字。让我们让数组的元素属于最低（零），中间（单位）和高级（两个）数字。

为了演示，我们以~~法国，~~ ~~俄罗斯~~ ~~卢森堡，~~荷兰的~~石勒苏益格-戈尔德斯坦~~的三向红白蓝旗~~标为准~~ 。为什么是荷兰的国旗呢？因为Edsger Dijkstra在有关该标志示例的演讲中检查了相应的算法，该算法被称为“荷兰国旗的任务”。

如您所见，没有什么特别新的东西。每个类别都有其自己的指针。最初，初中和中级的标签占据数组开头的起始位置，并在遇到相应元素时向右移动。高阶指针首先在数组的末尾，并向左移动。

实际上，通过数组也将是不完整的，如果位或多或少均匀地分布，则该算法将通过数组的2/3，然后将所有元素散布在其“带”中。

美国国旗分类::美国国旗分类

现在，在我们的解释中，我们可以继续使用多频段美国国旗。

当我们没有两个，不是三个，而是任意数量的数字时，我们确定每个数字应从何处开始（其“带”），并在其“带”中重新绘制元素。

在此算法中，数字通常不视为小数，而是以不同的数字表示，通常是2的幂。通常，数字256被用作位深度的基础（比128小一些），这使您可以有效地进行排序以排列字符串。对于位深度的数字，较小的2 ⁿ （2、4、16等）更方便，它允许您通过按位移位进行比较，而不是在比较十进制数字时提高幂。

动画显示了一个基数为16的位深度的示例：

在第一遍-搜索最大值，以便确定阵列中元素之间的最大位数（以便从元素中正确提取从帐户中确定的位数）。
然后发生递归处理。调用时，将指示子数组和当前处理位的边界。第一次调用时，整个数组是一个子数组；左侧的第一位被占用。
在子数组的元素中，将执行初始计算-当前类别中每个数字出现多少次。通过此计数，您可以确定这些数字位数的位置（即，已知要将特定数字中具有下一个数字的元素移至“带”的范围和位置）。实际上，本地化是指向“带”的指针，在这些带中需要移动相应的元素。
根据本地化指针，将在现场进行交换-类别中的数字显示您要向其发送元素的位置，与之发生交换的另一个元素将发生位置。该子句将一直执行，直到在下一次交换中不存在从另一个位置到达的元素为止（然后您可以移至子数组的下一个元素，并类似地对其执行此子句）。
作为交换的结果，元素通过下一个数字中的数字重新分配到块中，然后进行递归-将相同的算法作为子数组应用于每个块，下一个作为当前数字。

在关于对具有近似分布的排序进行计数的文章中，有一种视觉上非常相似的算法- 近似排序 。在那里，我们计算了数组中每个数字出现了多少次-并根据获得的位置重新分配了元素。在这里，我们考虑子数组元素中类别中的每个数字出现多少次-并根据获得的位置重新分配子数组中的元素。如果近似值是一种计数排序，则“ American”是计数位排序。

美国国旗排序-Python实现

#           def get_radix_val(x, digit, radix) -> int: return int(floor(x / radix**digit)) % radix #             def compute_offsets(a_list, start: int, end: int, digit, radix) -> list: #          counts = [0 for _ in range(radix)] for i in range(start, end): #        #         val = get_radix_val(a_list[i], digit, radix) counts[val] += 1 #       #          offsets = [0 for _ in range(radix)] sum = 0 #         for i in range(radix): offsets[i] = sum sum += counts[i] return offsets #      def swap(a_list, offsets, start: int, end: int, digit, radix) -> None: i = start #          next_free = copy(offsets) #        #   (       ) cur_block = 0 while cur_block < radix-1: # if i >= start + offsets[cur_block+1]: cur_block += 1 continue radix_val = get_radix_val(a_list[i], digit, radix) if radix_val == cur_block: i += 1 continue swap_to = next_free[radix_val] a_list[i], a_list[swap_to] = a_list[swap_to], a_list[i] next_free[radix_val] += 1 #   def american_flag_sort_helper(a_list, start: int, end: int, digit, radix) -> None: #          offsets = compute_offsets(a_list, start, end, digit, radix) #      swap(a_list, offsets, start, end, digit, radix) if digit == 0: #     ? return #   #       for i in range(len(offsets)-1): #      #         american_flag_sort_helper(a_list, offsets[i], offsets[i+1], digit-1, radix) #   def american_flag_sort(a_list, radix) -> None: #,         for x in a_list: assert(type(x) == int) #    max_val = max(a_list) #    (  ) max_digit = int(floor(log(max_val, radix))) #   -     american_flag_sort_helper(a_list, 0, len(a_list), max_digit, radix)