欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

常用排序算法之-------------归并排序

程序员文章站 2022-03-24 14:09:22
...

递归实现

package sort;

public class MergeSort {

	public static void main(String[] args) {
		int[] arr = {2,4,1,5,6,3,9};
		mergeSort(arr);
		print(arr);
	}
	/**
	 * x归并排序的递归方法,先取mid,二分,分到L=R为止,即只剩一个数,
	 * x然后往上依次合并,借助额外数组,合并时,将两个分别有序部分中较小的数值依次放入额外数组
	 * x最后额外数组的值拷贝回原数组
	 * @param arr
	 * x时间复杂度为O(NlogN),空间复杂度为O(N)
	 */
	private static void mergeSort(int[] arr) {
		// TODO Auto-generated method stub
		if(arr == null || arr.length < 2)
			return;
		sortProcess(arr, 0, arr.length-1);
	}

	private static void sortProcess(int[] arr, int L, int R) {
		// TODO Auto-generated method stub
		if(L == R)
			return;
		int mid = L + ((R - L) >> 1);
		sortProcess(arr, L, mid);
		sortProcess(arr, mid + 1, R);
		merge(arr, L, mid, R);
	}

	private static void merge(int[] arr, int L, int mid, int R) {
		// TODO Auto-generated method stub
		int[] help = new int[R - L + 1];
		int i = 0;
		int p1 = L;
		int p2 = mid + 1;
		while (p1 <= mid && p2 <= R) {
			help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
		}
		while(p1 <= mid)
			help[i++] = arr[p1++];
		while(p2 <= R)
			help[i++] = arr[p2++];
		for (int j = 0; j < help.length; j++) {
			arr[L + j] = help[j];
		}
	}
	private static void print(int[] arr) {
		for (int i : arr) {
			System.out.print(i+"\t");
		}
	}
}

非递归实现

package sort;

public class MergeSort_2 {

	public static void main(String[] args) {
		int[] arr = {2,4,1,5,6,3,9,1,2,3,5,56,0,23,8};
		mergeSort(arr);
		print(arr);
	}
	private static void mergeSort(int[] arr) {
		if(arr == null || arr.length < 2)
			return;
		int span = 1;
		int[] temp = new int[arr.length];
		while (span < arr.length) {
			merge_method(arr, span, arr.length);
			span *= 2;
		}
	}
	private static void merge_method(int[] arr, int span, int length) {
		// TODO Auto-generated method stub
		int index = 0,j;
		while(index + 2*span - 1 < length) {
			merge(arr, index, index+span-1, index+2*span-1);
			index = index + 2*span;
		}
		//处理剩下的不能构成完整的两组的
		if(index + span - 1 < length)
			merge(arr, index, index + span - 1, length - 1);
	}
	private static void merge(int[] arr, int L, int mid, int R) {
		// TODO Auto-generated method stub
		int[] help = new int[R - L + 1];
		int i = 0;
		int p1 = L;
		int p2 = mid + 1;
		while (p1 <= mid && p2 <= R) {
			help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
		}
		while(p1 <= mid)
			help[i++] = arr[p1++];
		while(p2 <= R)
			help[i++] = arr[p2++];
		for (int j = 0; j < help.length; j++) {
			arr[L + j] = help[j];
		}
	}
	private static void print(int[] arr) {
		for (int i : arr) {
			System.out.print(i+"\t");
		}
	}
}

 

相关标签: 算法 归并排序