排序算法---链表排序

前言

　　链表排序思想和数组排序类似，区别就是数组遍历容易，数据交换也容易；链表(单项链表)只能一个方向遍历，不能逆序遍历(也可以先反转在遍历)，且不能随机访问，所以排序比较麻烦，同时链表的数据交换也很麻烦，如果交换两个节点，需要共涉及3个节点，无形中增加了复杂度，也可以直接交换节点中的数据，这种方式相对简单。

　　如下列出了几种相对比较好简单也好理解的链表排序算法，代码如下：

#include <iostream>

using namespace std;

struct Node
{
    struct Node *next;
    int data;
};

Node *createNode(int x)
{
    Node *p = NULL;
    
    p = new Node;
    p->next = NULL;
    p->data = x;
    
    return p;
}

void addNode(Node **head, Node *p)
{
    Node *temp = NULL;
    if(*head == NULL)
    {
        *head = p;
    }
    else
    {
        temp = *head;
        while(temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = p;
    }
}

void showList(Node *head)
{
    while(head != NULL)
    {
        cout << head->data << "  ";
        head = head->next;
    }
    cout << endl;
}

void swap(int& a, int& b)
{
    int tmp = b;
    b = a;
    a = tmp;
}

// 1. 直接选择排序   ------直接交换数据
void ListSort_1(Node **head)
{
    Node *p = NULL;
    Node *q = NULL;
    Node *t = NULL;
    
    if(*head == NULL || (*head)->next == NULL)
    {
        return;
    }

    for(p = *head; p != NULL; p = p->next)
    {
        t = p;
        
        for(q = p->next; q != NULL; q = q->next)
        {
            if(q->data < t->data)
            {
                t = q;
            }
        }
        
        if(t != p)
        {
            swap(p->data, t->data);
        }
    }
    
    return;
}

// 2. 冒泡排序     ------直接交换数据
void ListSort_2(Node **head)
{
    Node *p = NULL;
    Node *q = NULL;
    Node *t = NULL;
    
    if(*head == NULL || (*head)->next == NULL)
    {
        return;
    }

    for(p = *head; p != NULL; p = p->next)
    {
        for(q = *head; q->next != NULL; q = q->next)
        {
            if(q->data > q->next->data)
            {
                swap(q->data, q->next->data);
            }
        }
        
    }
}

// 3. 插入排序
void ListSort_3(Node **head)
{
    //直接插入排序涉及到链表的反向遍历，比较麻烦，不建议
}

Node *merge(Node *left, Node *right)
{
    Node *head = createNode(-1);  // 小技巧
    Node *temp = head;
    
    while(left != NULL && right != NULL)
    {
        if(left->data < right->data)
        {
            temp->next = left;
            temp = temp->next;
            left = left->next;
        }
        else
        {
            temp->next = right;
            temp = temp->next;
            right = right->next;
        }
    }
    
    if(left != NULL)
    {
        temp->next = left;
    }
    
    if(right != NULL)
    {
        temp->next = right;
    }
    
    return head->next;
}

Node *_ListSort_4(Node *head)
{
    Node *pFast = NULL;
    Node *pSlow = NULL;
    Node *mid = NULL;
    
    if(head == NULL || head->next == NULL)
    {
        return head;
    }
    
    pFast = head;
    pSlow = head;
    
    while(pFast->next != NULL && pFast->next->next != NULL)
    {
        pFast = pFast->next->next;
        pSlow = pSlow->next;
    }
    
    mid = pSlow->next;
    pSlow->next = NULL;
    
    return merge(_ListSort_4(head), _ListSort_4(mid));
}

// 4. 归并排序      ------交换节点
void ListSort_4(Node **head)
{
    Node *temp = *head;
    *head = _ListSort_4(temp);
}

int main()
{
    Node *head = NULL;
    
    addNode(&head, createNode(2));
    addNode(&head, createNode(5));
    addNode(&head, createNode(7));
    addNode(&head, createNode(4));
    addNode(&head, createNode(6));
    addNode(&head, createNode(3));
    addNode(&head, createNode(1));
    addNode(&head, createNode(9));
    addNode(&head, createNode(8));

    cout << "Sort Before:" << endl;
    showList(head);
    
    //ListSort_1(&head);
    //ListSort_2(&head);
    ListSort_4(&head);
    
    cout << "Sort After:" << endl;
    showList(head);211 
    while(1);
    return 0;
}