算法学习(十)-递归 之归并排序

算法学习(10)-递归 之归并排序

package com.tw.dst.recursive;

/**  
 * <p>
 * 算法学习 ----递归
 * 概念介绍:
 * 归并排序：归并算法的中心是归并两个已经有序的数组，并且递归调用归并操作。   
 * 归并排序优点和缺点：比简单排序在速度上快很多；归并排序会占用双倍的存储空间。  
 * 归并排序的效率：归并排序的时间复杂度是 O(N*LogN)；简单排序的复杂度是O(N2)。</p>
 * @author tangw 2010-12-13
 */  
public class MergeRecursion3 {   
  
    private long[] theArray;   
    private int nElems;   
    /**
     * <p>初始化数组</p> 
     * @param max
     */
    public MergeRecursion3(int max) {  
        theArray = new long[max];   
        nElems = 0;   
    }   
  
    /**
     * <p>插入数据</p>
     * @param value
     */
    public void insert(long value) {   
        theArray[nElems] = value;   
        nElems++;   
    }   
    /**
     * <p>显示数组中的数据</p>
     */
    public void display() {
        for (int j = 0; j < nElems; j++) {   
            System.out.print(theArray[j]+","+" ");   
        }   
    }   
    /**  
     * <p>归并排序算法</p>
     */  
    public void mergeSort() {   
        long[] workSpace = new long[nElems];//创建一个工作数组，用于排序操作使用   
        recMergeSort(workSpace, 0, nElems - 1);//执行归并排序操作   
    }   
       
    /**
     * <p>递归分割数据到基本单位 </p> 
     * @param workSpace
     * @param lowerBound
     * @param upperBound
     */
    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);   
        }   
    }   
       
	/**
	 * 归并操作将基本单位归并成整个有序的数组 
	 * @param workSpace
	 * @param lowPtr
	 * @param highPtr
	 * @param 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);   
    }   
    
    
    public static void main(String[] args) {   
        int maxSize = 100;   
        MergeRecursion3 arr = new MergeRecursion3(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,  
 */  
  
/**  
 * 总结：  
 * 归并排序比简单排序的效率高很多
 */