递归使用列表STL进行插入排序 [英] Insertion sort using a list STL recursively

问题描述

因此，我正在尝试将此向量代码修改为列表。我了解向量，但对列表来说还很陌生。到目前为止，这是我一直尝试的方法。如何解决此问题，请告诉我。
这是原始矢量代码：

So I am trying to modify this code of vectors into lists. I understand vectors but fairly new to lists. This is what I have tried so Far how can I fix this Please let me Know. Here is the original vector code:

void insertion_sort(std::vector <int> &num) {
int i, j, key;
bool insertionNeeded = false;

for (j = 1; j < num.size(); j++) {
    key = num[j];
    insertionNeeded = false;
    for (i = j - 1; i >= 0; i--) { // larger values move right

        if (key < num[i]) {
            num[i + 1] = num[i];
            insertionNeeded = true;
        }
        else
            break;
    }
    if (insertionNeeded)
        num[i + 1] = key;    //Put key into its proper location
}
}

我尝试转换为列表的代码：
运行它时出现错误

Here is the code I tried to convert to Lists: I am getting an error when I run it

void insertion_sort(list<int> &li) {
int i, j, key;
bool insertionNeeded = false;
list<int>::iterator itr = li.begin();
for (j = 1; j < li.size(); j++) {
    advance(itr, j);
    key = *itr;
    insertionNeeded = false;
    for (i = j - 1; i >= 0; i--) { // larger values move right
        advance(itr, i);

        if (key < i) {
            advance(itr, i + 1);
            int temp1 = *itr;
                 advance(itr, i);
                 int temp2 = *itr;

                 temp1 = temp2;
            insertionNeeded = true;
        }
        else
            break;
    }
    if (insertionNeeded)
        advance(itr, i + 1);
        *itr = key;
}
}

推荐答案

此是我的快速答案。
测试代码为 此处 。

This is my quick answer. The test code is here.

请注意， std :: advance 会修改其参数。
OTOH， std :: next 保留其自变量。

Note that std::advance modifies its argument. OTOH, std::next leaves its argument unmodified.

void insertion_sort(std::list<int> &li)
{
    for (auto j = 1U; j < li.size(); ++j) 
    {
        auto itr = li.begin();
        std::advance(itr, j);
        const auto key = *itr;

        for (auto i = j; i > 0U; --i) // i is just a counter.
        {        
            std::advance(itr, -1);

            if (key < *itr) // larger values move right
            {
                const int temp = *itr;
                *itr = key;
                *std::next(itr) = temp;        
            }
            else{            
                break;
            }
        }
    }
}

这篇关于递归使用列表STL进行插入排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！