merage sort

Divide-and-conquer

merge sort 的核心理念是 Divide-and-conquer ，這個范式的核心是把問題分割成跟原問題相似的子問題，然后，遞歸的解決這些子問題，最后把這些子問題的結(jié)論合并得到原始問題的答案。Divide-and-conquer 分三步：

1. Divide 把問題分割成跟原來的問題一致但是規(guī)模變小了的子問題。
2. Conquer 遞歸的解決子問題。如果問題足夠小了，直接解決子問題。
3. Combine 把子問題的解決方案合并的到原問題的解決方案。

如圖所示：

mergeSort1.png

進(jìn)一步擴(kuò)展成更多的遞歸步驟：


dac.png

Merge Sort

Merge Sort 采用的就是Divide-and-conquer ，對于一個數(shù)組a[p....r]有以下三步：

1. Divide 找到p和r的中點(diǎn)q;
2. Conquer 遞歸的對每次生成的子數(shù)組進(jìn)行排序；
3. Combine 把兩個排序好的子數(shù)組合并成一個排序好的數(shù)組。

舉一個具體例子：

? 對于一個數(shù)組 array[0..7] [14, 7, 3, 12, 9, 11, 6, 2] .

• 在divide 階段,我們計算出來一個中值q＝3
• 在conquer 階段，我們分別對兩個子數(shù)組array[0..3], [14, 7, 3, 12] 和 array[4..7], [9, 11, 6, 2] 進(jìn)行排序。當(dāng)我們完成conquer ，兩個數(shù)組都是有序的分別是 [3, 7, 12, 14] 和 [2, 6, 9, 11],最后我們得到完整的數(shù)組[3, 7, 12, 14, 2, 6, 9, 11]
• 最后在combine階段，我們合并(merge) 兩個數(shù)組，得到最終的有序數(shù)組[2, 3, 6, 7, 9, 11, 12, 14]

我們用圖形來演示一下這個過程：

![Uploading Merge-sort-example-300px_933644.gif . . .]

再來兩個動圖演示一下：

Merge-sort-example-300px.gif

Merge_sort_animation2.gif

Java 實現(xiàn)

public void mergeSort(int[] A, int start, int end, int[] temp) {
    if(start >= end) {
        return;
    }
    int left = start;
    int right = end;
    int mid = (start + end) / 2;
    
    mergeSort(A, start, mid, temp);
    mergeSort(A, mid + 1, end, temp);
    merge(A, start, mid, end, temp)
}

public void merge(int[] A, int start, int mid, int end, int[] temp) {
    int left = start;
    int right = mid + 1;
    int index = start;
    
    while(left <= mid && right <= end) {
        if(A[left] < A[right]) {
            temp[index++] = A[left++];
        } else {
            temp[index++] = A[right++];
        }
    }
  while(left <= mid) {
        temp[index++] = A[left++];
  } 
  while (right <= end) {
        temp[index++] = A[right++];
  }
  for(index = start; index <= end; index++) {
        A[index] = temp[index];
  }
}

LeetCode 衍生問題

算法前面說的比較清楚，直接說兩個比較難的問題：

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {val = x;}
}

解法1:

ListNode dummy = new ListNode(0);

public ListNode mergeKLists(ListNode[] list) {
    if(lists.length == 0) return null;
    int i = 0;
    int j = lists.length - 1;
    while( j != 0 ) {
        while(i < j) {
            lists[i] = mergeTwo(lists[i++], lists[j--]); 
        }
        i = 0;
    }
    return lists[0];
}

public ListNode mergeTwo(ListNode node1, ListNode node2) {
    ListNode head = dummy;
    while(node1 != null && node2 != null) {
        if(node1.val < node2.val) {
            head.next = node1;
            node1 = node1.next;
        }
        head = head.next;
    }
  if(node1 != null) {
        head.next = node1;
  }
  if(node2 != null) {
        head.next = node2;
  }
  return dummy.next;
}

解法2,我們借助java的優(yōu)先級隊列(PriorityQueue)來解這個問題:

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });

        for(ListNode n : lists) {
            if(n != null) {
                heap.add(n);
            }
        }

        ListNode head = heap.peek();
        while(!heap.isEmpty()) {
            ListNode min = heap.poll();
            if (min.next != null) {
                heap.add(min.next);
            }
            min.next = heap.peek();
        }
        return head;
    }

優(yōu)先級隊列實現(xiàn)了一種通過堆排序來解決問題的方案。

第二個問題 Merge Intervals:

Given a collection of intervals, merge all overlapping intervals.

For example,

Given [1,3],[2,6],[8,10],[15,18],

return [1,6],[8,10],[15,18].

數(shù)據(jù)結(jié)構(gòu)如下：

 public class Interval {
        int start;
        int end;

        Interval() {start = 0; end = 0;}
        Interval(int s, int e) {start = s; end = e;}
    };

解法1:

 public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <=1 ) return intervals;
        List<Interval> merged = new ArrayList<>();

        //對輸入進(jìn)行一下排序
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if(o1.start != o2.start) {
                    return o1.start - o2.start;
                }
                return o1.end - o2.end;
            }
        });

        int startMin = intervals.get(0).start;
        int endMax = intervals.get(0).end;

        for (int i = 1; i < intervals.size(); i++) {
            int start = intervals.get(i).start;
            int end = intervals.get(i).end;

            if (start > endMax) {
                merged.add(new Interval(startMin, endMax));
                //完成一個節(jié)點(diǎn)的添加；
                startMin = start;
                endMax = end;
            } else {
                //吞掉一個節(jié)點(diǎn)；
                endMax = Math.max(end, endMax);
            }
        }
        merged.add(new Interval(startMin, endMax));
        return merged;
    }

解法2（原地排序，空間占用率低）:

public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() < 2) {
            return intervals;
        }
        intervals.sort(new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        });
        int length = 1;
        for(int i = 1; i < intervals.size(); i++) {
            if(intervals.get(length - 1).end < intervals.get(i).start) {
                intervals.set(length++, intervals.get(i));
            } else {
                intervals.get(length - 1).end = Math.max(intervals.get(length - 1).end, intervals.get(i).end);
            }
        }
        return intervals.subList(0, length);
    }