LeetCode刷題筆記——排序（插入排序、歸并排序、桶排序）

1. 插入排序（連結清單）

來源：147題

使用插入排序的方法對連結清單進行排序，其時間複雜度是 O ( n 2 ) O(n^2) O(n2)， n n n是連結清單的長度：

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }
        //建立啞節點 dummyHead
        //引入啞節點是為了便于在 head 節點之前插入節點。
        
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
		//維護 lastSorted 為連結清單的已排序部分的最後一個節點
		//維護 curr 為待插入的元素
		//
        ListNode lastSorted = head, curr = head.next;
        while (curr != null) {
            if (lastSorted.val <= curr.val) {
                lastSorted = lastSorted.next;
            } else {
                ListNode prev = dummyHead;
                while (prev.next.val <= curr.val) {
                    prev = prev.next;
                }
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next;
        }
        return dummyHead.next;
    }
}
           

2. 歸并排序（連結清單）

來源：147題

時間複雜度是 O ( n log ⁡ n ) O(n \log n) O(nlogn) 的排序算法：歸并排序、堆排序和快速排序（快速排序的最差時間複雜度是 O ( n 2 ) O(n^2) O(n2)）：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return sort(head,null);
    }

    public ListNode sort(ListNode head, ListNode tail){
    	//遞歸的終止條件是連結清單的節點個數小于或等于 11
    	//即當連結清單為空或者連結清單隻包含 11 個節點時，不需要對連結清單進行拆分和排序
        if(head==null)return head;
        if(head.next == tail){
            head.next = null;
            return head;
        }
		//尋找連結清單的中點可以使用快慢指針的做法：快指針每次移動 2 步，慢指針每次移動 1 步
		//當快指針到達連結清單末尾時，慢指針指向的連結清單節點即為連結清單的中點。
        ListNode slow = head, fast = head;
        while(fast!=tail){
            slow = slow.next;
            fast = fast.next;
            if(fast!=tail) fast = fast.next;
        }
        ListNode mid = slow;
        ListNode list1 = sort(head, mid);
        ListNode list2 = sort(mid, tail);
        ListNode merge = merge(list1, list2);

        return merge;
    }

    public ListNode merge(ListNode head1, ListNode head2){
        ListNode dummyNode = new ListNode(0);
        ListNode tmp = dummyNode, tmp1 = head1, tmp2 = head2;

        while(tmp1!=null && tmp2!=null){
            if(tmp1.val<=tmp2.val){
                tmp.next = tmp1;
                tmp1 = tmp1.next;
            }else{
                tmp.next = tmp2;
                tmp2 = tmp2.next;
            }
            tmp = tmp.next;
        }
        if(tmp1!=null){
            tmp.next = tmp1;
        }else if(tmp2!=null){
            tmp.next = tmp2;
        }
        return dummyNode.next;
    }
}