昨天，我在洗衣服时把袜子配对，结果发现我这样做效率不高。我在做一个天真的搜索——挑选一只袜子，然后“反复”寻找那一双袜子。这需要平均在n/2*n/4=n2/8袜子上迭代。
作为一名计算机科学家，我在想我能做什么？排序（根据大小/颜色/…）当然是为了实现O（NlogN）解决方案。
哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。
因此，问题基本上是：
给定一堆n双袜子，其中包含2n个元素（假设每只袜子正好有一对匹配的袜子），用对数的额外空间高效地将它们配对的最佳方式是什么？（如果需要的话，我相信我可以记住这些信息。）
我将感谢回答以下方面的问题：
大量袜子的一般理论解。袜子的实际数量没有那么多，我不相信我的配偶和我有超过30双。（而且很容易区分我的袜子和她的袜子；这也可以用吗？）它是否等同于元素清晰度问题？
当前回答
正如许多作者所指出的，基数排序是一种有效的袜子排序方法。尚未提出的是一种完美的哈希方法。用每双袜子买来的时间来计算真是太麻烦了。在你购买袜子时，只需按顺序给袜子编号，就可以让你在整理袜子时把它们放在自己编号的抽屉里。
最多24双袜子的示例。请注意，较大的袜子隔层消除了将袜子卷在一起的需要，这就是所谓的速度/存储权衡。
其他回答
我刚刚完成袜子配对，我发现最好的方法是：
选择一只袜子并将其收起来（为这双袜子创建一个“水桶”）如果下一个是上一个的一对，则将其放到现有的存储桶中，否则创建一个新的存储桶。
在最坏的情况下，这意味着您将有n/2个不同的存储桶，并且您将有n-2个关于哪个存储桶包含当前袜子的确定。显然，如果你只有几对，这个算法会很好地工作；我用了12双鞋。
它不是那么科学，但它工作得很好：）
由于人脑的结构与现代CPU完全不同，所以这个问题毫无实际意义。
人类可以利用“找到匹配的对”这一事实来战胜CPU算法，这对于一个不太大的集合来说是一个操作。
我的算法：
spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
// Thanks to human visual SIMD, this is one, quick operation.
pair = notice_any_matching_pair();
remove_socks_pair_from_surface(pair);
}
至少这是我在现实生活中使用的，我发现它非常有效。缺点是它需要一个平坦的表面，但通常很丰富。
成本：移动袜子->高，查找/搜索袜子排成一排->小
我们想做的是减少移动次数，并用搜索次数进行补偿。此外，我们还可以利用智人的多威胁环境，在解密缓存中保存更多的东西。
X=您的，Y=您的配偶
从所有袜子的A堆开始：
选择两个袜子，将相应的X袜子放在X线上，将Y袜子放在Y线上的下一个可用位置。
直到A为空。
对于每行X和Y
选择行中的第一只袜子，沿着行搜索，直到找到相应的袜子。放入相应的袜子成品线。可选当您搜索线条时，当前正在查看的袜子与之前的袜子相同，请对这些袜子执行步骤2。
可选地，在第一步中，您从该行中拾取两个袜子，而不是两个，因为缓存内存足够大，我们可以快速识别其中一个袜子是否与您正在观察的行上的当前袜子匹配。如果你有幸拥有三只手臂，那么考虑到受试者的记忆足够大，你可以同时解析三只袜子。
直到X和Y都为空。
Done
然而，由于这与选择排序具有相似的复杂性，由于I/O（移动袜子）和搜索（搜索袜子的行）的速度，所花费的时间要少得多。
案例1：所有袜子都是一样的（顺便说一句，这是我在现实生活中所做的）。
选择其中的任意两个组成一对。恒定时间。
案例2：有固定数量的组合（所有权、颜色、大小、纹理等）。
使用基数排序。这只是线性时间，因为不需要比较。
情况3：组合的数量事先未知（一般情况）。
我们必须进行比较，以检查两只袜子是否成对。选择基于O（n log n）比较的排序算法之一。
然而，在现实生活中，当袜子的数量相对较少（恒定）时，这些理论上的优化算法将无法很好地工作。这可能比顺序搜索花费更多的时间，理论上需要二次时间。
每当你拿起袜子时，把它放在一个地方。然后你拿起的下一只袜子，如果它与第一只袜子不匹配，就把它放在第一只袜子旁边。如果是，那就有一对。这样，有多少种组合其实并不重要，而且你挑选的每一只袜子只有两种可能——要么它已经在你的袜子数组中匹配，要么它没有匹配，这意味着你将它添加到数组中的一个位置。
这也意味着你几乎肯定不会把所有袜子都放在阵列中，因为袜子会在搭配时被取下。
