我的Java开发学习之旅------>Java经典排序算法之归并排序

 void Merge(SeqList R，int low，int m，int high)
    {//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的
     //子文件R[low..high]
     int i=low，j=m+1，p=0； //置初始值
     RecType *R1； //R1是局部向量，若p定义为此类型指针速度更快
     R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))；
     if(! R1) //申请空间失败
       Error("Insufficient memory available!")；
     while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上
       R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]；
     while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中
       R1[p++]=R[i++]；
     while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中
       R1[p++]=R[j++]；
     for(p=0，i=low；i<=high；p++，i++)
       R[i]=R1[p]；//归并完成后将结果复制回R[low..high]
    } //Merge

void MergeSortDC(SeqList R，int low，int high)
     {//用分治法对R[low..high]进行二路归并排序
       int mid；
       if(low<high){//区间长度大于1
          mid=(low+high)/2； //分解
          MergeSortDC(R，low，mid); //递归地对R[low..mid]排序
          MergeSortDC(R，mid+1，high)； //递归地对R[mid+1..high]排序
          Merge(R，low，mid，high)； //组合，将两个有序区归并为一个有序区
        }
     }//MergeSortDC

public class MergeSortTest {

	public static void main(String[] args) {
		int[] data = new int[] { 2, 4, 7, 5, 8, 1, 3, 6 };
		System.out.print("初始化：\t");
		print(data);
		System.out.println("");
	
		mergeSort(data, 0, data.length - 1);
		
		System.out.print("\n排序后:  \t");
		print(data);
	}

	public static void mergeSort(int[] data, int left, int right) {
		if (left >= right)
			return;
		//两路归并
		// 找出中间索引
		int center = (left + right) / 2;
		// 对左边数组进行递归
		mergeSort(data, left, center);
		// 对右边数组进行递归
		mergeSort(data, center + 1, right);
		// 合并
		merge(data, left, center, center + 1, right);
		System.out.print("排序中:\t");
		print(data);
	}

	/**
	 * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序
	 * 
	 * @param data
	 *            数组对象
	 * @param leftStart
	 *            左数组的第一个元素的索引
	 * @param leftEnd
	 *            左数组的最后一个元素的索引
	 * @param rightStart
	 *            右数组第一个元素的索引
	 * @param rightEnd
	 *            右数组最后一个元素的索引
	 */
	public static void merge(int[] data, int leftStart, int leftEnd,
			int rightStart, int rightEnd) {
		int i = leftStart;
		int j = rightStart;
		int k = 0;
		// 临时数组
		int[] temp = new int[rightEnd - leftStart + 1]; //创建一个临时的数组来存放临时排序的数组 
		// 确认分割后的两段数组是否都取到了最后一个元素
		while (i <= leftEnd && j <= rightEnd) {
			// 从两个数组中取出最小的放入临时数组
			if (data[i] > data[j]) {
				temp[k++] = data[j++];
			} else {
				temp[k++] = data[i++];
			}
		}
		// 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
		while (i <= leftEnd) {
			temp[k++] = data[i++];
		}
		while (j <= rightEnd) {
			temp[k++] = data[j++];
		}
		k = leftStart;
		// 将临时数组中的内容拷贝回原数组中 // （原left-right范围的内容被复制回原数组）
		for (int element : temp) {
			data[k++] = element;
		}
	}

	public static void print(int[] data) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + "\t");
		}
		System.out.println();
	}
}

初始化：	2	4	7	5	8	1	3	6	

排序中:	2	4	7	5	8	1	3	6	
排序中:	2	4	5	7	8	1	3	6	
排序中:	2	4	5	7	8	1	3	6	
排序中:	2	4	5	7	1	8	3	6	
排序中:	2	4	5	7	1	8	3	6	
排序中:	2	4	5	7	1	3	6	8	
排序中:	1	2	3	4	5	6	7	8	

排序后:  	1	2	3	4	5	6	7	8	

==================================================================================================

  作者：欧阳鹏  欢迎转载，与人分享是进步的源泉！

  转载请保留原文地址：http://blog.csdn.net/ouyang_peng

==================================================================================================