实现链接列表的选择排序 [英] Implementing Selection Sort for Linked Lists

问题描述

我想实现一个选择排序算法，将使用链接列表，并将使用迭代器来通过它们。选择排序算法如下：对于列表中除最后一个元素以外的每个元素（我们称为 K ），它将从我们的位置找出最小的当前打开（因此它将从K开始直到最后一个元素）。之后它会交换K和最小的元素。

I am trying to implement a selection sort algorithm that will work with linked lists and will use iterators to scrool through them. The selection sort algorithm is the following: for each element of the list except the last one(let's call it K), it will seek out the smallest on from the position we are currently on(so it will start from K until the last element). After that it will swap K and the smallest element.

我认为我的错误是在第一个for循环;我非常不确定 - a.end（）是前一个元素。我得到一些输出，虽然它是错误的。

I think that my mistake is in the first for loop; I am very unsure that --a.end() is the pre-last element. I get some output, though it is wrong.

#include <iostream>
#include <list>

using namespace std;

void sort_list(list<int>& a)
{
    //from the first until the pre-last element
    for(list<int> :: iterator itr = a.begin(); itr != (--a.end()); ++itr)
    {
            int smallest = *itr;

        //get smallest element after current index
         list<int> :: iterator itr2 =itr;
          ++itr2;
    for(; itr2 != a.end(); ++itr2)
        {
                if (smallest > *itr2)
                   {
                       smallest = *itr2;
                   } 
        }
        //swap smallest and current index
        int tmp = *itr;
        *itr = smallest;
        smallest = tmp;
    }
}

int main()
{
    //create a list and some elements
    list<int> listi;
    listi.push_back(5);
    listi.push_back(4);
    listi.push_back(3);
    listi.push_back(2);
    listi.push_back(1);

    // sort the list
    sort_list(listi);
    //print all of the elements
    for(list<int> :: iterator itr = listi.begin(); itr != listi.end(); ++itr)
    {
            cout << *itr << endl;
    }

    return 0;
}

推荐答案

$ c> itr2 = ++ itr 您还可以更改 itr 的值，因此您应该执行类似

When you do itr2 = ++itr you also change the value of itr, so instead you should do something like

list<int> :: iterator itr2 = itr;
for(++itr2; itr2 != a.end(); ++itr2) {
    ...
}

此外，你必须保留一个指针指向最小的元素，如果你想以后交换，如下：

Furthermore, you have to keep a pointer to the smallest element, if you want to swap it later, like this:

 int* smallest = &(*itr);

这还需要一些其他更改，您可以找到一个工作示例代码此处。

This also requires some other changes, you can find a working example of your code here.

这篇关于实现链接列表的选择排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！