接下來準備學習一下歸并排序
去別的blog看了一段，很多博客概括介紹歸并的時候是這樣子的：
基本理念:分治思想（divide and conquer）
主要用處:將兩個(或者多個 兩個就稱為<u>二路歸并</u>)已經排好序的序列合并排序
時間復雜度： O(n logn)
可以看出來這也是我們遇到的第三個n logn時間復雜度的排序了
歸并排序
基本思想：
以二路歸并為例子
其實說白了只有一句話
先分割再合并
- 給定一個數(shù)組array[n]
- 選取一個中間位置mid吧(只是一個標志,不要太care,注意inside，not outside) 需要排序的開始位置start，需要排序的結束位置end
需要有end和start的原因是因為，萬一我們只需要對array的[start,end]進行排序呢？
plus 至于是左閉右開還是都是閉，看你的end的取值咯，只要對應就好
另外(** start>mid>end**)
- 那么我們是不是就需要將array[start,mid]
姑且稱之為array1和array[mid+1,end]姑且稱之為array2兩個數(shù)組排序后進行合并？ - 那么
3.提到的那兩個數(shù)組是不是按照剛才說的是將其排好序后才能merge(歸并)在一起？那么問題來了，這兩個數(shù)組要排序？ - 那么這個兩個數(shù)組（array1和array2）自己的問題就是需要排序
那么是不是還要對于每個數(shù)組按照剛才2.的步驟來一遍？
遞歸 boom 問題解決了，那么還有一個問題，眾所周知，遞歸除了將步驟跳到前面做重復的工作(代碼中就是調用相同的函數(shù)) 還需要有一個臨界值，也就是什么時候表示我們不遞歸了？ 直到遞歸到后面拆分的array數(shù)組的元素只有一個，是不是就開始回溯了？
over 大致思路就是這樣
下面看示例圖：注意不同顏色的箭頭，首先是分(藍色箭頭一層層分下去)然后是治(綠色箭頭一層層合并排序)
關注細節(jié)：
-
如何將兩個已經排好序的數(shù)組(比如是
array1和array2)合并成為一個數(shù)組呢？
思路很簡單，反正二者都是已經排好序的了，先確定一個臨時數(shù)組temp
(確保足夠長，要滿足 temp.length >= array1.length + array2.length)
然后就一個一個比較(假設是從小到大排序)，假設i，j=0；
那么就是
①如果array1[i]>array2[j] 那么temp[k]=array1[i]; k++; i++; 否則temp[k] = array2[j]; k++; j++;
②然后接下來接著做①直到其中一個數(shù)組已經走到底了，那么就只需要
那么接下來就是將沒走到底的全接了temp后面
package mergeSort;
import java.util.Arrays;
/**
* @author mengf
* 將兩個有序的數(shù)組合并為一個有序的數(shù)組的示例
* 默認兩個數(shù)組的排序從小到大
*/
public class Demo1 {
public static void main(String[] args) {
int[] array = merge(new int[] { 1, 3, 5, 7, 11 },
new int[] { 2, 4, 6, 8, 10, 12, 14, 15 });
System.out.println(Arrays.toString(array));
}
public static int[] merge(int[] array1, int[] array2) {
// i是array1的索引
// j是array2的索引
// k是新數(shù)組result的索引
int i = 0, j = 0, k = 0;
int length1 = array1.length;
int length2 = array2.length;
int[] result = new int[length1 + length2];
while (i < length1 && j < length2) {
// if (array1[i]<array2[j]) {
// result[k] = array1[i];
// i++;
// }else {
// result[k] = array2[j];
// j++;
// }
// k++;
// 上面注釋掉的這段代碼可以用一下一句來表示
// 第一次發(fā)現(xiàn)三目運算符是如此的清爽
result[k++] = array1[i] < array2[j] ? array1[i++] : array2[j++];
}
if (i < length1) {
while (i < length1) {
result[k++] = array1[i++];
}
} else if (j < length2) {
while (j < length2) {
result[k++] = array2[j++];
}
}
return result;
}
}
然后解決了思路的拆分問題(遞歸)，也解決了將拼起來的兩個有序數(shù)組merge起來的問題，那么這個算法應該是沒有問題的了！
接下來我們開始上代碼！
package mergeSort;
import java.util.Arrays;
public class MergeSort {
/**
* 默認size是10 可以自行設定 擴容 一般設置為size是需要排序的數(shù)組的長度就好了
*/
private static int temp[] = new int[10];
public static void setBufferSize(int length) {
temp = new int[length];
}
public static void main(String[] args) {
int array[] = new int[]{
10,9,8,7,6,5,4,3,2,1,0,-1,-10,-13,24
};
setBufferSize(array.length);
//閉區(qū)間 所以length-1
mergeSort(array, 0, array.length-1);
System.out.println(Arrays.toString(array));
}
public static void mergeSort(int[] array, int start, int end) {
if (start == end) {
return ;
}
int mid = start + (end - start) / 2;
mergeSort(array, start, mid);
mergeSort(array, mid + 1, end);
merge(array, start, mid, mid + 1, end);
return;
}
private static void merge(int[] array,int start1,int end1,int start2,int end2) {
int i = start1;
int j = start2;
int k = 0;
while (i <= end1 && j <= end2) {
temp[k++] = array[i] < array[j] ? array[i++]:array[j++];
}
while (i <= end1) {
temp[k++] = array[i++];
}
while (j <= end2) {
temp[k++] = array[j++];
}
//將temp的復制到對應的[start1,end1] [start2,end2]
k = 0 ;
for(int index = start1 ; index <= end1 ; index++){
array[index] = temp[k++];
}
for(int index = start2 ; index <= end2 ; index++){
array[index] = temp[k++];
}
}
}
測試的是成功的，但是不知道是不是最優(yōu)的做法，我只是按照思路自行寫了一遍，大家可以參考其他網站的寫法，畢竟這些常見排序算法的講解到處都是！
如果有更好的更優(yōu)雅的書寫方式，可以指出來，sharing is important！
我還是想吐槽啊，簡書為啥不能可以修改文字的顏色，不需要太多顏色，就紅色我也滿足了?。。?！我也不是想搞得花哨，只是覺得黑白還是太單調了，粗體有的時候也不能滿足我想要強調的心情。
