MergeSort -- 归并排序
博客专区 > gAKey 的博客 > 博客详情
MergeSort -- 归并排序
gAKey 发表于3个月前
MergeSort -- 归并排序
  • 发表于 3个月前
  • 阅读 0
  • 收藏 0
  • 点赞 0
  • 评论 0

华为云·免费上云实践>>>   

/*
 * 归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。
 * 如设有数列{6,202,100,301,38,8,1}
 * 初始状态: [6] [202] [100] [301] [38] [8] [1] 比较次数
 * i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]         3
 * i=2 [ 6 100 202 301 ] [ 1 8 38 ]              4
 * i=3 [ 1 6 8 38 100 202 301 ]             4
 */

public class MergeSort {
	public static void sort(int[] data) {
		int[] temp = new int[data.length];
		mergeSort(data, temp, 0, data.length - 1);
	}

	private static void mergeSort(int[] data, int[] temp, int l, int r) {
		int mid = (l + r) / 2;
		if (l == r)
			return;
		mergeSort(data, temp, l, mid);
		mergeSort(data, temp, mid + 1, r);

		for (int i = l; i <= r; i++) {
			temp[i] = data[i];
		}
		int i1 = l;
		int i2 = mid + 1;
		for (int cur = l; cur <= r; cur++) {
			if (i1 == mid + 1)
				data[cur] = temp[i2++];
			else if (i2 > r)
				data[cur] = temp[i1++];
			else if (temp[i1] < temp[i2])
				data[cur] = temp[i1++];
			else

				data[cur] = temp[i2++];
		}
	}
}

 

共有 人打赏支持
粉丝 3
博文 38
码字总数 2477
×
gAKey
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: