2018-09-19 归并排序 (递归和非递归)

一，归并

所谓的归并，既是将两个已经排好序的队列合并成一个有序队列。英文中用merge这个词。
分析如下图：

2018-09-19 归并排序 (递归和非递归)

通过上图，基本能够理解归并的原理，那么下边用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 的有序数组为止

2018-09-19 归并排序 (递归和非递归)

递归的思路很容易理解，我们只需要把数组对半拆分，然后再对半拆分，直到拆分为只含有一个元素的子数组，然后再把子数两两归并。
递归方式实现代码：

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++];
        }
    }
}