时间复杂度为N*LogN级别的的排序算法-归并排序和普通快速排序算法 · QQldd2019/javaStructures@aec2855 · GitHub
Skip to content

Commit aec2855

Browse files
shinezejianshinezejian
committed
时间复杂度为N*LogN级别的的排序算法-归并排序和普通快速排序算法
1 parent e53d182 commit aec2855

5 files changed

Lines changed: 472 additions & 0 deletions

File tree

‎src/com/zejian/structures/Sort/SortTestHelper.java‎

Lines changed: 31 additions & 0 deletions

‎src/com/zejian/structures/Sort/Sort_NLogN/MergeSort.java‎

Lines changed: 205 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,205 @@
1+
package com.zejian.structures.Sort.Sort_NLogN;
2+
3+
import com.zejian.structures.Sort.SortTestHelper;
4+
import com.zejian.structures.Sort.Sort_N_2.InsertionSort;
5+
6+
import java.lang.reflect.Array;
7+
import java.util.Arrays;
8+
9+
/**
10+
* Created by zejian on 2018/2/12.
11+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
12+
* 归并排序算法,采用的是分而治之的策略.其核心思想是先把要排序的数组元素不断得进行一分为二,
13+
* 直到每个分组只有一个元素时,由于该分组只有一个元素就本身就是有序的数组,然后再将有序的数组
14+
* 两两合并为新的有序数组,合并完成后如果还有分组就重复前面的操作将有序数组再次合并为新的有
15+
* 序数组,直到合并为一个数组为止.最终数组就是有序数组.如下演示:
16+
* 8 5 1 2 7 6 3 4 其中l=0 r=7 , mid=(l+r)/2 =3
17+
* 根据下标3分为两组: [8 5 1 2] [7 6 3 4]
18+
*
19+
* 注意:先处理左边分组(继续分组操作直到分组的元素个数为1)
20+
* [8 5 1 2] ==> L=0 R=3 mid=(l+r)/2=1
21+
* [8 5] [1 2]
22+
* [8 5] ==> L=0 R=1 mid=0;
23+
* [8] [5] ==> L=0 R=0 L>=R 分组结束
24+
* 对有序数组[8] [5]进行归并[5 8]
25+
* [1 2] ==> L=2 R=3 mid=2
26+
* [1] [2] ==> L=2 R=2 L>=R 分组结束
27+
* 对有序数组[1] [2]进行归并[1 2]
28+
* 再对有序数组[5 8] [1 2]进行合并[1 2 5 8]
29+
* 左边最终处理结果:[1 2 5 8]
30+
*
31+
* 再处理右边分组
32+
* [7 6 3 4] ==> L=4 R=7 mid=5
33+
* [7 6] [3 4]
34+
* [7 6] ==> L=4 R=5 mid=4
35+
* [7] [6] ==> L=4 R=4 L>=R分组结束
36+
* 合并有序数组[7] [6] => [6 7]
37+
* 同理: [3] [4] => [3 4]
38+
* 合并有序数组[6 7] [3 4] ==> [3 4 6 7]
39+
* 右边处理完成
40+
*
41+
* 最终合并有序数组[1 2 5 8] 和 [3 4 6 7]
42+
* [1 2 3 4 5 6 7 8]
43+
*
44+
*
45+
* 归并排序时间复杂度分析:
46+
* 对于数组进行分组直到数组元素个数为1,采用的是类似与二叉树查找的操作,因此假设数组元素个数为N,
47+
* 那么N个元素分组后最多有 ㏒N 层.由于每层分组后最终都需要对数组执行归并操作,而每层处理的归并
48+
* 操作(该操作就是让数组中元素交换位置)总元素是是固定的为N.
49+
* 因此归并排序的时间复杂度为 N * ㏒N
50+
*
51+
* [8 5 1 2 7 6 3 4]
52+
* 1层 [8 5 1 2] [7 6 3 4]
53+
* 2层 [8 5] [1 2] [7 6] [3 4]
54+
* 3层 [8] [5] [1] [2] [7] [6] [3] [4]
55+
* 执行归并操作
56+
* [5 8] [1 2] [6 7] [3 4] 每次归并操作元素个数为N
57+
* [1 2 5 8] [3 4 6 7]
58+
* [1 2 3 4 5 6 7 8]
59+
*
60+
*
61+
* 归并排序算法和快速排序算法是java.util.Arrays中使用的排序算。
62+
* 对于一般的基本数据类型，Arrays.sort函数使用双轴快速排序算法，
63+
* 而对于对象类型使用归并排序（准确的说使用的是TimSort排序算法，
64+
* 它是归并排序的优化版本）。这样做的原因有两点
65+
* 第一个原因，归并排序是稳定的而快速排序不是稳定的。
66+
* 第二个原因，对于基本数据类型，排序的稳定性意义不大，
67+
* 但对于复合数据类型（比如对象）排序的稳定性就能帮助我们保持排序结果的某些性质。
68+
*
69+
*/
70+
public class MergeSort {
71+
72+
/**
73+
* 未优化版归并排序
74+
* @param array
75+
* @param <T>
76+
*/
77+
public static <T extends Comparable<T>> void sort(T[] array){
78+
assert array != null;
79+
int n = array.length;
80+
mergeSort(array,0,n-1);
81+
}
82+
83+
/**
84+
* 优化版归并排序
85+
* @param array
86+
* @param <T>
87+
*/
88+
public static <T extends Comparable<T>> void sortOptimize(T[] array){
89+
assert array != null;
90+
int n = array.length;
91+
mergeSortOptimize(array,0,n-1);
92+
}
93+
94+
95+
/**
96+
* 归并排序算法优化版
97+
*/
98+
private static <T extends Comparable<T>> void mergeSortOptimize(T[] array ,int l , int r){
99+
100+
// 优化: 对于小规模数组, 使用插入排序,在较小的数据范围内,数据近乎有序
101+
// 可能性非常,采用插入排序能提高效率
102+
if( r - l <= 15 ){
103+
InsertionSort.sort(array, l, r);
104+
return;
105+
}
106+
107+
//计算分组间距
108+
int mid = l + (r - l)/2;
109+
110+
//递归分组
111+
mergeSort(array,l,mid);
112+
mergeSort(array,mid+1,r);
113+
114+
/**
115+
* 优化: 对于arr[mid] <= arr[mid+1]的情况,不进行merge
116+
* 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
117+
*/
118+
if( array[mid].compareTo(array[mid+1]) > 0 ) {
119+
//两边都分组完成即分组后数组元素只有一个后开始合并
120+
merge(array, l, mid, r);
121+
}
122+
}
123+
124+
/**
125+
* 归并排序算法(未优化版)
126+
* @param array
127+
* @param l
128+
* @param r
129+
* @param <T>
130+
*/
131+
private static <T extends Comparable<T>> void mergeSort(T[] array ,int l , int r){
132+
//递归结束条件(分组后数组只有一个元素时不再分组)
133+
if(l>=r){
134+
return;
135+
}
136+
137+
//计算分组间距
138+
int mid = l + (r - l)/2;
139+
140+
//递归分组
141+
mergeSort(array,l,mid);
142+
mergeSort(array,mid+1,r);
143+
//两边都分组完成即分组后数组元素只有一个后开始合并
144+
merge(array, l, mid, r);
145+
}
146+
147+
/**
148+
* 合并函数
149+
* @param array
150+
* @param l
151+
* @param mid
152+
* @param r
153+
* @param <T>
154+
*/
155+
public static <T extends Comparable<T>> void merge(T[] array , int l , int mid , int r){
156+
int len = r-l+1;
157+
//创建临时数据辅助归并
158+
T[] temp = (T[]) Array.newInstance(array.getClass().getComponentType(),len);
159+
//把需要归并的元素全赋值给temp;
160+
for(int i=l ; i <= r ; i++){
161+
temp[i-l] = array[i];
162+
}
163+
164+
int i = l;
165+
int j = mid+1;
166+
//执行归并操作(O(N)级别)
167+
for(int k=l ; k <= r ; k++){
168+
if(i > mid){ //说明左边的元素已全部归并完成
169+
array[k] = temp[j-l];
170+
j++;
171+
}else if(j > r){ //说明右边的元素已全部归并完成
172+
array[k] = temp[i-l];
173+
i++;
174+
}else if(temp[i-l].compareTo(temp[j-l]) > 0){//左边的元素大于右边
175+
array[k] = temp[j-l];
176+
j++;
177+
}else if(temp[i-l].compareTo(temp[j-l]) < 0){ //右边的元素大于左边
178+
array[k] = temp[i-l];
179+
i++;
180+
}
181+
}
182+
}
183+
184+
public static void main(String[] args) {
185+
//
186+
// Integer[] arr = {10,9,8,7,6,5,4,3,2,1};
187+
// MergeSort.sort(arr);
188+
// for( int i = 0 ; i < arr.length ; i ++ ){
189+
// System.out.print(arr[i]);
190+
// System.out.print(' ');
191+
// }
192+
// System.out.println();
193+
194+
//对于近乎有序的数组,优化后的归并排序效率更高
195+
int N = 200000;
196+
Integer[] arr1 = SortTestHelper.generateNearlyOrderedArray(N, 4);
197+
Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);
198+
199+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.MergeSort","sort", arr1);
200+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.MergeSort","sortOptimize",arr2);
201+
202+
}
203+
204+
205+
}

‎src/com/zejian/structures/Sort/Sort_NLogN/MergeSortBottomUp.java‎

Lines changed: 100 additions & 0 deletions

0 commit comments

Comments
 (0)