C++单链表选择排序

#include <iostream>

struct Node {

int value;

Node *next;

Node(int data) : value(data), next(nullptr) {};

};

Node * ListSelectSort(Node * head);

Node * getSmallestNode(Node * head);

void print(Node * head);

int main()

{

Node n1(15);

Node n2(3);

Node n3(8);

Node n4(11);

Node n5(2);

Node n6(1);

n1.next = &n2;

n2.next = &n3;

n3.next = &n4;

n4.next = &n5;

n5.next = &n6;

print(ListSelectSort(&n1));

system("pause");

return 0;

}

Node * ListSelectSort(Node * head)

{

Node * tail = nullptr;

Node * cur = head;

Node * smallpre = nullptr;

Node * small = nullptr;

while (cur != nullptr)

{

small = cur;

smallpre = getSmallestNode(cur);

if (smallpre != nullptr)

{

small = smallpre->next;

smallpre->next = small->next;

}

cur = cur == small ? cur->next : cur;

if (tail == nullptr)

{

head = small;

}

else

{

tail->next = small;

}

tail = small;

}

return head;

}

Node * getSmallestNode(Node * head)

{

Node * smallpre = nullptr;

Node * pre = head;

Node * small = head;

Node * cur = head->next;

while (cur != nullptr)

{

if (cur->value < small->value)

{

smallpre = pre;

small = cur;

}

pre = cur;

cur = cur->next;

}

return smallpre;

}

void print(Node * head)

{

while (head != nullptr)

{

std::cout << head->value << std::endl;

head = head->next;

}

}