Defant&Kravitz（1）给出了一种算法，通过将袜子依次放在脚上和脚下来对袜子进行排序。

他们的算法适用于任意数量的英尺。

本文给出了（定理1.1）可使用单脚排序的袜子订单的特征。从他们的定理1.3可以看出，每一个4种颜色的袜子订单最多可以用两只脚进行排序，而有5种颜色的袜订单不可能用两只脚排序。

Colin Defant和Noah Kravitz，袜子足部分类（2022）

每当你拿起袜子时，把它放在一个地方。然后你拿起的下一只袜子，如果它与第一只袜子不匹配，就把它放在第一只袜子旁边。如果是，那就有一对。这样，有多少种组合其实并不重要，而且你挑选的每一只袜子只有两种可能——要么它已经在你的袜子数组中匹配，要么它没有匹配，这意味着你将它添加到数组中的一个位置。

这也意味着你几乎肯定不会把所有袜子都放在阵列中，因为袜子会在搭配时被取下。

对于p双袜子（n=2p只袜子），我实际上是这样做的：

从袜子堆里随便拿一只袜子。对于第一只袜子，或者如果之前选择的所有袜子都已配对，只需将袜子放入前面未配对袜子“阵列”的第一个“槽”中。如果有一个或多个选定的未配对袜子，请对照阵列中的所有未配对袜子检查当前袜子。在构建阵列时，可以将袜子分为普通类别或类型（白色/黑色、脚踝/圆领、运动型/连衣裙），并“向下搜索”以仅比较同类。如果你找到了一个可以接受的匹配，把两只袜子放在一起，然后把它们从阵列中去掉。如果没有，请将当前袜子放入阵列中第一个打开的插槽中。对每只袜子重复上述步骤。

这种方案的最坏情况是，每双袜子都不同，必须完全匹配，而且你挑选的第一双n/2袜子都不同。这是你的O（n2）场景，极不可能。如果袜子的独特类型的数量t小于袜子对的数量p=n/2，并且每种类型的袜子都足够相似（通常在穿着相关的术语中），使得该类型的任何袜子都可以与任何其他袜子配对，那么正如我上面所推断的，你必须与之进行比较的袜子的最大数量是t，之后你拉动的下一只袜子将与未配对的袜子之一相匹配。这种情况在普通袜子抽屉中比在最坏情况下更可能发生，并将最坏情况的复杂性降低到O（n*t），其中通常t<<n。

做一些预处理怎么样？我会在每只袜子上缝上一个标记或身份证号码，这样每双袜子都有相同的标记/身份证号码。这个过程可能在你每次买一双新袜子时都会完成。然后，您可以进行基数排序以获得O（n）总成本。为每个标记/身份证号码找一个位置，只需逐一挑选所有袜子并将它们放在正确的位置。

我刚刚完成袜子配对，我发现最好的方法是：

选择一只袜子并将其收起来（为这双袜子创建一个“水桶”）如果下一个是上一个的一对，则将其放到现有的存储桶中，否则创建一个新的存储桶。

在最坏的情况下，这意味着您将有n/2个不同的存储桶，并且您将有n-2个关于哪个存储桶包含当前袜子的确定。显然，如果你只有几对，这个算法会很好地工作；我用了12双鞋。

它不是那么科学，但它工作得很好：）

我的解决方案并不完全符合您的要求，因为它正式需要O（n）“额外”空间。然而，考虑到我的条件，它在我的实际应用中非常有效。因此，我认为这应该很有趣。

与其他任务合并

我的特殊情况是，我不用烘干机，只是把衣服挂在普通的烘干机上。挂布需要O（n）操作（顺便说一句，我在这里总是考虑垃圾箱包装问题），这个问题本质上需要线性的“额外”空间。当我从桶里拿出一只新袜子时，如果这双袜子已经挂好了，我会试着把它挂在旁边。如果是新袜子，我会在旁边留出一些空间。

Oracle机器更好；-）

显然，这需要一些额外的工作来检查是否有匹配的袜子已经挂在某个地方，这将为计算机提供系数约为1/2的解O（n^2）。但在这种情况下，“人为因素”实际上是一种优势——如果匹配的袜子已经挂起，我通常可以很快（几乎为O（1））识别出它（可能涉及到大脑缓存中的一些难以察觉的因素）——将其视为一种有限的“预言机”，如oracle Machine；-）我们人类在某些情况下比数字机器有这些优势；-）

快到O（n）！

因此，将袜子配对的问题与挂布的问题联系起来，我可以免费获得O（n）“额外的空间”，并有一个及时的解决方案，大约O（n），只需要比简单的挂布多一点的工作，即使在非常糟糕的星期一早晨，也可以立即获得一双完整的袜子…；-）