归并排序-排序-算法

关注
归并排序-排序-算法www.shan-machinery.com 归并排序-排序-算法 目录

文章目录 1、前言2、算法3、Java代码实现4、算法时间复杂度分析***后记*** :

内容 1、前言

归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

2、算法 把长度为n的输入序列分成两个长度为n/2的子序列对这两个子序列分别采用归并排序(递归)将两个排序好的子序列合并成一个最终的排序序列 动图展示:[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LkyFa78M-1614521379775)(./images/merge.gif)] 3、Java代码实现

为统一和方便,我们这里的算法类为工具类,序列类型为Comparable[],代码如下:

package com.gaogzhen.algorithm.sort;/** * 归并排序 */public class Merge {private static Comparable[] assit;/** * 排序 * * @param a */public static void sort(Comparable[] a) {// 1、初始化辅助数组assit = new Comparable[a.length];// 2、定义lo,hi,分别记录数组最小索引和最大索引int lo = 0;int hi = a.length - 1;// 3、调用重载sort方法完成子数组索引冲Lo到hi的排序sort(a, lo, hi);}/** * 分组和归并 * 递归 * * @param a * @param lo * @param hi */public static void sort(Comparable[] a, int lo, int hi) {// 递归结束条件:hi>=loif (lo >= hi) {return;}// 1、确定分组中间量midint mid = lo + (hi - lo) / 2;// 2、拆分子数组// 2.1、调用sort完成子数组索引从lo->mid的排序sort(a, lo, mid);// 2.2、调用sort完成子数组索引从mid+1->hi的排序sort(a, mid + 1, hi);// 3、有序归并// 3.1、完成子数组2.1和2.2的归并merge(a, lo, mid, hi);}public static void merge(Comparable[] a, int lo, int mid, int hi) {// 1、初始化指针i,p1,p2int i = lo;int p1 = lo;int p2 = mid + 1;// 1.1、i为数组assit指针,p1为索引lo->mid子数组索引,p2为索引mid+1->hi子数组索引// 2、同时遍历2个子数组并比较,较小的存入assit,直至任意一个子数组结束while (p1 https://www.shan-machinery.com