查看: 1797|回复: 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;5 Y9 H+ }+ Z/ G2 E/ ]2 r
      }) k* @. s; d! A& C
}
9 Z0 ~! [) h) v8 C6 d% Z
% H9 X7 W/ P0 h' q! f public static void main(String[] args) {
; s6 \6 q& K- q, m/ g$ ?       int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
% |6 T5 ]* g4 q       MergeSort(a, 0, a.length - 1);0 J( C" u, b% B3 M/ s, [
      System.out.println(Arrays.toString(a));# r2 Q( V- _9 V# B
}
, h' i) B! U& @% n( r5 _+ L}
# O! R8 ]7 R, r  n
$ k3 Q8 Y7 a4 ?8 X) q  Z- X# y; Y+ |& X* p
运行截图* T" h1 g! n% W4 O7 ?+ n6 C. G
7 r( E+ p8 c8 s: Z. K1 i, @/ h

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

6 j0 [- `* o! S! F) M/ `2 {: M: g3 Q; G
1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
( D0 R# H$ J" k6 ]3 J2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到0 z  X7 e' D6 c" t$ N
。
原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035
+ z. U5 q1 D( ^. x; y
: ^1 {  G  x* Q( G
7 |7 t0 x! }8 K2 \* f; A