algorithm - 将相似类型的元素放在一起

Question

我在某处读到这个面试问题并试图解决它:

给定一个水果摊(最多 8 种不同类型的水果)。将相似类型的水果放在一起。限制:a) Fruit Stall 是你的整个世界(即不要使用额外的空间)，b) 拿一个水果并知道它的类型 (getType()) 是一个代价高昂的操作，但交换是一个非常便宜的操作。

注意:您需要编写代码来处理所有情况，记住水果的最大类型可以是 8 种。

所以，我想到的想法是，我们需要为所有水果(数组元素)调用 getType()，然后根据特定类型对它们进行相应的排序。在不知道水果类型的情况下，我不知道如何在这里进行交换，什么是解决这个问题的最佳方法？

Answer 1

由于这是一道面试题，我假设你的水果摊是一个数组。将数组分成八个区域，使每个区域仅包含给定类型的水果，使用七个指针，一个指针指向除第一个区域之外的每个区域的开头。使用第八个指针指向未排序区域的开始。

初始化指向数组开头的指针。获取指针的定义很棘手，因为您必须涵盖没有给定类型的水果的情况。一个可能的定义是指针 i 包含到目前为止排序的水果的数量，直到并包括 i，因为 i = 1..8。然后在开始时所有指针都设置为零，并且 1 1 1 2 2 3 4 4 |对应p1=3 p2=5 p3=6 p4=8 p5=p6=p7=p8=8

反复查看未分类区域开头的第一个水果，找出它的类型。如果它不应该进入最终区域，则将它与最终区域开始处的元素交换，并将指针前进到最终区域的开始。如果它不应该进入倒数第二个区域，则将它与倒数第二个区域开始处的元素交换，并将指针前进到倒数第二个区域的开始......等等，直到新水果位于正确的位置.现在将指针前进到第一个未分类的水果并重复。

这会查看每个水果一次，我认为您无法通过较少调用 getType() 来进行排序。你不关心交换的次数，所以我认为这是最优的。

我将显示以 c1、c2、c1、c3、c2、c1、c4、c4 开头的交换行。我不会费心在 cs 中写，我会使用 |将已知一切有序的左侧区域与类型未知的右侧区域分开

| 1 2 1 3 2 1 4 4

1 | 2 1 3 2 1 4 4

1 2 | 1 3 2 1 4 4

1 1 | 2 3 2 1 4 4

1 1 2 | 3 2 1 4 4

1 1 2 3 | 2 1 4 4

1 1 2 2 | 3 1 4 4

1 1 2 2 3 | 1 4 4

1 1 2 2 1 | 3 4 4

1 1 1 2 2 | 3 4 4

1 1 1 2 2 3 | 4 4

1 1 1 2 2 3 4 | 4

1 1 1 2 2 3 4 4 |