萤火小屋

萤火小屋分享世界

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

手撕二路归并排序-Java代码

发表于 2021-03-26 | 分类于 算法学习日记 | 0 | 阅读次数 18

手撕二路归并排序

复杂度和稳定性

时间复杂度:

  1. 最好:O(nlog2n)
  2. 最坏:O(nlog2n)
  3. 平均:O(nlog2n)

空间复杂度:O(n)

稳定性:稳定

Java代码

public class MergeSort {

	public int[] mergeSort(int[] array, int left, int right) {
		if(left == right) {  // 当数组只有一个元素,直接返回单元素数组
			return new int[] { array[left] };
		}
		
		int mid = ( left + right ) / 2;  // 找到数组中点
		int[] leftArray = mergeSort(array, left, mid);        // 左侧数组:递归归并排序左侧数组
		int[] rightArray = mergeSort(array, mid + 1, right);  // 右侧数组:递归归并排序右侧数组
		int[] mergeArray = new int[leftArray.length + rightArray.length];
		
		int leftCursor = 0, rightCursor = 0, mergeCursor = 0;  // 定义左侧数组游标,右侧数组游标,合并数组游标
		
		while (leftCursor < leftArray.length && rightCursor < rightArray.length) {  // 当有一个游标到头就停止
			if (leftArray[leftCursor] < rightArray[rightCursor]) {
				mergeArray[mergeCursor] = leftArray[leftCursor];
				leftCursor++;
			} else {
				mergeArray[mergeCursor] = rightArray[rightCursor];
				rightCursor++;
			}
			mergeCursor++;
		}
		while (leftCursor < leftArray.length) {  // 将左侧游标走完
			mergeArray[mergeCursor] = leftArray[leftCursor];
			leftCursor++;
			mergeCursor++;
		}
		while (rightCursor < rightArray.length) {  // 将右侧游标走完
			mergeArray[mergeCursor] = rightArray[rightCursor];
			rightCursor++;
			mergeCursor++;
		}
		return mergeArray;  // 返回合并数组
	}
	
	public static void main(String[] args) {
		MergeSort ms = new MergeSort();
		int[] array = {54,8,9,84,71,6,31,20,15,80,94,2,17,22,28,98,21,30};
		int[] resArray = ms.mergeSort(array, 0, array.length - 1);
		
		for (int i : resArray) {
			System.out.print(i + "  ");
		}
	}
}
# 算法 # 手撕 # 归并排序
手撕快速排序-Java代码
分治算法
  • 文章目录
  • 站点概览
优律

优律

萤火小屋分享世界

34 日志
13 分类
33 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
  • 崔笑颜的博客
  • 大耗子的小屋
0%
© 2019 — 2021 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持