我所做的就是拿起第一只袜子，把它放下（比如，放在洗衣碗的边缘）。然后我拿起另一只袜子，检查它是否与第一只袜子相同。如果是，我会把它们都去掉。如果不是，我把它放在第一只袜子旁边。然后我拿起第三只袜子，将其与前两只袜子进行比较（如果它们还在的话）。等

这种方法可以很容易地在阵列中实现，假设“移除”袜子是一个选项。实际上，你甚至不需要“脱掉”袜子。如果您不需要对袜子进行排序（见下文），那么您只需移动它们，就可以得到一个数组，该数组中所有袜子都成对排列。

假设袜子的唯一操作是比较相等，这个算法基本上仍然是n2算法，尽管我不知道平均情况（从未学会计算）。

当然，分类可以提高效率，尤其是在现实生活中，你可以很容易地将袜子“插入”在另外两个袜子之间。在计算中，树也可以做到这一点，但这是额外的空间。当然，我们又回到了NlogN（或者更多，如果有几只袜子按排序标准是相同的，但不是来自同一双）。

除此之外，我想不出什么，但这种方法在现实生活中似乎非常有效

这个问题实际上很有哲理。本质上，这是关于人们解决问题的能力（我们大脑的“湿件”）是否等同于算法所能完成的任务。

袜子分类的一个明显算法是：

Let N be the set of socks that are still unpaired, initially empty
for each sock s taken from the dryer
  if s matches a sock t in N
    remove t from N, bundle s and t together, and throw them in the basket
  else
    add s to N

现在这个问题的计算机科学都是关于步骤的

“如果s与N中的袜子t配对”。我们能多快“记住”到目前为止所看到的东西？“从N中删除t”和“将s添加到N”。跟踪我们目前所看到的情况有多贵？

人类将使用各种策略来实现这些目标。人类的记忆是关联的，类似于哈希表，其中存储值的特征集与相应的值本身配对。例如，“红色汽车”的概念映射到一个人能够记住的所有红色汽车。有完美记忆的人有完美的映射。大多数人（以及其他大多数人）在这方面都不完美。关联映射的容量有限。映射可能会在各种情况下（一杯啤酒太多）消失，被错误记录（“我认为她的名字是贝蒂，而不是内蒂”），或者即使我们观察到真相已经改变，也永远不会被覆盖（“爸爸的车”让人想起“橙色火鸟”，而我们实际上知道他用它换了红色的科迈罗）。

就袜子而言，完美回忆意味着看一只袜子总会产生它的同胞t的记忆，包括足够的信息（它在熨衣板上的位置），以便在恒定的时间内找到t。一个有照片记忆的人会在恒定的时间内完成1和2的任务。

记忆力不太好的人可能会根据自己能力范围内的特征使用一些常识等价类：尺寸（爸爸、妈妈、宝宝）、颜色（绿色、红色等）、图案（菱形、素色等）、风格（脚、膝盖高等）。这通常允许通过内存在恒定时间内定位类别，但随后需要通过类别“桶”进行线性搜索。

一个完全没有记忆或想象力的人（抱歉）只会把袜子放在一堆里，然后对整堆袜子进行线性搜索。

一个整洁的怪人可能会像某人建议的那样使用数字标签。这打开了完全排序的大门，允许人类使用与CPU完全相同的算法：二进制搜索、树、散列等。

因此，“最佳”算法取决于运行该算法的湿软件/硬件/软件的质量，以及我们是否愿意通过对其施加总订单来“欺骗”。当然，一个“最好”的元算法是雇佣世界上最好的袜子分类器：一个人或机器可以通过不断的时间查找、插入和删除，在1-1关联存储器中获取并快速存储大量的袜子属性集N。这样的人和机器都可以采购。如果你有一双袜子，你可以在O（N）时间内将所有袜子配对N双，这是最佳的。总订单标签允许您使用标准哈希来获得与人工或硬件计算机相同的结果。

整理n双袜子的问题是O（n）。在你把它们扔进洗衣篮之前，你先把左边的衣服穿到右边的衣服上。取出时，你剪下线，把每一对线放进抽屉里——对n对线进行2次操作，所以O（n）。

现在，下一个问题很简单，你是自己洗衣服，还是妻子洗衣服。这可能是一个完全不同领域的问题。：）

当我对袜子进行排序时，我会进行近似基数排序，将袜子放在同一颜色/图案类型的其他袜子附近。除非在我即将放下袜子的地方/附近，我能看到一对完全匹配的袜子，否则我会在那一刻取出这双袜子。

几乎所有其他算法（包括usr评分最高的答案）排序，然后删除配对。我发现，作为一个人，一次考虑的袜子数量最好尽量减少。

我通过以下方式做到这一点：

挑选一只与众不同的袜子（在袜子堆里最先映入我眼帘的东西）。从概念位置开始基数排序，根据与该位置的相似性从堆中拉出袜子。将新袜子放在当前袜子堆的附近，距离取决于它的不同程度。如果你发现自己将袜子放在另一只袜子的上面，因为它是相同的，请在那里形成一对，然后将它们取下。这意味着未来的比较需要更少的努力来找到正确的位置。

这利用了人类在O（1）时间内进行模糊匹配的能力，这在某种程度上相当于在计算设备上建立哈希图。

通过先穿上与众不同的袜子，你可以留出空间来“放大”那些不那么与众不同的特征。

在去除了浅色、条纹袜子和三双长袜之后，你可能最终会得到大致按磨损程度分类的白色袜子。

在某种程度上，袜子之间的差异很小，以至于其他人不会注意到差异，因此不需要进一步的匹配。

排序解决方案已经提出，但排序有点太多了：我们不需要排序；我们只需要平等团体。

所以散列就足够了（而且更快）。

对于每种颜色的袜子，形成一堆。重复输入篮中的所有袜子，并将它们分配到颜色堆上。在每个桩上循环，并通过其他度量（例如模式）将其分配到第二组桩中递归地应用此方案，直到您将所有袜子分发到非常小的堆上，您可以立即进行可视化处理

当SQL Server需要对庞大的数据集进行哈希连接或哈希聚合时，这种递归哈希分区实际上是由它完成的。它将其构建输入流分配到许多独立的分区中。该方案可线性扩展到任意数量的数据和多个CPU。

如果您可以找到一个分发密钥（哈希密钥），该密钥提供足够的存储桶，使得每个存储桶足够小，可以快速处理，那么您就不需要递归分区。不幸的是，我认为袜子没有这种特性。

如果每只袜子都有一个名为“PairID”的整数，那么可以根据PairID%10（最后一位）轻松地将它们分配到10个桶中。

我能想到的现实世界中最好的分区是创建一个堆积的矩形：一个维度是颜色，另一个是图案。为什么是长方形？因为我们需要O（1）随机访问桩。（3D长方体也可以，但这不太实用。）

更新：

并行性呢？多人能更快地匹配袜子吗？

最简单的并行化策略是让多个工人从输入篮中取出袜子，然后将袜子放到堆上。这只会增加这么多——想象100人在10个桩上战斗。同步成本（表现为手部碰撞和人类通信）破坏了效率和加速（参见通用可扩展性定律！）。这是否容易陷入僵局？不，因为每个工人一次只需要访问一堆。只有一个“锁”，就不会出现死锁。活锁可能是可能的，这取决于人类如何协调对桩的访问。他们可能只是使用随机退避，就像网卡在物理级别上那样，以确定什么卡可以独占地访问网络线路。如果它适用于NIC，那么它也应该适用于人类。如果每个工人都有自己的一组桩，它几乎可以无限扩展。然后，工人可以从输入篮中取出大块袜子（很少有人争抢，因为他们很少这样做），而且他们在分发袜子时根本不需要同步（因为他们有线程局部堆）。最后，所有工人都需要联合他们的桩组。我相信，如果工人形成一个聚合树，这可以在O（log（工人计数*每个工人的桩数））中完成。

元素的清晰度问题呢？正如文章所述，元素区别问题可以用O（N）来解决。袜子问题也是如此（如果你只需要一个分发步骤（我提出了多个步骤，只是因为人类不擅长计算-如果你在md5上分发（颜色、长度、图案…），即所有属性的完美哈希），那么一个步骤就够了）。

显然，一个速度不能比O（N）快，所以我们已经达到了最佳下限。

虽然输出不完全相同（在一种情况下，只是布尔值。在另一种情况中，是袜子对），但渐近复杂性是相同的。

我提出了另一个解决方案，它不会承诺更少的操作，也不会减少时间消耗，但应该尝试看看它是否能成为一个足够好的启发式方法，在大量袜子配对中提供更少的时间消耗。

前提条件：不能保证有相同的袜子。如果它们的颜色相同，并不意味着它们的大小或图案相同。袜子随机洗牌。袜子的数量可能是奇数（有些不见了，我们不知道有多少）。准备记住一个变量“index”并将其设置为0。

结果将有一个或两个桩：1。“匹配”和2。“缺少”

启发式：

找到最与众不同的袜子。找到匹配项。如果没有匹配项，请将其放在“缺失”堆上。从1开始重复。直到没有最与众不同的袜子。如果袜子少于6只，请转到11只。盲目地将所有袜子与邻居配对（不要打包）找到所有匹配的对，将其打包并将打包的对移动到“匹配”的堆中；如果没有新的匹配项-将“索引”增加1如果“index”大于2（这可能取决于袜子的值因为袜子数量越多盲目配对）进入11打乱其余的转到1忘记“索引”挑选一只袜子查找其配对如果没有袜子，就把它移到“失踪”的那一堆如果找到匹配项，将其配对，将其打包并移动到“匹配”堆中如果还有不止一只袜子，那就去12只如果只剩下一个，请转到14满意的微笑：）

此外，还可以添加检查袜子是否损坏，就像移除袜子一样。它可以插入2到3之间，13到14之间。

我期待听到任何经验或更正。