merage sort
Divide-and-conquer
merge sort 的核心理念是 Divide-and-conquer 仰泻，這個范式的核心是把問題分割成跟原問題相似的子問題词疼，然后，遞歸的解決這些子問題鹃操，最后把這些子問題的結論合并得到原始問題的答案坯约。Divide-and-conquer 分三步：
- Divide 把問題分割成跟原來的問題一致但是規(guī)模變小了的子問題。
- Conquer 遞歸的解決子問題。如果問題足夠小了什燕，直接解決子問題。
- Combine 把子問題的解決方案合并的到原問題的解決方案竞端。
如圖所示：
mergeSort1.png
進一步擴展成更多的遞歸步驟：
dac.png
Merge Sort
Merge Sort 采用的就是Divide-and-conquer 屎即，對于一個數(shù)組a[p....r]有以下三步：
- Divide 找到p和r的中點q;
- Conquer 遞歸的對每次生成的子數(shù)組進行排序；
- 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] 進行排序。當我們完成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ù)結構如下：
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<>();
//對輸入進行一下排序
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é)點的添加；
startMin = start;
endMax = end;
} else {
//吞掉一個節(jié)點贵扰；
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);
}
