专栏首页码字搬砖一遍文章搞定归并排序-java版

一遍文章搞定归并排序-java版

1. 归并排序

1.1 归并排序的基本介绍

利用分治思想,将问题分成一些小的问题,然后递归求解

1.2 归并排序思想

1.3 归并排序的时间复杂度和空间复杂度等

算法名称

平均时间复杂度

最好情况

最坏情况

空间复杂度

稳定性

归并排序

O(nlogn)

O(nlogn)

O(nlogn)

O(n)

稳定

2. 代码演示

/**
 * @author shengjk1
 * @date 2020/4/11
 */
public class MergetSort {
	public static void main(String[] args) {
		int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
		int[] temp = new int[arr.length];
		mergeSort(arr, 0, arr.length - 1, temp);
		System.out.println(Arrays.toString(arr));
		
	}
	
	
	public static void mergeSort(int[] arr, int left, int right, int[] temp) {
		if (left < right) {
			System.out.println("mergerSort left:" + left + " right:" + right);
			int mid = (left + right) / 2;
			//向左递归
			mergeSort(arr, left, mid, temp);
			//向右递归
			mergeSort(arr, mid + 1, right, temp);
			//合并
			merge(arr, left, mid, right, temp);
		}
	}
	
	/**
	 * @param arr   原始数组
	 * @param left  要合并的数组的最左边
	 * @param mid   要合并的数组的中间
	 * @param right 要合并数组的最右边
	 * @param temp  临时数组
	 */
	public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
		System.out.println("merge    left:" + arr[left] + " right:" + arr[right]);
		//左边有序序列的初始索引
		int i = left;
		//右边有序序列的初始索引
		int j = mid + 1;
		//指向 temp 数组的当前索引
		int t = 0;
		
		//(一)
		//先把左右两边有序数据按照规则填充到 temp 数组中
		//知道左右两边的有序序列,有一边处理完毕为止
		while (i <= mid && j <= right) {
			//如果左边的有序序列的当前元素小于等于右边有序序列的当前元素
			//即将左边的当前元素填充到 temp 数组
			//然后自增
			if (arr[i] <= arr[j]) {
				temp[t] = arr[i];
				t++;
				i++;
			} else {
				temp[t] = arr[j];
				t++;
				j++;
			}
			
		}
		
		/*
		(二)
		把剩余数据的一边的数据依次全部填充到 temp 中
		 */
		while (i <= mid) {
			temp[t] = arr[i];
			t++;
			i++;
		}
		
		while (j <= right) {
			temp[t] = arr[j];
			t++;
			j++;
		}
		
		/*
		(三)
		将 temp 数组的元素拷贝到 arr
		注意,并不是每次都拷贝所有
		 */
		t = 0;
		int tempLeft = left;
		while (tempLeft <= right) {
			arr[tempLeft] = temp[t];
			t++;
			tempLeft++;
		}
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数组实现顺序存储二叉树

    shengjk1
  • 一遍文章搞定快排-java版

    首先将将要排序的数据分割成两组,其中一组的所有数据都要比另外一组的任何一个数据小,然后再按照此方法进行快速排序。

    shengjk1
  • 用大顶堆实现数据排序

    堆分为大顶堆和小顶堆 大顶堆 每个节点的值都大于或等于其左右孩子节点的值 小顶堆 每个节点的值都小于或等于其左右孩子节点的值

    shengjk1
  • 算法之常见排序算法-冒泡排序、归并排序、快速排序

    对于编程中琳琅满目的算法,本人向来是不善此道也不精于此的,而说起排序算法,也只是会冒泡排序。还记得当初刚做开发工作面试第一家公司时,面试官便让手写冒泡排序(入职...

    本人秃顶程序员
  • Java实现快速排序

    用户2436820
  • 快速排序填坑口诀

    快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此在很多笔试面试中出现的几率...

    KevinYan
  • 队列安排

    glm233
  • 前端排序算法实现

    前端迷
  • 程序员进阶之算法练习(三)

    前言 看完题目大意,先思考,再看解析;觉得题目大意不清晰,点击题目链接看原文。 A 题目链接 题目大意:n个数字,找出连续一串上升序列的长度。 代码实...

    落影
  • python下载网络图片文件到本地

    import urllib.request rsp=urllib.request.urlopen(“http://n.sinaimg.cn/ent/tra...

    葆宁

扫码关注云+社区

领取腾讯云代金券