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

最多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);
}

至少这是我在现实生活中使用的，我发现它非常有效。缺点是它需要一个平坦的表面，但通常很丰富。

真实世界方法：

尽快将袜子从未分类的袜子堆中取出，一次一个，然后放在前面。桩应布置得有一定的空间效率，所有袜子指向相同的方向；桩的数量受你容易到达的距离的限制。选择一堆袜子时，应尽快将袜子放在一堆看起来很像的袜子上；偶尔出现的I型（把袜子放在不属于它的袜子堆上）或II型（当有一堆类似的袜子时，把袜子放进自己的袜子堆里）错误是可以容忍的——最重要的考虑是速度。

一旦所有袜子都成了一堆，快速穿过多个袜子堆，创建成对的袜子，然后将它们取下（这些袜子朝抽屉方向）。如果袜子堆中有不匹配的袜子，请将它们重新堆到最好的位置（在尽可能快的限制范围内）。当处理完所有的多袜子堆后，将由于II类错误而未配对的剩余可配对袜子进行配对。哎呦，你完了——我有很多袜子，直到大部分都脏了才洗。另一个实际注意事项是：我将一双袜子的顶部翻转到另一双袜子上，利用它们的弹性财产，以便它们在被运送到抽屉和抽屉中时保持在一起。

你试图解决错误的问题。

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

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

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

希望这有帮助！

一种有效的袜子配对算法

前提条件

堆里必须至少有一只袜子桌子必须足够大，以容纳N/2袜子（最坏情况），其中N是总数袜子。

算法

Try:

挑选第一只袜子把它放在桌子上选择下一只袜子，然后看看它（可能会把“不再有袜子”扔到袜子堆里）现在扫描桌子上的袜子（如果桌子上没有袜子，则抛出异常）有匹配的吗？a） 是=>从桌子上取下匹配的袜子b） no=>将袜子放在桌子上（可能会抛出“桌子不够大”异常）

除了：

桌子不够大：小心地将所有未配对的袜子混合在一起，然后继续操作//此操作将导致一个新的堆和一个空表桌子上没有袜子：扔（最后一只不受欢迎的袜子）堆里没有袜子：出口洗衣房

最后：

如果袜子堆里还有袜子：转到3

已知问题

如果或周围没有表，算法将进入无限循环桌子上没有足够的地方容纳至少一只袜子。

可能的改进

根据要分拣的袜子数量，吞吐量可能是通过整理桌子上的袜子来增加空间

为了使其工作，需要一个具有唯一每双袜子的价值。这样的属性很容易根据袜子的视觉财产合成。

按所述属性对桌上的袜子进行排序。让我们调用该属性“颜色”。将袜子排成一排，并将深色袜子放在右侧（即push_back（）），左侧（即。.push_front（））

对于大量的袜子，尤其是以前看不见的袜子，属性合成可能需要很长时间，因此吞吐量将明显下降。但是，这些属性可以保存在内存中并重用。

需要进行一些研究来评估这种可能性的效率改善出现以下问题：

上述袜子的最佳搭配数量是多少改善对于给定数量的袜子，之前需要多少次迭代吞吐量增加？a） 用于最后一次迭代b） 对于所有迭代

符合MCVE指南的PoC：

#include <iostream>
#include <vector>
#include <string>
#include <time.h>

using namespace std;

struct pileOfsocks {
    pileOfsocks(int pairCount = 42) :
        elemCount(pairCount<<1) {
        srand(time(NULL));
        socks.resize(elemCount);

        vector<int> used_colors;
        vector<int> used_indices;

        auto getOne = [](vector<int>& v, int c) {
            int r;
            do {
                r = rand() % c;
            } while (find(v.begin(), v.end(), r) != v.end());
            v.push_back(r);
            return r;
        };

        for (auto i = 0; i < pairCount; i++) {
            auto sock_color = getOne(used_colors, INT_MAX);
            socks[getOne(used_indices, elemCount)] = sock_color;
            socks[getOne(used_indices, elemCount)] = sock_color;
        }
    }

    void show(const string& prompt) {
        cout << prompt << ":" << endl;
        for (auto i = 0; i < socks.size(); i++){
            cout << socks[i] << " ";
        }
        cout << endl;
    }

    void pair() {
        for (auto i = 0; i < socks.size(); i++) {
            std::vector<int>::iterator it = find(unpaired_socks.begin(), unpaired_socks.end(), socks[i]);
            if (it != unpaired_socks.end()) {
                unpaired_socks.erase(it);
                paired_socks.push_back(socks[i]);
                paired_socks.push_back(socks[i]);
            }
            else
                unpaired_socks.push_back(socks[i]);
        }

        socks = paired_socks;
        paired_socks.clear();
    }

private:
    int elemCount;
    vector<int> socks;
    vector<int> unpaired_socks;
    vector<int> paired_socks;
};

int main() {
    pileOfsocks socks;

    socks.show("unpaired socks");
    socks.pair();
    socks.show("paired socks");

    system("pause");
    return 0;
}