查看: 1829|回复: 0

神级基础排序——归并排序

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2020-3-30 17:02 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

神级基础排序——归并排序

归并排序的介绍

归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
概念

是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想

将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。

实现代码
import java.util.Arrays;

/**
* @Author god-jiang
* @date 2020/1/13
*/
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
public static void MergeSort(int[] arr, int start, int end) {
      //分治的结束条件
      if (start >= end) {
         return;
      }
      //保证不溢出取start和end的中位数
      int mid = start + ((end - start) >> 1);
      //递归排序并且合并
      MergeSort(arr, start, mid);
      MergeSort(arr, mid + 1, end);
      Merge(arr, start, mid, end);
}

//合并
public static void Merge(int[] arr, int start, int mid, int end) {
      int[] temp = new int[end - start + 1];
      int p1 = start;
      int p2 = mid + 1;
      int p = 0;
      while (p1 <= mid && p2 <= end) {
         if (arr[p1] > arr[p2]) {
            temp[p++] = arr[p2++];
         } else {
            temp[p++] = arr[p1++];
         }
      }
      while (p1 <= mid) {
         temp[p++] = arr[p1++];
      }
      while (p2 <= end) {
         temp[p++] = arr[p2++];
      }
      for (int i = 0; i < temp.length; i++) {
         arr[i + start] = temp;
7 w2 A7 @5 x9 G8 X, j       }2 W2 ^' L, Y# v8 r% Q5 G. a
}
# A. Q& m% P; x/ ^  h* l" O6 ]3 ]: a7 D* `1 t2 T9 L
public static void main(String[] args) {
: k% E, M  Q/ T" m+ ~0 T7 e       int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};! T) ]  m( b8 I$ e# X$ w
      MergeSort(a, 0, a.length - 1);/ {0 K+ p( G2 l
      System.out.println(Arrays.toString(a));) e! p9 o* c4 s8 e1 [
}
' @, [3 |3 r( w! _+ L0 S}7 w( p9 Q/ w& f% B* z6 v4 m/ q6 f
" p$ G4 h  |* [" X
3 ^- O2 E. w! h& n3 \5 k" I) M% b
运行截图
( e" x+ R) A5 y% h" ~, z$ a$ A
5 w1 I! t% e0 [) Y7 C

2020-3-30 17:02 上传
下载附件 (89.18 KB)

% `% _7 I% |. R$ Q4 A: v9 O' a  F/ P/ o  L4 v
1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
$ g! Y& s4 w. R, h: U' A2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
* ?- U% G! _2 q。
) |7 `; M9 ~4 ]; C3 J原文链接：https://blog.csdn.net/weixin_37686415/article/details/1051800358 s, l6 d$ L. W; W
. M5 [$ ~% x  v* e

4 D, D. G7 o7 B/ `% A1 s