7. 归并排序（Merge Sort）
基本思想：
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序示例：
合并方法：
设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为m+1-i 、n+1-m。
- j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标
- 若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束
- //选取r[i]和r[j]较小的存入辅助数组rf
如果r[i]<r[j]，rf[k]=r[i]； i++； k++； 转⑵
否则，rf[k]=r[j]； j++； k++； 转⑵ - //将尚未处理完的子表中元素存入rf
如果i<=m，将r[i…m]存入rf[k…n] //前一子表非空
如果j<=n , 将r[j…n] 存入rf[k…n] //后一子表非空 - 合并结束。
算法代码：（方法一，两个for循环）
public class MergeSort2 {
private static void mergeSort(int[] a) {
double len = a.length;
int time = (int)len >> 1; //相当于len/2 ，即归并的趟数
for(int i=0; i<time; i++){
int subLength = 1 << i; //相当于2的i次方 ，子序列的长度
int subNum = (int) Math.ceil(len/((subLength+1)*(i+1))); //子序列数
for(int j=0; j<subNum; j++){
int a1_start = (int) (j*2*subLength< len ? j*2*subLength : len-1); //即下一组归并开始索引与上一组相差值
int a2_start = (int) (a1_start+subLength < len ? a1_start+subLength : len-1);
int a2_end = (int) ((a1_start+2*subLength-1) < len ? (a1_start+2*subLength-1): len-1); //防止最后一个越界
merge(a, a1_start, a2_start, a2_end);
}
System.out.println("-------------归并排序后:-------------");
print(a);
System.out.println("************************************");
}
}
//归并函数，传入的参数分别为：原数组，第一个字序列的开始索引，第二个字序列的开始索引，第二个字序列的结束索引
private static void merge(int[] a, int a1_start, int a2_start, int a2_end){
int len = a.length;
int[] rf = new int[a2_end-a1_start+1];
int i = a1_start, j = a2_start, k = 0;
while( i<a2_start && j <= a2_end){
if(a[i]<a[j]){
rf[k] = a[i];
i++;
k++;
}else{
rf[k] = a[j];
j++;
k++;
}
}
while(i<a2_start){
rf[k] = a[i];
k++;
i++;
}
while(j <= a2_end){
rf[k] = a[j];
k++;
j++;
}
//拷贝rf数组，到原数组 arraycopy(源数组，源数组开始索引，目标数组，目标数组开始索引，需要拷贝的长度);
System.arraycopy(rf,0,a,a1_start,rf.length);
print(a);
}
// 打印数组
public static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int a[] = { 49, 38, 65, 97, 76, 13, 27};
System.out.println("排序前 ： ");
print(a);
System.out.println("排序 ： ");
mergeSort(a);
print(a);
}
}
输出结果：
排序前 ：
49 38 65 97 76 13 27
排序 ：
38 49 65 97 76 13 27
38 49 65 97 76 13 27
38 49 65 97 13 76 27
38 49 65 97 13 76 27
-------------归并排序后:-------------
38 49 65 97 13 76 27
************************************
38 49 65 97 13 76 27
38 49 65 97 13 27 76
-------------归并排序后:-------------
38 49 65 97 13 27 76
************************************
13 27 38 49 65 76 97
-------------归并排序后:-------------
13 27 38 49 65 76 97
************************************
13 27 38 49 65 76 97
归并的迭代算法(方法二)
1 个元素的表总是有序的。所以对n 个元素的待排序列，每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表，所得子表除最后一个子表长度可能为1 外，其余子表长度均为2。再进行两两合并，直到生成n 个元素按关键码有序的表。
public class MergeSort {
// private static long sum = 0;
/**
* <pre>
* 二路归并
* 原理：将两个有序表合并和一个有序表
* </pre>
*
* @param a
* @param s
* 第一个有序表的起始下标
* @param m
* 第二个有序表的起始下标
* @param t
* 第二个有序表的结束小标
*
*/
private static void merge(int[] a, int s, int m, int t) {
int[] tmp = new int[t - s + 1];
int i = s, j = m, k = 0;
while (i < m && j <= t) {
if (a[i] <= a[j]) {
tmp[k] = a[i];
k++;
i++;
} else {
tmp[k] = a[j];
j++;
k++;
}
}
while (i < m) {
tmp[k] = a[i];
i++;
k++;
}
while (j <= t) {
tmp[k] = a[j];
j++;
k++;
}
System.arraycopy(tmp, 0, a, s, tmp.length);
print(a);
}
/**
*
* @param a
* @param s
* @param len
* 每次归并的有序集合的长度
*/
public static void mergeSort(int[] a, int s, int len) {
int size = a.length;
int mid = size / (len << 1); // size/(len*2)
int c = size & ((len << 1) - 1); // 判断数组长度奇偶数
// -------归并到只剩一个有序集合的时候结束算法-------//
if (mid == 0)
return;
// ------进行一趟归并排序-------//
for (int i = 0; i < mid; ++i) {
s = i * 2 * len;
merge(a, s, s + len, (len << 1) + s - 1);
}
// -------将剩下的数和倒数一个有序集合归并-------//
if (c != 0)
merge(a, size - c - 2 * len, size - c, size - 1);
// -------递归执行下一趟归并排序------//
mergeSort(a, 0, 2 * len);
}
public static void main(String[] args) {
int[] a = new int[] {49, 38, 65, 97, 76, 13, 27 };
mergeSort(a, 0, 1);
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
}
// 打印数组
public static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
输出结果：
38 49 65 97 76 13 27
38 49 65 97 76 13 27
38 49 65 97 13 76 27
38 49 65 97 13 27 76
38 49 65 97 13 27 76
13 27 38 49 65 76 97
13 27 38 49 65 76 97
7. 归并排序（Merge Sort）
基本思想：
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序示例：
合并方法：
设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为m+1-i 、n+1-m。
- j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标
- 若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束
- //选取r[i]和r[j]较小的存入辅助数组rf
如果r[i]<r[j]，rf[k]=r[i]； i++； k++； 转⑵
否则，rf[k]=r[j]； j++； k++； 转⑵ - //将尚未处理完的子表中元素存入rf
如果i<=m，将r[i…m]存入rf[k…n] //前一子表非空
如果j<=n , 将r[j…n] 存入rf[k…n] //后一子表非空 - 合并结束。
算法代码：（方法一，两个for循环）
输出结果：
public class MergeSort2 {
private static void mergeSort(int[] a) {
double len = a.length;
int time = (int)len >> 1; //相当于len/2 ，即归并的趟数
for(int i=0; i<time; i++){
int subLength = 1 << i; //相当于2的i次方 ，子序列的长度
int subNum = (int) Math.ceil(len/((subLength+1)*(i+1))); //子序列数
for(int j=0; j<subNum; j++){
int a1_start = (int) (j*2*subLength< len ? j*2*subLength : len-1); //即下一组归并开始索引与上一组相差值
int a2_start = (int) (a1_start+subLength < len ? a1_start+subLength : len-1);
int a2_end = (int) ((a1_start+2*subLength-1) < len ? (a1_start+2*subLength-1): len-1); //防止最后一个越界
merge(a, a1_start, a2_start, a2_end);
}
System.out.println("-------------归并排序后:-------------");
print(a);
System.out.println("************************************");
}
}
//归并函数，传入的参数分别为：原数组，第一个字序列的开始索引，第二个字序列的开始索引，第二个字序列的结束索引
private static void merge(int[] a, int a1_start, int a2_start, int a2_end){
int len = a.length;
int[] rf = new int[a2_end-a1_start+1];
int i = a1_start, j = a2_start, k = 0;
while( i<a2_start && j <= a2_end){
if(a[i]<a[j]){
rf[k] = a[i];
i++;
k++;
}else{
rf[k] = a[j];
j++;
k++;
}
}
while(i<a2_start){
rf[k] = a[i];
k++;
i++;
}
while(j <= a2_end){
rf[k] = a[j];
k++;
j++;
}
//拷贝rf数组，到原数组 arraycopy(源数组，源数组开始索引，目标数组，目标数组开始索引，需要拷贝的长度);
System.arraycopy(rf,0,a,a1_start,rf.length);
print(a);
}
// 打印数组
public static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int a[] = { 49, 38, 65, 97, 76, 13, 27};
System.out.println("排序前 ： ");
print(a);
System.out.println("排序 ： ");
mergeSort(a);
print(a);
}
}
排序前 ：
49 38 65 97 76 13 27
排序 ：
38 49 65 97 76 13 27
38 49 65 97 76 13 27
38 49 65 97 13 76 27
38 49 65 97 13 76 27
-------------归并排序后:-------------
38 49 65 97 13 76 27
************************************
38 49 65 97 13 76 27
38 49 65 97 13 27 76
-------------归并排序后:-------------
38 49 65 97 13 27 76
************************************
13 27 38 49 65 76 97
-------------归并排序后:-------------
13 27 38 49 65 76 97
************************************
13 27 38 49 65 76 97
归并的迭代算法(方法二)
1 个元素的表总是有序的。所以对n 个元素的待排序列，每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表，所得子表除最后一个子表长度可能为1 外，其余子表长度均为2。再进行两两合并，直到生成n 个元素按关键码有序的表。
public class MergeSort {
// private static long sum = 0;
/**
* <pre>
* 二路归并
* 原理：将两个有序表合并和一个有序表
* </pre>
*
* @param a
* @param s
* 第一个有序表的起始下标
* @param m
* 第二个有序表的起始下标
* @param t
* 第二个有序表的结束小标
*
*/
private static void merge(int[] a, int s, int m, int t) {
int[] tmp = new int[t - s + 1];
int i = s, j = m, k = 0;
while (i < m && j <= t) {
if (a[i] <= a[j]) {
tmp[k] = a[i];
k++;
i++;
} else {
tmp[k] = a[j];
j++;
k++;
}
}
while (i < m) {
tmp[k] = a[i];
i++;
k++;
}
while (j <= t) {
tmp[k] = a[j];
j++;
k++;
}
System.arraycopy(tmp, 0, a, s, tmp.length);
print(a);
}
/**
*
* @param a
* @param s
* @param len
* 每次归并的有序集合的长度
*/
public static void mergeSort(int[] a, int s, int len) {
int size = a.length;
int mid = size / (len << 1); // size/(len*2)
int c = size & ((len << 1) - 1); // 判断数组长度奇偶数
// -------归并到只剩一个有序集合的时候结束算法-------//
if (mid == 0)
return;
// ------进行一趟归并排序-------//
for (int i = 0; i < mid; ++i) {
s = i * 2 * len;
merge(a, s, s + len, (len << 1) + s - 1);
}
// -------将剩下的数和倒数一个有序集合归并-------//
if (c != 0)
merge(a, size - c - 2 * len, size - c, size - 1);
// -------递归执行下一趟归并排序------//
mergeSort(a, 0, 2 * len);
}
public static void main(String[] args) {
int[] a = new int[] {49, 38, 65, 97, 76, 13, 27 };
mergeSort(a, 0, 1);
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
}
// 打印数组
public static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
输出结果：
38 49 65 97 76 13 27
38 49 65 97 76 13 27
38 49 65 97 13 76 27
38 49 65 97 13 27 76
38 49 65 97 13 27 76
13 27 38 49 65 76 97
13 27 38 49 65 76 97