归并排序：递归+合并。是经典算法——分治法的典型应用。
思路：1）将一串数据，首先分成两部分，每个部分分别排序，然后合并成一串数据。2）在1）中，由于每个部分的数据并不是有序的，两个分串就需要再次分别分成两部分，这样的话就有了4个分串。3）一直往下分，直到分到每个部分只有一个数据，而一个数据必定是有序的，因为只有它自己本身。4）在1）~3）的过程中需要用到递归的思想。分到最低层时进行合并，每个分串的数据不断累加，直到变成2个大串，最后合并成一个整串。
至于有序序列的合并，可以参考<两个有序序列的合并>。
下面用java代码实现。
/** * 将两个有序数列进行合并,从小到大 * 有序数列分别为：array[firstIndex...middIndex] * array[middIndex+1...lastIndex] * @param array 需要重新整合的数组 * @param firstIndex 数组中序列1的起始下标 * @param middIndex 数组中序列1的结束坐标 * @param lastIndex 数组中序列2的结束坐标 * @param tempArray 操作过程中临时用于存放数据的数组 */ private static void mergeArray(int[] array,int firstIndex, int middIndex,int lastIndex, int[] tempArray) { //tempArray的坐标 int tempIndex = 0; //序列1的坐标 int aIndex = firstIndex; //序列2的坐标 int bIndex = middIndex + 1; //一旦发现序列1或者2中的其中一个的下标已经到了结束坐标 //需要退出循环，否则会造成内存溢出 while((aIndex <= middIndex) && (bIndex <= lastIndex)) { if(array[aIndex]<array[bIndex]) { tempArray[tempIndex++] = array[aIndex++]; } else { tempArray[tempIndex++] = array[bIndex++]; } } //如果是序列1的下标还没到结束坐标 while(aIndex <= middIndex) { tempArray[tempIndex++] = array[aIndex++]; } //如果是序列2的下标还没有到结束坐标 while(bIndex <= lastIndex) { tempArray[tempIndex++] = array[bIndex++]; } //将临时数组tempArray中的数据赋予array for(int i = 0; i < tempIndex; i++) { array[firstIndex + i] = tempArray[i]; } }
/** * 归并排序：递归 && 合并 * * 首先，只有一个元素的序列必定是有序的 * 我们可以从一个元素的序列入手，组建成2个元素的有序序列 * 直到最后组建成N个元素的有序序列 * 当然，给定了一个N元素的数组后，就是对上面所述的逆过程 * * @param array 要排序的数组 * @param firstIndex 数组头 * @param lastIndex 数组尾 * @param tempArray 临时数组 */ private static void mergeSort(int[] array, int firstIndex, int lastIndex, int[] tempArray) { if(firstIndex < lastIndex) { int middIndex = (firstIndex + lastIndex) / 2; //左边有序 mergeSort(array, firstIndex, middIndex, tempArray); //右边有序 mergeSort(array, middIndex + 1, lastIndex, tempArray); //将两个有序数列合并 mergeArray(array, firstIndex, middIndex, lastIndex, tempArray); } }
public static void main(String[] args) { // TODO Auto-generated method stub int[] tempArray = new int[10]; int[] array = {50,10,90,30,70,40,80,60,20}; mergeSort(array,0,8,tempArray); for(int i = 0;i <9; i++) { System.out.println(array[i]); } }
参考文章：http://blog.csdn.net/morewindows/article/details/6678165