合並排序的道理及java代碼完成。本站提示廣大學習愛好者：（合並排序的道理及java代碼完成）文章只能為提供參考，不一定能成為您想要的結果。以下是合並排序的道理及java代碼完成正文
概述
合並（Merge）排序法是將兩個（或兩個以上）有序表歸並成一個新的有序表，即把待排序序列分為若干個子序列，每一個子序列是有序的。然後再把有序子序列歸並為全體有序序列。
合並排序采取的是遞歸來完成，屬於“分而治之”，將目的數組從中央一分為二，以後分離對這兩個數組停止排序，排序終了以後再將排好序的兩個數組“合並”到一路，合並排序最主要的也就是這個“合並”的進程，合並的進程中須要額定的跟須要合並的兩個數組長度分歧的空間。
後果圖：
步調
請求空間，使其年夜小為兩個曾經排序序列之和，該空間用來寄存歸並後的序列
設定兩個指針，最後地位分離為兩個曾經排序序列的肇端地位
比擬兩個指針所指向的元素，選擇絕對小的元素放入到歸並空間，並挪動指針到下一名置
反復步調3直到某一指針到達序列尾
將另外一序列剩下的一切元素直接復制到歸並序列尾
實例
原始數據：
3 5 2 6 2
合並的條件是將數組離開，一分為二，再一分為二，分到不克不及再分，停止合並。
第一輪分隔，索引2 ((0+4)/2=2) 為中央
[3 5 2] [6 2]
第二輪分隔，對[3 5 2]停止分隔
[3 5] [2] [6 2]
第三輪分隔，對[3 5]停止分隔
[3] [5] [2] [6 2]
歸並[3] [5]
[3 5] [2] [6 2]
歸並[3 5] [2]
[2 3 5] [6 2]
第四輪分隔，對[6 2]停止分隔
[2 3 5] [6] [2]
歸並[6] [2]
[2 3 5] [2 6]
歸並[2 3 5] [2 6]
[2 2 3 5 6]
代碼完成(Java)
package com.coder4j.main.arithmetic.sorting;
public class Merge {
private static int mark = 0;
/**
* 合並排序
*
* @param array
* @param low
* @param high
* @return
*/
private static int[] sort(int[] array, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
mark++;
System.out.println("正在停止第" + mark + "次分隔，獲得");
System.out.println("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]");
// 右邊數組
sort(array, low, mid);
// 左邊數組
sort(array, mid + 1, high);
// 閣下合並
merge(array, low, mid, high);
}
return array;
}
/**
* 對數組停止合並
*
* @param array
* @param low
* @param mid
* @param high
*/
private static void merge(int[] array, int low, int mid, int high) {
System.out.println("歸並:[" + low + "-" + mid + "] 和 [" + (mid + 1) + "-" + high + "]");
int[] temp = new int[high - low + 1];
int i = low;// 左指針
int j = mid + 1;// 右指針
int k = 0;
// 把較小的數先移到新數組中
while (i <= mid && j <= high) {
if (array[i] < array[j]) {
temp[k++] = array[i++];
} else {
temp[k++] = array[j++];
}
}
// 兩個數組之一能夠存在殘剩的元素
// 把右邊殘剩的數移入數組
while (i <= mid) {
temp[k++] = array[i++];
}
// 把左邊邊殘剩的數移入數組
while (j <= high) {
temp[k++] = array[j++];
}
// 把新數組中的數籠罩array數組
for (int m = 0; m < temp.length; m++) {
array[m + low] = temp[m];
}
}
/**
* 合並排序
*
* @param array
* @return
*/
public static int[] sort(int[] array) {
return sort(array, 0, array.length - 1);
}
public static void main(String[] args) {
int[] array = { 3, 5, 2, 6, 2 };
int[] sorted = sort(array);
System.out.println("終究成果");
for (int i : sorted) {
System.out.print(i + " ");
}
}
}
測試輸入成果：
正在停止第1次分隔，獲得 [0-2] [3-4] 正在停止第2次分隔，獲得 [0-1] [2-2] 正在停止第3次分隔，獲得 [0-0] [1-1] 歸並:[0-0] 和 [1-1] 歸並:[0-1] 和 [2-2] 正在停止第4次分隔，獲得 [3-3] [4-4] 歸並:[3-3] 和 [4-4] 歸並:[0-2] 和 [3-4] 終究成果 2 2 3 5 6
經測試，與實例中成果分歧。
