合并排序

概述

合并的升序排列

代码

package com.lilei.myes.es.pack1114;

import java.util.Random;

public class merge_sort {

	public static void main(String[] args) {

		Random rand = new Random();

		int[] array = new int[10];

		for (int i = 0; i < array.length; i++)
			array[i] = rand.nextInt(100);

		for (int v : array)
			System.out.print(v + ",");

		System.out.println();
		int[] aux = new int[array.length];

		merge(array,aux,0,array.length-1);

		for (int v : array)
			System.out.print(v + ",");
	}

	static void merge(int[] array,int[] aux, int left, int right) {
		if (left < right) {

			int mid = (left + right) / 2;
			merge(array,aux,left,mid);
			merge(array,aux,mid+1,right);
			
			int p_left = left;
			int p_right = mid+1;
			int p_aux = left;
			
			while(p_left<=mid && p_right<=right){
				if (array[p_left] < array[p_right]){
					aux[p_aux] = array[p_left];
					p_left++;
				}else{
					aux[p_aux] = array[p_right];
					p_right++;
				}
				p_aux++;
			}
			
			if (p_left<=mid){
				for(int i=p_left;i<=mid;i++){
					aux[p_aux++] = array[i];
				}
			}else if (p_right<=right){
				for(int i=p_right;i<=right;i++){
					aux[p_aux++] = array[i];
				}
			}
			
			for(int i=left;i<=right;i++){
				array[i] = aux[i];
			}
		}

	}

}