我在攻读计算机科学博士期间经常思考这个问题。我提出了多种解决方案，这取决于区分袜子的能力，从而尽可能快地找到正确的袜子。

假设看袜子和记住它们独特图案的成本可以忽略不计（ε）。那么最好的解决办法就是把所有的袜子都扔到桌子上。这包括以下步骤：

将所有袜子放在一张桌子上（1），并创建一个hashmap｛pattern:position｝（ε）当有剩余袜子时（n/2）：随机挑选一只袜子（1）查找相应袜子的位置（ε）取回袜子（1）并存放

这确实是最快的可能性，并且以n+1＝O（n）复杂度执行。但它假设你完全记得所有的模式。。。在实践中，情况并非如此，我个人的经验是，你有时在第一次尝试时找不到匹配的一对：

把所有袜子扔在桌子上（1）当有剩余袜子时（n/2）：随机挑选一只袜子（1）当未配对时（1/P）：找到具有相似图案的袜子拿袜子，比较两者（1）如果可以，存储配对

这现在取决于我们找到匹配对的能力。如果你的深色/灰色双鞋或白色运动袜经常有非常相似的图案，这一点尤其正确！让我们承认你有概率找到相应的袜子。在找到相应的袜子以形成一双袜子之前，平均需要1/P的尝试。总体复杂度为1+（n/2）*（1+1/P）=O（n）。

两者在袜子数量上都是线性的，并且是非常相似的解决方案。让我们稍微修改一下这个问题，承认你有多双类似的袜子，并且很容易在一次移动中存储多双袜子（1+ε）。对于K个不同的模式，您可以实现：

对于每只袜子（n）：随机挑选一只袜子（1）将其放到其模式的集群中对于每个集群（K）：取簇并储存袜子（1+ε）

总体复杂度变为n+K=O（n）。它仍然是线性的，但选择正确的算法现在可能很大程度上取决于P和K的值！但人们可能会再次反对，因为您可能很难找到（或创建）每只袜子的集群。

此外，你也可以在网站上查找最佳算法，并提出自己的解决方案，从而节省时间：）

正如许多作者所指出的，基数排序是一种有效的袜子排序方法。尚未提出的是一种完美的哈希方法。用每双袜子买来的时间来计算真是太麻烦了。在你购买袜子时，只需按顺序给袜子编号，就可以让你在整理袜子时把它们放在自己编号的抽屉里。

最多24双袜子的示例。请注意，较大的袜子隔层消除了将袜子卷在一起的需要，这就是所谓的速度/存储权衡。

作为实际解决方案：

快速制作一堆易于区分的袜子。（用颜色表示）快速整理每一堆，并使用袜子的长度进行比较。作为一个人，你可以很快地决定用哪只袜子进行分区，以避免最坏的情况。（你可以看到多只袜子平行排列，这对你有利！）当垃圾堆达到一个阈值时，停止分类，在该阈值下，您可以立即找到不合适的袜子和短袜

如果你有1000只袜子，有8种颜色，平均分布，你可以在c*n时间内每125只袜子做4堆。以5只袜子为阈值，你可以在6次跑步中对每一堆袜子进行分类。（数2秒把袜子扔到正确的堆上，只需要不到4小时。）

如果你只有60只袜子、3种颜色和2种袜子（你/你妻子的），你可以在1次跑步中对每一堆10只袜子进行分类（同样阈值=5）。（数2秒，需要2分钟）。

最初的桶排序将加快您的进程，因为它在c*n时间内将n个袜子分成k个桶，因此您只需执行c*n*log（k）工作。（不考虑阈值）。所以，你所做的所有关于n*c*（1+log（k））的工作，其中c是把袜子扔在一堆上的时间。

与任何c*x*n+O（1）方法相比，只要log（k）<x-1，该方法将是有利的。

在计算机科学中，这可能很有用：我们有一个n个事物的集合，它们的顺序（长度）和等价关系（额外的信息，例如袜子的颜色）。等价关系允许我们对原始集合进行分区，并且在每个等价类中我们的顺序仍然保持不变。一个事物到它的等价类的映射可以在O（1）中完成，因此只需要O（n）就可以将每个项分配给一个类。现在我们已经使用了额外的信息，可以以任何方式对每个类进行排序。其优点是数据集已经明显更小。

该方法也可以嵌套，如果我们有多个等价关系->使颜色堆积，而不是在纹理上的每个堆积分区内，而不是按长度排序。任何等价关系如果创建一个分区，其中包含2个以上的元素，且大小大致相等，那么与排序相比，排序的速度都会有所提高（前提是我们可以直接将袜子分配给它的堆），并且排序可以在较小的数据集上快速进行。

创建一个哈希表，该表将用于不匹配的袜子，使用模式作为哈希。一只一只地重复袜子。如果袜子在哈希表中有图案匹配，请将袜子从表中取出并配对。如果袜子没有火柴，就把它放到桌子上。

如果“移动”操作相当昂贵，而“比较”操作很便宜，并且无论如何都需要将整个集合移动到一个缓冲区中，在那里搜索速度比原始存储快得多。。。只需将排序整合到强制移动中即可。

我发现，将分拣过程整合到晾衣架中，这一过程变得轻而易举。无论如何，我需要拿起每一只袜子，然后把它挂起来（移动），把它挂在绳子上的某个特定位置几乎不需要任何费用。现在，为了不强制搜索整个缓冲区（字符串），我选择按颜色/阴影放置袜子。左边更黑，右边更亮，前面更鲜艳。现在，在我挂上每一只袜子之前，我先看看它的“右边附近”是否已经有一只匹配的袜子——这限制了“扫描”其他2-3只袜子——如果有，我就把另一只挂在旁边。然后，我把它们成对地卷起来，然后在干的时候把它们从绳子上取下来。

现在，这似乎与顶级答案所建议的“按颜色形成桩”没有什么不同，但首先，通过不选择离散桩而是选择范围，我没有问题将“紫色”分类为“红色”还是“蓝色”桩；它只是介于两者之间。然后通过集成两个操作（挂起晾干和分拣），挂起时的分拣开销大约是单独分拣的10%。

两种思路，查找任何匹配项所需的速度，与查找所有匹配项所需要的速度相比，与存储相比。

对于第二种情况，我想指出一个GPU并行版本，它查询所有匹配的袜子。

如果您有多个要匹配的财产，则可以使用分组元组和更高级的zip迭代器以及推力的转换函数，尽管这里是一个基于GPU的简单查询：

//test.cu
#include <thrust/device_vector.h>
#include <thrust/sequence.h>
#include <thrust/copy.h>
#include <thrust/count.h>
#include <thrust/remove.h>
#include <thrust/random.h>
#include <iostream>
#include <iterator>
#include <string>

// Define some types for pseudo code readability
typedef thrust::device_vector<int> GpuList;
typedef GpuList::iterator          GpuListIterator;

template <typename T>
struct ColoredSockQuery : public thrust::unary_function<T,bool>
{
    ColoredSockQuery( int colorToSearch )
    { SockColor = colorToSearch; }

    int SockColor;

    __host__ __device__
    bool operator()(T x)
    {
        return x == SockColor;
    }
};


struct GenerateRandomSockColor
{
    float lowBounds, highBounds;

    __host__ __device__
    GenerateRandomSockColor(int _a= 0, int _b= 1) : lowBounds(_a), highBounds(_b) {};

    __host__ __device__
    int operator()(const unsigned int n) const
    {
        thrust::default_random_engine rng;
        thrust::uniform_real_distribution<float> dist(lowBounds, highBounds);
        rng.discard(n);
        return dist(rng);
    }
};

template <typename GpuListIterator>
void PrintSocks(const std::string& name, GpuListIterator first, GpuListIterator last)
{
    typedef typename std::iterator_traits<GpuListIterator>::value_type T;

    std::cout << name << ": ";
    thrust::copy(first, last, std::ostream_iterator<T>(std::cout, " "));
    std::cout << "\n";
}

int main()
{
    int numberOfSocks = 10000000;
    GpuList socks(numberOfSocks);
    thrust::transform(thrust::make_counting_iterator(0),
                      thrust::make_counting_iterator(numberOfSocks),
                      socks.begin(),
                      GenerateRandomSockColor(0, 200));

    clock_t start = clock();

    GpuList sortedSocks(socks.size());
    GpuListIterator lastSortedSock = thrust::copy_if(socks.begin(),
                                                     socks.end(),
                                                     sortedSocks.begin(),
                                                     ColoredSockQuery<int>(2));
    clock_t stop = clock();

    PrintSocks("Sorted Socks: ", sortedSocks.begin(), lastSortedSock);

    double elapsed = (double)(stop - start) * 1000.0 / CLOCKS_PER_SEC;
    std::cout << "Time elapsed in ms: " << elapsed << "\n";

    return 0;
}

    //nvcc -std=c++11 -o test test.cu

1000万只袜子的运行时间：9毫秒