在单个链接列表上实现选择排序-Java 学习之路

Heya我正在尝试在单链表上实现选择排序算法，我知道代码中存在一些问题但是虽然我的链表包含数字7 1 2 6，但运行后的输出是7777 . 任何帮助，将不胜感激 .

template<class Type>
void UnOrderedLinkedList<Type>::selectionSort()
{
nodeType<Type>* loc;
nodeType<Type>* minIndex;
nodeType<Type>* temp;
temp = first;
if(temp == NULL)
    cerr<<"Cannot sort an empty list."<<endl;
else
    if(temp->link == NULL)
    cerr<<"List has only one item so it is already sorted."<<endl;
else

while(temp != NULL)
{
    minIndex = minLocation(temp, last);
    swap(temp, minIndex);
    temp = temp->link;
}
}


template<class Type>
nodeType<Type>* UnOrderedLinkedList<Type>::minLocation(nodeType<Type>* first, nodeType<Type>* last)

nodeType<Type>* minIndex;
nodeType<Type>* other;

minIndex = first;
other = minIndex->link;

while(other != NULL)
{
    if(minIndex->info > other->info)
    {
        minIndex = other;
        other = other->link;
    }

    else
    {
        other = other->link;
    }

}
    return minIndex;
}

然后交换：

template<class Type>
void UnOrderedLinkedList<Type>::swap(nodeType<Type>* first, nodeType<Type>* second)
{
     nodeType<Type>* temp;
     temp->info = first->info;
     first->info = second->info;
     second->info = temp->info;
}

2 回答

1
从 swap 函数：
```
nodeType<Type>* temp;
 temp->info = first->info;
```
这是未定义行为的明显案例！你声明一个局部变量，一个指针，没有初始化 . 然后你直接使用未初始化的变量，导致所述UB . 既然你使用指针，你应该很高兴程序没有崩溃 .

在这里，你实际上不需要交换节点 . 您所需要的只是 info 的实例，并使用：
```
SomeType temp;
temp = first->info;
first->info = second->info;
second->info = temp;
```
回复于 2024-05-02T07:48:30+08:00

@JoachimPileborg的答案当然有效，但请注意，您不需要编写自己的单链表的成员函数 sort 来进行选择排序 .

原因是generic version（具有 O(N^2) 复杂性）已经兼容任何暴露 forward iterators 的单链表，例如标准库中的那个， std::forward_list ：

#include <algorithm>    // min_element, iter_swap, is_sorted
#include <cassert>      // assert
#include <forward_list> // forward_list
#include <functional>   // less
#include <iostream>     // cout
#include <ios>          // boolalpha
#include <iterator>     // distance, next

template<class FwdIt, class Compare = std::less<>>
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const selection = std::min_element(it, last, cmp);
        std::iter_swap(selection, it); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

int main()
{
    auto fl = std::forward_list<int> { 2, 4, 1, 0, -1, 8, 2 };
    std::cout << std::boolalpha << std::is_sorted(fl.begin(), fl.end()) << '\n';
    for (auto const& e : fl) std::cout << e << ", "; std::cout << '\n';
    selection_sort(fl.begin(), fl.end());
    std::cout << std::boolalpha << std::is_sorted(fl.begin(), fl.end()) << '\n';
    for (auto const& e : fl) std::cout << e << ", "; std::cout << '\n';
}

Live Example

注意 std::forward_list 也实现了自己的成员函数 sort . 这个版本 - 它进行 O(N log N) 合并排序 - 无法单独基于公共接口实现（实际上你可以使用 O(N) 额外的存储而不是 forward_list 保证的 O(1) 存储） .

回复于 2024-05-02T07:48:30+08:00

在单个链接列表上实现选择排序

2 回答

相关问题