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

袜子，无论是真的还是类似的数据结构，都将成对提供。

最简单的答案是，在允许袜子对分开之前，应该初始化袜子对的单个数据结构，该结构包含指向左右袜子的指针，从而可以直接或通过袜子对引用袜子。袜子也可以扩展为包含指向其伙伴的指针。

这通过使用抽象层来消除任何计算配对问题。

将同样的想法应用于袜子配对的实际问题，显而易见的答案是：不要让你的袜子不配对。袜子是一双提供的，一双放在抽屉里（也许是把它们捆在一起），一双穿。但可能脱漆的地方是在洗衣机里，所以所需要的只是一个物理机制，让袜子保持在一起并有效地清洗。

有两种物理可能性：

对于一个“pair”对象，它保持指向每只袜子的指针，我们可以使用一个布袋来将袜子放在一起。这似乎是巨大的开销。

但是，为了让每一只袜子都能互相参照，有一个很好的解决方案：一个popper（如果你是美国人，可以使用“按扣”），比如：

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

然后，你所做的就是在脱下袜子并将其放进洗衣篮后立即将袜子扣在一起，再次消除了需要用“配对”概念的物理抽象来对袜子进行配对的问题。

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

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

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

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

拿起第一只袜子放在桌子上。现在再挑一只袜子；如果它与第一个拾取的匹配，请将其放在第一个拾取上。如果没有，把它放在桌子上，离第一个小距离。挑选第三只袜子；如果它与前两个匹配，请将它放在它们的上面，或者将它放置在距离第三个的一小段距离处。重复上述步骤，直到你捡起所有袜子。

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

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

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

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

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

一种有效的袜子配对算法

前提条件

堆里必须至少有一只袜子桌子必须足够大，以容纳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;
}