侧边栏壁纸
博主头像
孔子说JAVA博主等级

成功只是一只沦落在鸡窝里的鹰,成功永远属于自信且有毅力的人!

  • 累计撰写 285 篇文章
  • 累计创建 125 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

java排序算法之归并排序

孔子说JAVA
2019-10-27 / 0 评论 / 0 点赞 / 65 阅读 / 2,168 字 / 正在检测是否收录...

1、排序算法概述

常用的内部排序方法有:交换排序(冒泡排序、快速排序)、选择排序(简单选择排序、堆排序)、插入排序(直接插入排序、希尔排序)、归并排序、基数排序(一关键字、多关键字)。

  • 所需辅助空间最多:归并排序
  • 所需辅助空间最少:堆排序
  • 平均速度最快:快速排序
  • 不稳定:快速排序,希尔排序,堆排序。

选择排序算法的依据:任何排序算法在数据量小的时候基本体现不出来差距。选择依据有:

  • 1.数据的规模 :当数据规模较小时,选择直接插入排序或冒泡排序。
  • 2.数据的类型 :如全部是正整数,那么考虑使用桶排序为最优。
  • 3.数据已有的顺序 :快排是一种不稳定的排序(当然可以改进),对于大部分排好的数据,快排会浪费大量不必要的步骤。

数据量极小,而且已经基本排好序,冒泡是最佳选择。我们说快排好,是指大量随机数据下,快排效果最理想。而不是所有情况。

2、归并排序时空复杂度

最好最差时间复杂度均为O(nlogn),平均时间复杂度O(nlogn),空间复杂度O(n),是一种稳定的排序算法。

  • 时间复杂度:对长度为n的文件,需进行趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlogn)。

  • 空间复杂度:需要一个辅助向量来暂存两有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序。

3、归并排序原理

归并排序 (merge sort) 是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序、两路归并排序 , 可用于内排序,也可以用于外排序。

  • 归并排序是一种概念上最简单的排序算法,与快速排序一样,归并排序也是基于分治法的。归并排序将待排序的元素序列分成两个长度相等的子序列,为每一个子序列排序,然后再将他们合并成一个子序列。合并两个子序列的过程也就是两路归并。

4、归并排序思路

分而治之(divide - conquer);每个递归过程涉及三个步骤:

  • 第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素。
  • 第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作。
  • 第三, 合并: 合并两个排好序的子序列,生成排序结果。

image-1649572493992

动图展示:

dda3419b93236a75bc559796345f95d1

5、归并排序举例说明

1.归并排序的流程:

image-1649572511853

2.合并两个有序数组的流程

image-1649572525033

6、归并排序代码

public class MergeSort {
	
	// 两路归并算法,两个排好序的子序列合并为一个子序列
	public static void merge(int[] a, int low, int mid, int high) {
		int[] tmp = new int[a.length];// 辅助数组
//		int[] tmp = new int[high-low+1];
		int p1 = low, p2 = mid + 1, k = low;// p1、p2是检测指针,k是存放指针
		// 把较小的数先移到新数组中
		while (p1 <= mid && p2 <= high) {
			tmp[k++] = a[p1] <= a[p2] ? a[p1++] : a[p2++];
		}
		// 上面的循环退出后,把剩余的元素依次填入到temp中
	    // 以下两个while只有一个会执行
		// 把左边剩余的数移入数组
		while (p1 <= mid) {
			tmp[k++] = a[p1++];// 如果第一个序列未检测完,直接将后面所有元素加到合并的序列中
		}
		// 把右边边剩余的数移入数组
		while (p2 <= high) {
			tmp[k++] = a[p2++];// 同上
		}
		// 复制回原数组  // 把新数组中的数覆盖nums数组
		for (int i = low; i <= high; i++) {
			a[i] = tmp[i];
		}
	}

	public static void mergeSort(int[] a, int start, int end) {
		if (start < end) {// 当子序列中只有一个元素时结束递归
//			int mid = (start + end) / 2;// 划分子序列
			int mid = start + ((end - start) >> 1);
//			System.out.println(start+"-"+mid+"-"+end);
			mergeSort(a, start, mid);// 对左侧子序列进行递归排序
			mergeSort(a, mid + 1, end);// 对右侧子序列进行递归排序
			merge(a, start, mid, end);// 左右归并
		}
	}
	
	public static void main(String[] args) {
		int[] arr = { 6, 3, 8, 2, 9, 1,7,4 };
		System.out.print("排序前的数组为:");
		for (int num : arr) {
			System.out.print(num + " ");
		}
		mergeSort(arr, 0, arr.length-1);
		System.out.println();
		System.out.print("排序后的数组为:");
		for (int num : arr) {
			System.out.print(num + " ");
		}
	}
}

// 排序前的数组为:6 3 8 2 9 1 7 4 
// 排序后的数组为:1 2 3 4 6 7 8 9 
0

评论区