一，归并
所谓的归并，既是将两个已经排好序的队列合并成一个有序队列。英文中用merge这个词。
分析如下图：
图片发自简书App
通过上图，基本能够理解归并的原理，那么下边用java代码来体现一下上边过程。
展示一下如何从两个有序队列归并成一个有序队列
public class MergeTest {
public static int[] merge(int[] a, int[] b) {
int[] c = new int[a.length + b.length];
int ai = 0;
int bi = 0;
int ci = 0;
while (ai < a.length && bi < b.length) {// 当两个数组都没耗尽时,则以一直循环下去
if (a[ai] <= b[bi]) {
c[ci++] = a[ai++];
} else {
c[ci++] = b[bi++];
}
}
while (ai < a.length) //此时说明a数组还有元素
c[ci++] = a[ai++];
while (bi < b.length) //此时说明b数组还有元素
c[ci++] = b[bi++];
return c;
}
public static void main(String[] args) {
int[] a = {5,8,11,19,22,25};
int[] b = {7,9,20,30,35,38,40};
int [] c = merge(a, b);
System.out.println(Arrays.toString(c));
}
}
二，归并排序
归并排序有多路归并排序，两路归并排序，这里只看一下两路归并排序。
一个含有n个元素无序的数组如何使用归并排序进行排序呢。
思路：
1，把 n 个元素看作有n个长度为1的子数组。
2，然后进行两两归并操作，得到一个有n/2个长度为2的子数组
3，重复步骤2，直到成为一个长度为 n 的有序数组为止
图片发自简书App
递归的思路很容易理解，我们只需要把数组对半拆分，然后再对半拆分，直到拆分为只含有一个元素的子数组，然后再把子数两两归并。
递归方式实现代码：
import java.util.Arrays;
/**
* 归并排序
* @author bsnpbus
*
*/
public class MergeSort1 {
private static void sort(int[] arr) {
int[] temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
sort(arr, 0, arr.length-1, temp);
}
private static void sort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;
sort(arr, left, mid, temp); // 左边递归 归并排序
sort(arr, mid+1, right, temp); // 右边递归 归并排序
merge(arr, left, mid, right, temp);
}
}
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 左序列指针
int j = mid+1; // 右序列指针
int t = 0; // 临时数组指针
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[t++] = arr[i++];
} else {
temp[t++] = arr[j++];
}
}
while (i <= mid) { // 如果左边有剩余,将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while (j <= right) { // 如果右边有剩余,将右边剩余元素填充进temp中
temp[t++] = arr[j++];
}
// 将temp中元素全部拷贝到原数组中
t = 0;
while (left <= right) {
arr[left++] = temp[t++];
}
}
public static void main(String[] args) {
int[] arr = {9,1,7,5,4,6,3,8,2};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
非递归循环方式实现：
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
/**
* 归并排序的 非递归算法 (循环方式)
* @author bsnpbus
*
*/
public class MergeSort3 {
public static void main(String args[]){
MergeSort3 mer = new MergeSort3();
//int[] array = mer.getArray();// 生成100个随机数字
int[] array = {9,1,7,5,4,6,3,8,2};
System.out.println("OriginalArray:" + Arrays.toString(array));
mer.mergeSort(array);
System.out.println("SortedArray:" + Arrays.toString(array));
}
public int[] getArray(){
Scanner cin = new Scanner(System.in);
System.out.print("Input the length of Array:");
int length = cin.nextInt();
int[] arr = new int[length];
Random r = new Random();
for(int i = 0; i < length; i++){
arr[i] = r.nextInt(100);
}
cin.close();
return arr;
}
public void mergeSort(int[] a){
int len = 1;
while(len < a.length){
for(int i = 0; i < a.length; i += 2*len){
merge(a, i, len);
}
len *= 2;
}
}
public void merge(int[] a, int i, int len){
int start = i;
int len_i = i + len;//要归并的前半部分数组
int j = i + len;
int len_j = j +len;//要归并的后半部分数组
int[] temp = new int[2*len];
int count = 0;
while(i < len_i && j < len_j && j < a.length){
if(a[i] <= a[j]){
temp[count++] = a[i++];
}
else{
temp[count++] = a[j++];
}
}
while(i < len_i && i < a.length){//注意：这里i也有可能超过数组长度
temp[count++] = a[i++];
}
while(j < len_j && j < a.length){
temp[count++] = a[j++];
}
count = 0;
while(start < j && start < a.length){
a[start++] = temp[count++];
}
}
}
