问题描述

编写一个算法，在基于单链表表示的待排序关键字序列上进行简单选择排序。

算法思想

每趟在原始链表中摘下关键字最大的结点，插入结果链表的最前端。

输入

3 1 2 5 4

输出

1 2 3 4 5

CODE

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

struct Node
{
    int val;
    Node* next;
    Node(int x) : val(x), next(NULL) {}
};

void print(Node *head)
{
    auto p = head;
    while (p)
    {
        cout << p->val << ' ';
        p = p->next;
    }
    cout << endl;
}

Node* select_sort(Node* head)
{
    Node *dummy = new Node(0), *p, *q, *r, *s;

    while (head) 
    {
        s = p = head; r = q = NULL;
        // s和r记忆最大节点和其前驱，p为工作指针，q为其前驱
        while (p)
        {
            if (p->val > s->val) 
            {
                s = p;
                r = q;
            }
            q = p; p = p->next;
        }
        // 删除最大节点
        if(s == head)           
            head = head->next;
        else
            r->next = s->next;  
        // 头插法
        s->next = dummy->next;
        dummy->next = s;
    }

    return dummy->next;
}

int main()
{
    int nums[5] = {3, 1, 2, 5, 4};
    Node* dummy = new Node(0);
    auto tail = dummy;
    for (int x : nums)
    {
        auto p = new Node(x);
        tail->next = p;
        tail = tail->next;
    }

    print(dummy->next);    

    auto p = select_sort(dummy->next);
    print(p);

    return 0;
}