首页 > 开发 > Java > 正文

Java排序算法之归并排序简单实现

2024-07-13 10:14:53
字体:
来源:转载
供稿:网友

算法描述:对于给定的一组记录,首先将每两个相邻的长度为1的子序列进行归并,得到 n/2(向上取整)个长度为2或1的有序子序列,再将其两两归并,反复执行此过程,直到得到一个有序序列。

package sorting;/** * 归并排序 * 平均O(nlogn),最好O(nlogn),最坏O(nlogn);空间复杂度O(n);稳定;较复杂 * @author zeng * */public class MergeSort {	public static void merge(int[] a, int start, int mid,	      int end) {		int[] tmp = new int[a.length];		System.out.println("merge " + start + "~" + end);		int i = start, j = mid + 1, k = start;		while (i != mid + 1 && j != end + 1) {			if (a[i] < a[j])			        tmp[k++] = a[i++]; else			        tmp[k++] = a[j++];		}		while (i != mid + 1)		      tmp[k++] = a[i++];		while (j != end + 1)		      tmp[k++] = a[j++];		for (i = start; i <= end; i++)		      a[i] = tmp[i];		for (int p : a)		      System.out.print(p + " ");		System.out.println();	}	static void mergeSort(int[] a, int start, int end) {		if (start < end) {			int mid = (start + end) / 2;			mergeSort(a, start, mid);			// 左边有序			mergeSort(a, mid + 1, end);			// 右边有序			merge(a, start, mid, end);		}	}	public static void main(String[] args) {		int[] b = { 49, 38, 65, 97, 76, 13, 27, 50 };		mergeSort(b, 0, b.length - 1);	}}

运行结果看一下:

java,归并排序算法,归并算法

总结

以上就是本文关于Java排序算法之归并排序简单实现的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!


注:相关教程知识阅读请移步到JAVA教程频道。
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表