/
MergeSort.java
122 lines (113 loc) · 3.85 KB
/
MergeSort.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
package com.github.anhTom2000.algorithm.sort;
import java.util.Arrays;
/**
* @author guang19
* @date 2020/5/2
* @description 归并排序
* @since 1.0.0
*/
public class MergeSort
{
public static void main(String[] args)
{
int[] arr = {3,5,0,-9,8,30,25,10,7,6};
/***
*
* 归并排序体现的也是一种分治的思想,它主要有两大核心思想: 分 , 并。
* 先将集合分成若干小的集合,然后将这些集合按照顺序合并成一个大的有序集合,不断的合并。
* 最终合并的集合就是一个有序的集合。
*
* 3 , 5 , 0 , -9 , 8 , 30 , 25 , 10 , 7 , 6
* 将集合分成2组
* left right
* [3 , 5 , 0 , -9 , 8] , [30 , 25 , 10 , 7 , 6]
* 再将这2组继续分组
* left right left right
* [3 , 5 , 0] [-9 , 8] , [30 , 25 , 10] , [7 , 6]
*
* left right left right left right left right
* [3,5] , [0] [-9] , [8] [30, 25] , [10] [7] , [6]
*
* left right left right
* [3], [5] [30] , [25]
*
*
* 然后将分组后的集合进行排序并归并:
* [3,5] [25,30]
*
* left right left right
* [0,3,5] , [-9,8] , [10,25,30] , [6,7]
*
* left right
* [-9,0,3,5,8] , [6,7,10,25,30]
*
* 继续合并:
* [-9,0,3,5,6,7,8,10,25,30]
*
* 归并排序的每次合并排序都需要借助一个临时数组,所以归并排序的过程是比较耗费空间的
*
*/
mergeSort(arr,0,arr.length - 1);
System.out.println("归并排序后的数组为: ");
System.out.println(Arrays.toString(arr));
}
//需要排序的数组,这个数组是整个递归过程中通用的
//left数组和right数组是虚拟的,就像上面演示的那样,他们是逻辑上存在的,需要依靠left和right下标区分界限
//left代表left数组的第一个元素的下标
//right代表right数组的最后一个元素的下标
public static void mergeSort(int[] array , int left , int right)
{
//这里设定最小分割条件,防止数组长度为1还分割
if(left < right)
{
//计算分割点
int mid = (left + right) >> 1;
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
//合并 , mid是left数组的最后一个元素的下标
merge(array, left,mid, right);
}
}
private static void merge(int[] array , int left , int mid,int right)
{
//创建临时数组,临时数组的长度就是right+1,因为right是right数组的最后一个元素的下标
int[] temp = new int[right + 1];
int l = left;
int m = mid + 1;
int tl = 0;
while (l <= mid && m <= right)
{
if(array[l] < array[m])
{
temp[tl] = array[l];
++tl;
++l;
}
else
{
temp[tl] = array[m];
++tl;
++m;
}
}
//如果left数组和right数组还有元素未被放入temp就再次遍历
while (l <= mid)
{
temp[tl] = array[l];
++tl;
++l;
}
while (m <= right)
{
temp[tl] = array[m];
++tl;
++m;
}
//将temp中的元素赋予array数组
tl = 0;
for (int i = left; i <= right ; ++i , ++tl)
{
array[i] = temp[tl];
}
}
}