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

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

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

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

成本：移动袜子->高，查找/搜索袜子排成一排->小

我们想做的是减少移动次数，并用搜索次数进行补偿。此外，我们还可以利用智人的多威胁环境，在解密缓存中保存更多的东西。

X=您的，Y=您的配偶

从所有袜子的A堆开始：

选择两个袜子，将相应的X袜子放在X线上，将Y袜子放在Y线上的下一个可用位置。

直到A为空。

对于每行X和Y

选择行中的第一只袜子，沿着行搜索，直到找到相应的袜子。放入相应的袜子成品线。可选当您搜索线条时，当前正在查看的袜子与之前的袜子相同，请对这些袜子执行步骤2。

可选地，在第一步中，您从该行中拾取两个袜子，而不是两个，因为缓存内存足够大，我们可以快速识别其中一个袜子是否与您正在观察的行上的当前袜子匹配。如果你有幸拥有三只手臂，那么考虑到受试者的记忆足够大，你可以同时解析三只袜子。

直到X和Y都为空。

Done

然而，由于这与选择排序具有相似的复杂性，由于I/O（移动袜子）和搜索（搜索袜子的行）的速度，所花费的时间要少得多。

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

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

从你的问题来看，你显然没有太多洗衣方面的实际经验：）。你需要一种算法，能很好地处理少量不可配对的袜子。

到目前为止，答案还没有充分利用我们的人类模式识别能力。集合游戏提供了如何做好这一点的线索：将所有袜子放在一个二维空间中，这样你就可以很好地识别它们，并用手轻松地够到它们。这将您的面积限制在120*80厘米左右。从那里选择您识别的配对并将其删除。将多余的袜子放在空闲空间，然后重复。如果你为穿着容易辨认的袜子的人洗衣服（脑海中浮现的是小孩子），你可以先选择袜子来进行基数排序。该算法仅在单袜子数量较少时有效

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

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

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

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

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

你试图解决错误的问题。

解决方案1：每次你把脏袜子放进洗衣篮时，把它们打个小结。这样你就不用在洗完衣服后做任何分类了。把它想象成在Mongo数据库中注册索引。未来需要做一些工作来节省CPU。

解决方案2：如果是冬天，你不必穿配套的袜子。我们是程序员。没有人需要知道，只要它有效。

解决方案3：分散工作。您希望异步执行如此复杂的CPU进程，而不阻塞UI。把那堆袜子塞进袋子里。只有在你需要的时候才找一双。这样，你的工作量就不那么明显了。

希望这有帮助！