数据结构与算法（JAVA篇）之递归算法（三）

<!----><!----><!----><!----><!----><!----><!---->

/**
 *
 * @author SunnyMoon
 */

/**
 * 概念介绍：
 * 
 * 归并排序：归并算法的中心是归并两个已经有序的数组，并且递归调用归并操作。
 * 
 * 归并排序优点和缺点：比简单排序在速度上快很多；归并排序会占用双倍的存储空间。
 * 
 * 归并排序的效率：归并排序的时间复杂度是 O(N*LogN)；简单排序的复杂度是O(N2)。
 */
public class Recursion3 {

    private long[] theArray;
    private int nElems;

    public Recursion3(int max) {//初始化数组
        theArray = new long[max];
        nElems = 0;
    }

    public void insert(long value) {//插入数据
        theArray[nElems] = value;
        nElems++;
    }

    public void display() {//显示数组中的数据
        for (int j = 0; j < nElems; j++) {
            System.out.print(theArray[j]+","+" ");
        }
    }
    /**
     * 归并排序算法
     */
    public void mergeSort() {
        long[] workSpace = new long[nElems];//创建一个工作数组，用于排序操作使用
        recMergeSort(workSpace, 0, nElems - 1);//执行归并排序操作
    }
    
    /**
     * 递归分割数据到基本单位
     */
    private void recMergeSort(long[] workSpace, int lowerBound, int upperBound) {
        if (lowerBound == upperBound) {
            return;
        } else {
            int mid = (lowerBound + upperBound) / 2;
            recMergeSort(workSpace, lowerBound, mid);
            recMergeSort(workSpace, mid + 1, upperBound);
            merge(workSpace, lowerBound, mid + 1, upperBound);
        }
    }
    
    /**
     * 归并操作将基本单位归并成整个有序的数组
     */
    private void merge(long[] workSpace, int lowPtr, int highPtr, int upperBound) {
        int j = 0;
        int lowerBound = lowPtr;
        int mid = highPtr - 1;
        int n = upperBound - lowerBound + 1;

        while (lowPtr <= mid && highPtr <= upperBound) {
            if (theArray[lowPtr] < theArray[highPtr]) {
                workSpace[j++] = theArray[lowPtr++];
            } else {
                workSpace[j++] = theArray[highPtr++];
            }
        }
            while (lowPtr <= mid) {
                workSpace[j++] = theArray[lowPtr++];
            }
            while (highPtr <= upperBound) {
                workSpace[j++] = theArray[highPtr++];
            }
            for (j = 0; j < n; j++) {
                theArray[lowerBound + j] = workSpace[j];
            }
    }
    public void println(String str){
            System.out.println(str);
        }
}

class MergeSortApp {//主程序

    public static void main(String[] args) {
        int maxSize = 100;
        Recursion3 arr = new Recursion3(maxSize);
        /**
         * 插入值到数组
         */
        arr.insert(64);
        arr.insert(21);
        arr.insert(11);
        arr.insert(33);
        arr.insert(12);
        arr.insert(85);
        arr.insert(44);
        arr.insert(99);
        arr.insert(3);
        arr.insert(0);
        arr.insert(108);
        arr.insert(36);
        
        arr.println("显示排序前数据：");
        arr.display();
        arr.println("");  
        
        arr.mergeSort();
        
        arr.println("显示排序后数据：");
        arr.display();
        arr.println("");  
    }
}
/**
 * 
 * 显示排序前数据：
 * 64, 21, 11, 33, 12, 85, 44, 99, 3, 0, 108, 36, 
 * 显示排序后数据：
 * 0, 3, 11, 12, 21, 33, 36, 44, 64, 85, 99, 108,
 */

/**
 * 总结：
 * 归并排序比简单排序的效率高很多，把递归发挥的淋漓尽致，大家可以试一下。
 * 最后给出归并排序工作过程图解。
 */

 

    图1： 归并排序工作过程

 

   <!----><!----><!----> <!---->