/**
* 模擬歸并排序merge sort
* 思路是將一個數(shù)組分成兩半 每一半再繼續(xù)分半 遞歸的拆分直至每個范圍內(nèi)只有一個元素 從最小的單元開始排序、返回上一層變?yōu)楦蟮膯卧判蛟俜祷厣弦粚幼兂筛蟮膯卧?最后完成整個數(shù)組的排序

*/
public class TestMergeSort {

? ?public static void sort(int[] arr){
? ? ? ?//先重載一個給整個數(shù)組排序的方法 不用手動輸入low=0 high=length-1 方便使用更易懂
? ? ? ?sort(arr, 0, arr.length-1);
? ? ? ?//最高位是length-1
? ?}

? ?public static void sort(int[] arr,int low,int high){
? ? ? ?if (low<high){
? ? ? ? ? ?//當(dāng)low=high即范圍內(nèi)只有一個數(shù)的時候不執(zhí)行直接結(jié)束迭代 兩個數(shù)及以上才需要排序
? ? ? ? ? ?int mid = (high+low)/2;
? ? ? ? ? ?sort(arr,low,mid);
? ? ? ? ? ?sort(arr,mid+1,high);
? ? ? ? ? ?//將當(dāng)前范圍分割成左右兩部分 分別進(jìn)行排序 這里會一層一層迭代 直到子范圍內(nèi)只有一個數(shù)的時候結(jié)束迭代 然后返回上一層依次進(jìn)行后續(xù)運(yùn)算
? ? ? ? ? ?//最下層兩個子范圍都是一個數(shù) 結(jié)束迭代 回到上一層往下執(zhí)行運(yùn)算 將兩個子范圍排序 執(zhí)行完就得到了范圍=2的有序集合
? ? ? ? ? ?// 執(zhí)行完結(jié)束 返回上一層 用范圍=2的有序集合和另外一個有序集合排序 執(zhí)行完再返回上一層 層層執(zhí)行、返回 直到最高層
? ? ? ? ? ?//最高層是數(shù)組的整個左半邊和整個右半邊 兩個半邊內(nèi)部都是排好序的 再將這兩部分執(zhí)行下面的運(yùn)算
? ? ? ? ? ?int[] b = new int[high-low+1];
? ? ? ? ? ?//new一個數(shù)組 長度和現(xiàn)在要排序的范圍的長度一致
? ? ? ? ? ?int i = 0;
? ? ? ? ? ?int left = low;
? ? ? ? ? ?//左半邊范圍的首位 用于左邊的索引
? ? ? ? ? ?int right = mid+1;
? ? ? ? ? ?//右半邊范圍的首位 用于右邊的索引
? ? ? ? ? ?while (left<mid+1&&right<high+1){
? ? ? ? ? ? ? ?b[i++] = (arr[left]<arr[right])?arr[left++]:arr[right++];
? ? ? ? ? ? ? ?//因為左半邊范圍和右半邊范圍都是從小到大排序好的 所以每次都比較兩個范圍內(nèi)最左側(cè)的那個元素 哪個小就放入b[i]中并將這邊的索引+1
? ? ? ? ? ? ? ?//等號左側(cè)也可以++ 條件運(yùn)算符內(nèi)也可以++
? ? ? ? ? ? ? ?//當(dāng)左邊或者右邊取完了即left<mid+1&&right<high+1 為false時結(jié)束循環(huán) 因為每次循環(huán)只會取左邊或者右邊一位數(shù) 所以不可能兩側(cè)同時取完 還沒取出的部分要繼續(xù)取
? ? ? ? ? ?}
? ? ? ? ? ?while (left<mid+1){
? ? ? ? ? ? ? ?//如果右邊取完了 左邊沒取完 這時b[]中所有存在的元素都比沒取完的小 沒取完的又是有序的 所以遍歷剩余的依次存到b中
? ? ? ? ? ? ? ?b[i++] = arr[left++];
? ? ? ? ? ?}
? ? ? ? ? ?while (right<high+1){
? ? ? ? ? ? ? ?//如果左邊取完了 右邊沒取完
? ? ? ? ? ? ? ?b[i++] = arr[right++];
? ? ? ? ? ?}
? ? ? ? ? ?//到這時左右兩邊都取完了 b也填滿了
? ? ? ? ? ?for (i = 0;i<b.length;i++){
? ? ? ? ? ? ? ?arr[low++] = b[i];
? ? ? ? ? ? ? ?//將b遍歷 存回arr的范圍中 即完成對當(dāng)前范圍的排序
? ? ? ? ? ?}
? ? ? ?}
? ?}

? ?public static void main(String[] args) {
? ? ? ?int[] a = {7,82,4,6,35,1,19,32,2};
? ? ? ?sort(a);
? ? ? ?System.out.println(Arrays.toString(a));
? ? ? ?//結(jié)果[1, 2, 4, 6, 7, 19, 32, 35, 82]
????????/*
????????第一步 7，82，4，6，35 ? 1，19，32，2
????????第二步 7，82，4 ? ? 6，35 ? ? 1，19，32，2
????????第三步 7，82 ? 4 ? ?6，35 ? ?1，19，32，2
????????第四步 7 ? 82 ? 4 ? 6，35 ? ? 1，19，32，2
????????第五步 7，82 ? 4 ? 6，35 ? ?1，19，32，2
????????第六步 4，7，82 ? ?6，35 ? ? 1，19，32，2
????????第七步 4，7，82 ? ?6 ? ?35 ? ?1，19，32，2
????????第八步 4，7，82 ? ?6，35 ? ? 1，19，32，2
????????第九步 4，6，7，35，82 ? ? ?1，19，32，2
????????第十步 4，6，7，35，82 ? ? ?1，19 ? ? ?32，2
????????十一步 4，6，7，35，82 ? ? ?1 ?19 ?32，2
????????十二步 4，6，7，35，82 ? ? ?1，19 ? ?32，2
????????十三步 4，6，7，35，82 ? ? ?1，19 ? ? 32 ? 2
????????十四步 4，6，7，35，82 ? ? ?1，19 ? ? ?2，32
????????十五步 4，6，7，35，82 ? ? ?1，2，19，32
????????十六步 1，2，4，6，7，19，32，35，82
????????*/

? ?}
}