鏈表排序（冒泡、選擇、插入、快排、歸并、希爾、堆排序）

參考http://www.cnblogs.com/TenosDoIt/p/3666585.html

插入排序（算法中是直接交換節點，時間復雜度O（n^2）,空間復雜度O（1））

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(head == NULL || head->next == NULL)return head;
        ListNode *p = head->next, *pstart = new ListNode(0), *pend = head;
        pstart->next = head; //為了操作方便，添加一個頭結點
        while(p != NULL)
        {
            ListNode *tmp = pstart->next, *pre = pstart;
            while(tmp != p && p->val >= tmp->val) //找到插入位置
                {tmp = tmp->next; pre = pre->next;}
            if(tmp == p)pend = p;
            else
            {
                pend->next = p->next;
                p->next = tmp;
                pre->next = p;
            }
            p = pend->next;
        }
        head = pstart->next;
        delete pstart;
        return head;
    }
};

?

---

選擇排序（算法中只是交換節點的val值，時間復雜度O（n^2）,空間復雜度O（1））

class Solution {
public:
    ListNode *selectSortList(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        //選擇排序
        if(head == NULL || head->next == NULL)return head;
        ListNode *pstart = new ListNode(0);
        pstart->next = head; //為了操作方便，添加一個頭結點
        ListNode*sortedTail = pstart;//指向已排好序的部分的尾部
        
        while(sortedTail->next != NULL)
        {
            ListNode*minNode = sortedTail->next, *p = sortedTail->next->next;
            //尋找未排序部分的最小節點
            while(p != NULL)
            {
                if(p->val < minNode->val)
                    minNode = p;
                p = p->next;
            }
            swap(minNode->val, sortedTail->next->val);
            sortedTail = sortedTail->next;
        }
        
        head = pstart->next;
        delete pstart;
        return head;
    }
};

?

---

快速排序1（算法只交換節點的val值，平均時間復雜度O（nlogn）,不考慮遞歸棧空間的話空間復雜度是O（1））

這里的partition我們參考數組快排partition的第二種寫法(選取第一個元素作為樞紐元的版本，因為鏈表選擇最后一元素需要遍歷一遍)，具體可以參考here

這里我們還需要注意的一點是數組的partition兩個參數分別代表數組的起始位置，兩邊都是閉區間，這樣在排序的主函數中：

void?quicksort(vector<int>&arr,?int?low,?int?high)

{

? if(low < high)

? {

?? int?middle = mypartition(arr, low, high);

?? quicksort(arr, low, middle-1);

?? quicksort(arr, middle+1, high);

? }

}

對左邊子數組排序時，子數組右邊界是middle-1，如果鏈表也按這種兩邊都是閉區間的話，找到分割后樞紐元middle，找到middle-1還得再次遍歷數組，因此鏈表的partition采用前閉后開的區間（這樣排序主函數也需要前閉后開區間），這樣就可以避免上述問題

?

class Solution {
public:
    ListNode *quickSortList(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        //鏈表快速排序
        if(head == NULL || head->next == NULL)return head;
        qsortList(head, NULL);
        return head;
    }
    void qsortList(ListNode*head, ListNode*tail)
    {
        //鏈表范圍是[low, high)
        if(head != tail && head->next != tail)
        {
            ListNode* mid = partitionList(head, tail);
            qsortList(head, mid);
            qsortList(mid->next, tail);
        }
    }
    ListNode* partitionList(ListNode*low, ListNode*high)
    {
        //鏈表范圍是[low, high)
        int key = low->val;
        ListNode* loc = low;
        for(ListNode*i = low->next; i != high; i = i->next)
            if(i->val < key)
            {
                loc = loc->next;
                swap(i->val, loc->val);
            }
        swap(loc->val, low->val);
        return loc;
    }
};

?

快速排序2（算法交換鏈表節點，平均時間復雜度O（nlogn）,不考慮遞歸棧空間的話空間復雜度是O（1））

這里的partition，我們選取第一個節點作為樞紐元，然后把小于樞紐的節點放到一個鏈中，把不小于樞紐的及節點放到另一個鏈中，最后把兩條鏈以及樞紐連接成一條鏈。

這里我們需要注意的是，1.在對一條子鏈進行partition時，由于節點的順序都打亂了，所以得保正重新組合成一條新鏈表時，要和該子鏈表的前后部分連接起來，因此我們的partition傳入三個參數，除了子鏈表的范圍（也是前閉后開區間），還要傳入子鏈表頭結點的前驅；2.partition后鏈表的頭結點可能已經改變

class Solution {
public:ListNode *quickSortList(ListNode *head) {// IMPORTANT: Please reset any member data you declared, as// the same Solution instance will be reused for each test case.//鏈表快速排序if(head == NULL || head->next == NULL)return head;ListNode tmpHead(0); tmpHead.next = head;qsortList(&tmpHead, head, NULL);return tmpHead.next;}void qsortList(ListNode *headPre, ListNode*head, ListNode*tail){//鏈表范圍是[low, high)if(head != tail && head->next != tail){ListNode* mid = partitionList(headPre, head, tail);//注意這里head可能不再指向鏈表頭了qsortList(headPre, headPre->next, mid);qsortList(mid, mid->next, tail);}}ListNode* partitionList(ListNode* lowPre, ListNode* low, ListNode* high){//鏈表范圍是[low, high)int key = low->val;ListNode node1(0), node2(0);//比key小的鏈的頭結點，比key大的鏈的頭結點ListNode* little = &node1, *big = &node2;for(ListNode*i = low->next; i != high; i = i->next)if(i->val < key){little->next = i;little = i;}else{big->next = i;big = i;}big->next = high;//保證子鏈表[low,high)和后面的部分連接little->next = low;low->next = node2.next;lowPre->next = node1.next;//為了保證子鏈表[low,high)和前面的部分連接return low;}
};

?

?

---

歸并排序（算法交換鏈表節點，時間復雜度O（nlogn）,不考慮遞歸棧空間的話空間復雜度是O（1））????????????????????????本文地址

首先用快慢指針的方法找到鏈表中間節點，然后遞歸的對兩個子鏈表排序，把兩個排好序的子鏈表合并成一條有序的鏈表。歸并排序應該算是鏈表排序最佳的選擇了，保證了最好和最壞時間復雜度都是nlogn，而且它在數組排序中廣受詬病的空間復雜度在鏈表排序中也從O(n)降到了O(1)

class Solution {
public:ListNode *mergeSortList(ListNode *head) {// IMPORTANT: Please reset any member data you declared, as// the same Solution instance will be reused for each test case.//鏈表歸并排序if(head == NULL || head->next == NULL)return head;else{//快慢指針找到中間節點ListNode *fast = head,*slow = head;while(fast->next != NULL && fast->next->next != NULL){fast = fast->next->next;slow = slow->next;}fast = slow;slow = slow->next;fast->next = NULL;fast = sortList(head);//前半段排序slow = sortList(slow);//后半段排序return merge(fast,slow);}}// merge two sorted list to oneListNode *merge(ListNode *head1, ListNode *head2){if(head1 == NULL)return head2;if(head2 == NULL)return head1;ListNode *res , *p ;if(head1->val < head2->val){res = head1; head1 = head1->next;}else{res = head2; head2 = head2->next;}p = res;while(head1 != NULL && head2 != NULL){if(head1->val < head2->val){p->next = head1;head1 = head1->next;}else{p->next = head2;head2 = head2->next;}p = p->next;}if(head1 != NULL)p->next = head1;else if(head2 != NULL)p->next = head2;return res;}
};

?

?

---

冒泡排序（算法交換鏈表節點val值，時間復雜度O（n^2）,空間復雜度O（1））

class Solution {
public:ListNode *bubbleSortList(ListNode *head) {// IMPORTANT: Please reset any member data you declared, as// the same Solution instance will be reused for each test case.//鏈表快速排序if(head == NULL || head->next == NULL)return head;ListNode *p = NULL;bool isChange = true;while(p != head->next && isChange){ListNode *q = head;isChange = false;//標志當前這一輪中又沒有發生元素交換，如果沒有則表示數組已經有序for(; q->next && q->next != p; q = q->next){if(q->val > q->next->val){swap(q->val, q->next->val);isChange = true;}}p = q;}return head;}
};

?