X Tutup
Skip to content

Commit aec2855

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

File tree

5 files changed

+472
-0
lines changed

5 files changed

+472
-0
lines changed

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

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -109,4 +109,35 @@ public static <T extends Comparable<T>> void testSort(String sortClassName, T[]
109109
e.printStackTrace();
110110
}
111111
}
112+
113+
114+
/**
115+
* 测试sortClassName所对应的排序算法排序arr数组所得到结果的正确性和算法运行时间
116+
* @param sortClassName
117+
* @param arr
118+
*/
119+
public static <T extends Comparable<T>> void testSort(String sortClassName, String methodName ,T[] arr){
120+
121+
// 通过Java的反射机制，通过排序的类名，运行排序函数
122+
try{
123+
// 通过sortClassName获得排序函数的Class对象
124+
Class sortClass = Class.forName(sortClassName);
125+
// 通过排序函数的Class对象获得排序方法
126+
Method sortMethod = sortClass.getMethod(methodName,new Class[]{Comparable[].class});
127+
// 排序参数只有一个，是可比较数组arr
128+
Object[] params = new Object[]{arr};
129+
130+
long startTime = System.currentTimeMillis();
131+
// 调用排序函数
132+
sortMethod.invoke(null,params);
133+
long endTime = System.currentTimeMillis();
134+
//判断是否有序
135+
assert isSorted( arr );
136+
137+
System.out.println( sortClass.getSimpleName()+"类方法:"+methodName+"消耗时间: " + (endTime-startTime) + "ms" );
138+
}
139+
catch(Exception e){
140+
e.printStackTrace();
141+
}
142+
}
112143
}

‎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
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
package com.zejian.structures.Sort.Sort_NLogN;
2+
3+
import com.zejian.structures.Sort.Sort_N_2.InsertionSort;
4+
5+
/**
6+
* Created by zejian on 2018/2/13.
7+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
8+
* 自底向上的归并排序算法
9+
* 自底向上的归并排序算法的思想就是数组中先一个一个归并成两两有序的数组，
10+
* 两两有序的数组归并成四个四个有序的数组，然后四个四个有序的序列归并八
11+
* 个八个有序的数组，以此类推，直到，归并的长度大于整个数组的长度，此时
12+
* 整个数组有序。需要注意的是数组按照归并长度划分，最后一个子数组可能不
13+
* 满足长度要求，这种情况需要注意。自顶下下的归并排序算法一般用递归
14+
* 来实现，而自底向上可以用循环来实现。
15+
* ∧
16+
* [1 2 3 4 5 6 7 8] ‖上 最后合并成一个有序数组
17+
* [1 2 5 8] [3 4 6 7] ‖向 再归并成四四分组
18+
* [5 8] [1 2] [6 7] [3 4] ‖底 先按两两分组,然后排序
19+
* [8] [5] [1] [2] [7] [6] [3] [4] ‖自 一一分组然后归并
20+
* [8 5 1 2 7 6 3 4] ‖ 未分组
21+
*
22+
*/
23+
public class MergeSortBottomUp {
24+
25+
26+
public static <T extends Comparable<T>> void sort(T[] array){
27+
assert array != null;
28+
int len = array.length;
29+
//分组循环排序,sz表示每组分组的个数,第一轮分组数组个数为1
30+
for (int sz = 1; sz < len ; sz += sz) {
31+
//对分组进行两两归并
32+
//由于每次归并的是两个分组个数,所以归并的间隔是 sz + sz = 2 * sz
33+
for (int i = 0; i < len ; i += 2*sz) {
34+
//i+sz 代表分组的下标最大值,由于下标从0开始,所以需要i+sz-1
35+
//用于归并的第二组起始点是i+sz,结束点:i + sz - 1 + sz
36+
//对array[i....i+sz-1] 和 array[i+sz.....i+sz+sz-1]进行归并
37+
int l = i;
38+
int mid = i+sz-1;
39+
int r = i+sz+sz-1;
40+
//进行合并操作,Math.min(r,len-1)防止数组越界,存在最后一个分组不符合整数的情况
41+
MergeSort.merge(array,l,mid,Math.min(r,len-1));
42+
}
43+
}
44+
}
45+
46+
/**
47+
* 优化版
48+
* @param array
49+
* @param <T>
50+
*/
51+
public static <T extends Comparable<T>> void sortOptimize(T[] array){
52+
assert array != null;
53+
int len = array.length;
54+
55+
//优化: 对于小数组, 使用插入排序优化sz是分组的大小
56+
for( int sz = 0 ; sz < len ; sz += 16 ){
57+
//Math.min(i+16-1,len-1)防止数组越界,存在最后一个分组不符合整数的情况
58+
InsertionSort.sort(array,sz,Math.min(sz+16-1,len-1));
59+
}
60+
61+
//分组循环排序,sz表示每组分组的个数,第一轮分组数组个数为1
62+
for (int sz = 16; sz < len ; sz += sz) {
63+
//对分组进行两两归并
64+
//由于每次归并的是两个分组个数,所以归并的间隔是 sz + sz = 2 * sz
65+
for (int i = 0; i < len ; i += 2*sz) {
66+
//i+sz 代表分组的下标最大值,由于下标从0开始,所以需要i+sz-1
67+
//用于归并的第二组起始点是i+sz,结束点:i + sz - 1 + sz
68+
//对array[i....i+sz-1] 和 array[i+sz.....i+sz+sz-1]进行归并
69+
int l = i;
70+
int mid = i+sz-1;
71+
int r = i+sz+sz-1;
72+
/**
73+
* 优化:对于arr[mid] <= arr[mid+1]的情况,不进行merge
74+
*/
75+
if(array[mid].compareTo(array[mid+1]) > 0) {
76+
//进行合并操作
77+
MergeSort.merge(array, l, mid, Math.min(r, len - 1));
78+
}
79+
}
80+
}
81+
}
82+
83+
84+
/**
85+
* Test
86+
* @param args
87+
*/
88+
public static void main(String[] args) {
89+
Integer[] arr = {10,9,8,7,6,5,4,3,2,1};
90+
MergeSortBottomUp.sortOptimize(arr);
91+
for( int i = 0 ; i < arr.length ; i ++ ){
92+
System.out.print(arr[i]);
93+
System.out.print(' ');
94+
}
95+
System.out.println();
96+
}
97+
98+
99+
100+
}

0 commit comments

Comments
 (0)
X Tutup