归并排序（Java 实例代码）

╰半夏微凉° 2023-10-14 14:57 46阅读 0赞

**目录**

归并排序

一、概念及其介绍

二、适用说明

三、过程图示

四、Java 实例代码

MergeSort.java 文件代码：

--------------------

## 归并排序 ##

#### 一、概念及其介绍 ####

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

#### 二、适用说明 ####

当有 n 个记录时，需进行 logn 轮归并排序，每一轮归并，其比较次数不超过 n，元素移动次数都是 n，因此，归并排序的时间复杂度为 O(nlogn)。归并排序时需要和待排序记录个数相等的存储空间，所以空间复杂度为 O(n)。

归并排序适用于数据量大，并且对稳定性有要求的场景。

#### 三、过程图示 ####

归并排序是递归算法的一个实例，这个算法中基本的操作是合并两个已排序的数组，取两个输入数组 A 和 B，一个输出数组 C，以及三个计数器 i、j、k，它们初始位置置于对应数组的开始端。

A\[i\] 和 B\[j\] 中较小者拷贝到 C 中的下一个位置，相关计数器向前推进一步。

当两个输入数组有一个用完时候，则将另外一个数组中剩余部分拷贝到 C 中。

![add76ec8445dc9babf908bd08acbd95f.png][]

自顶向下的归并排序，递归分组图示：

![6d22b099490e50d32b69e5fd3a8630c8.png][]

对第三行两个一组的数据进行归并排序

![73d5f7d6a162e7b58e932f0363e09639.png][]

对第二行四个一组的数据进行归并排序

![5806b4c7f6360b2a350d34438f273d0e.png][]

整体进行归并排序

![d0dcc732134177464db004f3bf407eeb.png][]

#### 四、Java 实例代码 ####

**源码包下载：**[Download![icon-default.png_t_N6B9][]https://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-merge-sort.zip][Download_icon-default.png_t_N6B9_https_www.runoob.com_wp-content_uploads_2020_09_runoob-algorithm-merge-sort.zip]

### MergeSort.java 文件代码： ###

public class MergeSort \{  
  
// 将arr\[l...mid\]和arr\[mid+1...r\]两部分进行归并  
private static void merge(Comparable\[\] arr, int l, int mid, int r) \{  
  
Comparable\[\] aux = Arrays.copyOfRange(arr, l, r + 1);  
  
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1  
int i = l, j = mid + 1;  
for (int k = l; k <= r; k++) \{  
  
if (i > mid) \{ // 如果左半部分元素已经全部处理完毕  
arr\[k\] = aux\[j - l\];  
j++;  
\} else if (j > r) \{ // 如果右半部分元素已经全部处理完毕  
arr\[k\] = aux\[i - l\];  
i++;  
\} else if (aux\[i - l\].compareTo(aux\[j - l\]) < 0) \{ // 左半部分所指元素 < 右半部分所指元素  
arr\[k\] = aux\[i - l\];  
i++;  
\} else \{ // 左半部分所指元素 >= 右半部分所指元素  
arr\[k\] = aux\[j - l\];  
j++;  
\}  
\}  
\}  
  
// 递归使用归并排序,对arr\[l...r\]的范围进行排序  
private static void sort(Comparable\[\] arr, int l, int r) \{  
if (l >= r) \{  
return;  
\}  
int mid = (l + r) / 2;  
sort(arr, l, mid);  
sort(arr, mid + 1, r);  
// 对于arr\[mid\] <= arr\[mid+1\]的情况,不进行merge  
// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失  
if (arr\[mid\].compareTo(arr\[mid + 1\]) > 0)  
merge(arr, l, mid, r);  
\}  
  
public static void sort(Comparable\[\] arr) \{  
  
int n = arr.length;  
sort(arr, 0, n - 1);  
\}  
  
// 测试MergeSort  
public static void main(String\[\] args) \{  
  
int N = 1000;  
Integer\[\] arr = SortTestHelper.generateRandomArray(N, 0, 100000);  
sort(arr);  
//打印数组  
SortTestHelper.printArray(arr);  
\}  
\}

[add76ec8445dc9babf908bd08acbd95f.png]: https://img-blog.csdnimg.cn/img_convert/add76ec8445dc9babf908bd08acbd95f.png
[6d22b099490e50d32b69e5fd3a8630c8.png]: https://img-blog.csdnimg.cn/img_convert/6d22b099490e50d32b69e5fd3a8630c8.png
[73d5f7d6a162e7b58e932f0363e09639.png]: https://img-blog.csdnimg.cn/img_convert/73d5f7d6a162e7b58e932f0363e09639.png
[5806b4c7f6360b2a350d34438f273d0e.png]: https://img-blog.csdnimg.cn/img_convert/5806b4c7f6360b2a350d34438f273d0e.png
[d0dcc732134177464db004f3bf407eeb.png]: https://img-blog.csdnimg.cn/img_convert/d0dcc732134177464db004f3bf407eeb.png
[icon-default.png_t_N6B9]: https://csdnimg.cn/release/blog_editor_html/release2.3.5/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N6B9
[Download_icon-default.png_t_N6B9_https_www.runoob.com_wp-content_uploads_2020_09_runoob-algorithm-merge-sort.zip]: https://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-merge-sort.zip