Java排序算法——归并排序

import java.util.Arrays;//=================================================// File Name :MergeSort//------------------------------------------------------------------------------// Author:Common//类名：Arrays_Merge//属性：//方法：class Arrays_Merge{private int[] arrays;private int curNum;//int[] workSpace;public Arrays_Merge(int max) { //建立一个max长度的空数组super();arrays = new int[max];curNum = 0;}public void insert(int value){ //往空的数组里面增加元素arrays[curNum] = value;curNum++;}public void display(){ //显示数组System.out.println(Arrays.toString(arrays));}public void mergeSort(){int[] arrays = new int[curNum];recMergeSort(arrays, 0, curNum-1);}public void recMergeSort(int[] 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);System.out.println("mid="+mid);}}public void merge(int[] 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(arrays[lowPtr]<arrays[highPtr]){//如果后面的小，就先放进新的数组中workSpace[j++] = arrays[lowPtr++];//如果运行第一行，就运行下面的第二个System.out.println("1lowPtr="+(lowPtr-1)+" "+workSpace[j-1]);}else{workSpace[j++] = arrays[highPtr++];//如果运行第二行，就运行下面的第一个System.out.println("1highPtr="+(highPtr-1)+" "+(j-1)+"="+workSpace[j-1]);}}while(lowPtr<=mid){//以下两个只可能运行一个workSpace[j++] = arrays[lowPtr++]; System.out.println("lowPtr="+(lowPtr-1)+" "+workSpace[j-1]);}while(highPtr<=upperBound){workSpace[j++] = arrays[highPtr++];System.out.println("highPtr="+(highPtr-1)+" "+workSpace[j-1]);}for(j=0;j<n;j++){arrays[lowerBound+j] = workSpace[j];}}}//主类//Function : MergeSortpublic class MergeSort {public static void main(String[] args) {// TODO 自动生成的方法存根int maxSize=10;Arrays_Merge arr;arr = new Arrays_Merge(maxSize);arr.insert(9);arr.insert(8);arr.insert(7);arr.insert(6);arr.insert(5);arr.insert(4);arr.insert(3);arr.insert(2);arr.insert(1);arr.display();arr.mergeSort();arr.display();}}