在單向鏈表上實現選擇排序

Question

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; 
} 

Answer 1

從你swap功能：

nodeType<Type>* temp; 
temp->info = first->info; 

這是未定義行爲明確的情況下！你聲明一個局部變量，一個指針，沒有初始化。然後你直接使用未初始化的變量，導致UB。既然你使用了指針，你應該對程序沒有崩潰感到高興。

這裏您不需要指針或節點，因爲您實際上並不交換節點。所有你需要的是一個什麼樣info是一個實例，並使用：

SomeType temp; 
temp = first->info; 
first->info = second->info; 
second->info = temp; 

Answer 2

通過@JoachimPileborg答案當然是作品，但請注意，你並不需要編寫一個成員函數自己的sort單向鏈接列表以便進行選擇排序。

的原因是，selection_sort（與O(N^2)複雜）一generic version已兼容暴露前向迭代，比如一個標準庫，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)存儲）。