#include <iostream>

using namespace std;

//别问我为什么要写链表的冒泡排序。

struct Node

{

    int data;

    Node *next;

    Node(int d = int()) :data(d), next(NULL){}

};

class List

{

public:

    List(int a[], int n)

    {

        first = NULL;

        for (int i = 0; i < n; i++)

        {

            if (first == NULL)

            {

                first = new Node(a[i]);

            }

            else

            {

                Node *s = new Node(a[i]);

                Node *p = first;

                while (p->next != NULL)

                {

                    p = p->next;

                }

                s->next = p->next;

                p->next = s;

            }

        }

    }

    //////////////////////////////////////////////////////////////////////////////

    //冒泡排序

    void Bul()

    {

        Node *ptr_one = first;

        Node *ptr_twe;

        Node *pr_one = NULL;

        Node *save = NULL;

        if (ptr_one == NULL || ptr_one->next == NULL)return;

        while (ptr_one != NULL && ptr_one->next != NULL)

        {

            Node *pr_twe = ptr_one;

            Node *m2 = NULL;

            save = ptr_one;

            for (ptr_twe = ptr_one->next; ptr_twe != NULL;)

            {

                if (ptr_one->data > ptr_twe->data)

                {

                    if (pr_one == NULL)

                    {

                        Node *m1;

                        Node *a;

                        m1 = ptr_twe->next;

                        m2 = ptr_one->next;

                        first->next = m1;

                        pr_twe->next = first;

                        a = first;

                        ptr_twe->next = m2;

                        first = ptr_twe;

                        save = ptr_twe;

                        ptr_twe = a;

                        ptr_one = first;

                    }

                    else

                    {

                        Swap(pr_one, pr_twe);

                        save = pr_one->next;

                        ptr_one = save;

                        ptr_twe = pr_twe->next;

                    }

                }

                pr_twe = ptr_twe;

                if (ptr_twe == NULL)continue;

                ptr_twe = ptr_twe->next;

            }

            pr_one = save;

            ptr_one = pr_one->next;

        }

    }

    void Swap(Node *prv1, Node *&prv2)

    {

        if (prv1->next == prv2)

        {

            Node *m = prv1->next;

            Node *n = prv2->next;

            m->next = n->next;

            n->next = m;

            prv1->next = n;

            prv2 = n;

        }

        else

        {

            Node *m1 = prv1->next;

            Node *save = m1->next;

            Node *m2 = prv2->next;

            m1->next = m2->next;

            prv2->next = m1;

            m2->next = save;

            prv1->next = m2;

        }

    }

    void Printf()

    {

        Node *p = first;

        while (p != NULL)

        {

            cout << p->data << "   ";

            p = p->next;

        }

        cout << endl;

    }

    //////////////////////////////////////////////////////////////////////////////////////

    //2路归并排序。

    Node *GetMidNode(Node* Start_Ptr)

    {

        Node *slow = Start_Ptr;

        Node *fast = Start_Ptr;

        if (Start_Ptr == NULL || Start_Ptr->next == NULL || Start_Ptr->next->next==NULL)return Start_Ptr;

        while (fast != NULL)

        {

            if (fast->next == NULL)

            {

                break;

            }

            fast = fast->next->next;

            slow = slow->next;

        }

        return slow;

    }

    void Merge()

    {

        Merge(first);

    }

    Node* Merge(Node *Start_Ptr)

    {

        if (Start_Ptr==NULL || Start_Ptr->next == NULL) return Start_Ptr;

        else

        {

            Node *Mid_Ptr = GetMidNode(Start_Ptr);

            Node *Next_Ptr = Mid_Ptr->next;

            Mid_Ptr->next = NULL;

            return Merage(Merge(Start_Ptr),Merge(Next_Ptr));

        }

    }

    Node* Merage(Node *ptr1, Node *ptr2)

    {

        Node* p1 = ptr1;

        Node *p2 = ptr2;

        Node *p = new Node();

        Node *save = p;

        while (p1 != NULL && p2 != NULL)

        {

            if (p1->data > p2->data)

            {

                p->next=p2;

                p = p2;

                p2 = p2->next;

            }

            else

            {

                p->next = p1;

                p = p1;

                p1 = p1->next;

            }

        }

        if (p1 == NULL)

        {

            p->next = p2;

        }

        if (p2 == NULL)

        {

            p->next = p1;

        }

        first = save->next;

        delete save;

        save = NULL;

        return first;

    }

    //////////////////////////////////////////////////////////////////////////////////////////

    //插入排序。

    void Insert()

    {

        Node *ptr_first = first;

        Node *pr_first;

        Node *ptr_twe;

        Node *pr_twe;

        Node *save;

            for (; ptr_first != NULL;pr_first = ptr_first)

            {

                save = ptr_first->next;

                if (ptr_first == first)

                {

                    ptr_twe = ptr_first;

                    ptr_twe->next = NULL;

                    first = ptr_twe;

                }

                else

                {

                    Node *p = ptr_twe;

                    Node *q = ptr_first;

                    while (p!=NULL&&p->data<q->data)

                    {

                        pr_twe = p;

                        p = p->next;

                    }

                    if (p == first)

                    {

                        //假设是第一个节点插入。

                        q->next = p;

                        ptr_twe = q;

                        first = ptr_twe;

                    }

                    else if(p == NULL)

                    {

                        pr_twe->next = q;

                        q->next = NULL;

                    }

                    else

                    {

                        q->next = pr_twe->next;

                        pr_twe->next = q;

                    }

                }

                ptr_first = save;

            }

    }

private:

    Node *first;

};

int main()

{

    int a[] = { 6,7,2,1,0,7,5,23,4,5,423,4,100,-32,4,-3,1};

    List list(a, sizeof(a) / sizeof(int));

    //list.Merge();

    //list.Bul();

    list.Insert();

    list.Printf();

    return 0;

}