Skip to content

Commit f45c511

Browse files
shinezejianshinezejian
committed
时间复杂度为N*LogN级别的的排序算法-双路快速排序和三路快速排序
1 parent aec2855 commit f45c511

5 files changed

Lines changed: 329 additions & 21 deletions

File tree

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

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package com.zejian.structures.Sort.Sort_NLogN;
2+
3+
import com.zejian.structures.Sort.SortTestHelper;
4+
5+
import java.util.Arrays;
6+
7+
/**
8+
* Created by zejian on 2018/2/12.
9+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
10+
* 测试归并排序,普通快速排序 双路快速排序 三路快速排序的性能效率
11+
*
12+
*/
13+
public class MainTest {
14+
15+
public static void main(String[] args) {
16+
17+
int N = 200000;
18+
19+
// 测试1 一般测试
20+
System.out.println("测试随机无序的数组, size = " + N + " , random range [0, " + N + "]");
21+
22+
Integer[] arr1 = SortTestHelper.generateRandomArray(N, 0, N);
23+
Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);
24+
Integer[] arr3 = Arrays.copyOf(arr1, arr1.length);
25+
Integer[] arr4 = Arrays.copyOf(arr1, arr1.length);
26+
27+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.MergeSort","sortOptimize",arr1);
28+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.QuickSort","sort",arr2);
29+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.QuickSort2Ways","quickSort2Ways",arr3);
30+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.QuickSort3Ways","quickSort3Ways",arr4);
31+
32+
System.out.println();
33+
34+
35+
// 测试2 有序性更强的测试
36+
System.out.println("测试存在大量重复元素的数组排序, size = " + N + " , random range [0,3]");
37+
38+
arr1 = SortTestHelper.generateRandomArray(N, 0, 3);
39+
arr2 = Arrays.copyOf(arr1, arr1.length);
40+
arr3 = Arrays.copyOf(arr1, arr1.length);
41+
arr4 = Arrays.copyOf(arr1, arr1.length);
42+
43+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.MergeSort","sortOptimize",arr1);
44+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.QuickSort","sort",arr2);
45+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.QuickSort2Ways","quickSort2Ways",arr3);
46+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.QuickSort3Ways","quickSort3Ways",arr4);
47+
48+
System.out.println();
49+
50+
51+
// 测试3 测试近乎有序的数组
52+
int swapTimes = 100;
53+
System.out.println("测试近乎有序的数组的数组排序, size = " + N + " , swap time = " + swapTimes);
54+
55+
arr1 = SortTestHelper.generateNearlyOrderedArray(N, swapTimes);
56+
arr2 = Arrays.copyOf(arr1, arr1.length);
57+
arr3 = Arrays.copyOf(arr1, arr1.length);
58+
arr4 = Arrays.copyOf(arr1, arr1.length);
59+
60+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.MergeSort","sortOptimize",arr1);
61+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.QuickSort","sort",arr2);
62+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.QuickSort2Ways","quickSort2Ways",arr3);
63+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.QuickSort3Ways","quickSort3Ways",arr4);
64+
65+
}
66+
}

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

Lines changed: 9 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
package com.zejian.structures.Sort.Sort_NLogN;
22

33
import com.zejian.structures.Sort.SortTestHelper;
4+
import com.zejian.structures.Sort.Sort_N_2.InsertionSort;
45

56
import java.util.Arrays;
67

@@ -42,15 +43,15 @@ public static <T extends Comparable<T>> void sort(T[] arr){
4243
*/
4344
public static <T extends Comparable<T>> void quickSort(T[] arr,int l,int r){
4445
//如果排序的数组元素个数少于16直接使用插入排序即可(优化点)
45-
// if(r-l < 16){
46-
// InsertionSort.sort(arr,l,r);
47-
// return;
48-
// }
49-
50-
if (l >= r){
46+
if(r-l < 16){
47+
InsertionSort.sort(arr,l,r);
5148
return;
5249
}
5350

51+
// if (l >= r){
52+
// return;
53+
// }
54+
5455
//获取分区的基准点的数组下标p
5556
int p = partition(arr,l,r);
5657
//使用递归的方式继续进行分区
@@ -90,7 +91,7 @@ private static <T extends Comparable<T>> int partition(T[] arr,int l ,int r){
9091
}
9192

9293

93-
private static <T extends Comparable<T>> void swap(T[] arr, int i, int j) {
94+
public static <T extends Comparable<T>> void swap(T[] arr, int i, int j) {
9495
T t = arr[i];
9596
arr[i] = arr[j];
9697
arr[j] = t;
@@ -106,7 +107,7 @@ public static void main(String[] args) {
106107
System.out.println();
107108

108109
//对于近乎有序的数组,优化后的归并排序效率更高
109-
int N = 200000;
110+
int N = 2000;
110111
Integer[] arr1 = SortTestHelper.generateNearlyOrderedArray(N, 4);
111112
Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);
112113
Integer[] arr3 = Arrays.copyOf(arr1, arr1.length);

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

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
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.util.Arrays;
7+
8+
/**
9+
* Created by zejian on 2018/2/14.
10+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
11+
* 双路快速排序算法:主要解决排序数据中存在大量重复值的情景,因为这种情况下使用前面实现
12+
* 的普通快速排序,会把等于v的元素归到 >=v 一方 而造成 < v 的一方数据过少
13+
* arr[l....j] < v 而 [j+1 ... r] >= v [j+1 ... r]包含大量重复的v元素
14+
* 从而造成分区时树结构失去平衡性,最终可能使普通快速排序由 N*logN 退化为 O(N²)
15+
*
16+
* 双路快速排序就是为了解决该问题而出现的.其基本思路与普通快速排序不同,
17+
* 其将分区设置为 arr[l+1...i) <= v; arr(j...r] >= v
18+
* 这样的话无论是小于v的左侧数组还是大于v的右侧数组都包含了等于v的情况,在这种情况下
19+
* 即使出现了大量重复元素,也不会导致左右两边分区的数组元素个数差距过大,造成排序性能
20+
* 效率过低.
21+
* 缺点是重复元素值仍会被交换位置.
22+
*
23+
* 时间复杂度依然是 N*logN 级别
24+
*
25+
*
26+
*/
27+
public class QuickSort2Ways {
28+
29+
/**
30+
* 双路快速排序
31+
* @param arr
32+
* @param <T>
33+
*/
34+
public static <T extends Comparable<T>> void quickSort2Ways(T[] arr){
35+
assert arr !=null;
36+
int len = arr.length;
37+
quickSort2Ways(arr,0,len-1);
38+
}
39+
40+
private static <T extends Comparable<T>> void quickSort2Ways(T[] arr , int l , int r){
41+
// //优化:数组个数小于16使用插入排序进行
42+
if(r-l < 16){
43+
InsertionSort.sort(arr,l,r);
44+
return;
45+
}
46+
if( l >= r){
47+
return;
48+
}
49+
50+
//计算并获取基准点的下标
51+
int p = partition(arr,l,r);
52+
//继续递归执行
53+
quickSort2Ways(arr,l,p-1);
54+
quickSort2Ways(arr,p+1,r);
55+
56+
}
57+
58+
/**
59+
* 双路快速排序的分区采用不同的分区思路
60+
* @return
61+
*/
62+
private static <T extends Comparable<T>> int partition(T[] arr , int l , int r){
63+
64+
//随机选取一个基准点并与最左侧位置的元素交换
65+
QuickSort.swap(arr,l,(int)(Math.random()*(r - l))+l);
66+
67+
//获取基准点
68+
T e = arr[l];
69+
70+
//下标从l+1开始
71+
int i = l+1; //arr[l+1 ... i) <= v
72+
int j = r; //arr(j...r] >= v
73+
74+
//进行分区操作
75+
while (true){
76+
//如果当前元素比基准点元素v小,不动,继续循环直到找到比较v大的停止
77+
while ( i <= r && arr[i].compareTo(e) < 0) i++;
78+
//如果当前元素比基准点元素v大,不动,继续循环直到找到比较v小的停止
79+
while ( j > l && arr[j].compareTo(e) > 0) j--;
80+
81+
//如果此时i>j说明已分区完成
82+
if(i > j){
83+
break;
84+
}
85+
86+
//交换i与j的元素
87+
QuickSort.swap(arr,i,j);
88+
i++;
89+
j--;
90+
}
91+
92+
93+
//最后交换基准元素的位置,这里之所以使用j,是因为上述while结束时,i>j
94+
//此时左侧分区j肯定是 arr[l+1...j] 而右侧分区肯定是arr[i...r]
95+
QuickSort.swap(arr,l,j);
96+
97+
return j;
98+
}
99+
100+
101+
public static void main(String[] args) {
102+
// Integer[] arr = {10,9,8,7,6,5,4,3,2,1};
103+
// QuickSort2Ways.quickSort2Ways(arr);
104+
// for( int i = 0 ; i < arr.length ; i ++ ){
105+
// System.out.print(arr[i]);
106+
// System.out.print(' ');
107+
// }
108+
// System.out.println();
109+
110+
//对于近乎有序的数组,优化后的归并排序效率更高
111+
int N = 200000;
112+
Integer[] arr1 = SortTestHelper.generateNearlyOrderedArray(N, 4);
113+
Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);
114+
Integer[] arr3 = Arrays.copyOf(arr1, arr1.length);
115+
Integer[] arr4 = Arrays.copyOf(arr1, arr1.length);
116+
System.out.println("处理近乎有序的数组:");
117+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.MergeSort","sortOptimize",arr1);
118+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.QuickSort","sort",arr2);
119+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.QuickSort2Ways","quickSort2Ways",arr3);
120+
121+
122+
123+
}
124+
125+
}

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

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
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.util.Arrays;
7+
8+
/**
9+
* Created by zejian on 2018/2/14.
10+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
11+
* 三路快速排序算法:也是为了解决排序元素中存在大规模重复元素的问题.只不过三路排序算法比
12+
* 双路快速排序算法性能更佳,因为针对于重复元素,三路快速排序不会再次进行交换位置或者纳入
13+
* 下一轮快速排序中.
14+
* 算法核心思想是把需要排序的数组分成3部分,分别是
15+
* arr[l+1 ... lt] arr[v,v,v,v,v,v...] arr[gt ... r]
16+
* 经过一轮分区后,再下一轮中只对arr[l+1 ... lt] 和 arr[gt ... r] 再次分区
17+
* 这样对于大量重复元素就无需处理,可以优化不少性能消耗
18+
*
19+
* 时间复杂度仍是 N*logN
20+
*
21+
* 三路快速排,无论是在大量重复元素的数据或者随机无序的大规模的数据或者近乎有序的大规模数据
22+
* 都能表现高效的处理优势.
23+
*/
24+
public class QuickSort3Ways {
25+
26+
public static <T extends Comparable<T>> void quickSort3Ways(T[] arr) {
27+
assert arr != null;
28+
int len = arr.length;
29+
quickSort3Ways(arr,0,len-1);
30+
}
31+
32+
33+
public static <T extends Comparable<T>> void quickSort3Ways(T[] arr, int l, int r) {
34+
//优化
35+
if( r-l < 16){
36+
InsertionSort.sort(arr,l,r);
37+
return;
38+
}
39+
40+
// if( l >= r){
41+
// return;
42+
// }
43+
44+
//partition
45+
46+
//随机选取一个基准点并与最左侧位置的元素交换
47+
QuickSort.swap(arr,l,(int)(Math.random()*(r - l))+l);
48+
49+
//获取基准点
50+
T e = arr[l];
51+
52+
int lt = l ; //arr[l+1 ... lt] < v
53+
int gt = r+1 ; //arr[gt ... r] > v
54+
int i = l+1; //arr[lt+1...i) == v
55+
//由于gt不断减少,gt右边是已分区好的元素,所以i<gt时才执行
56+
while (i < gt){
57+
//如果当前元素小于e,则把当前元素与lt+1位的元素交换
58+
if (arr[i].compareTo(e) < 0){
59+
QuickSort.swap(arr,i,lt+1);
60+
i++;
61+
lt++;
62+
}else if(arr[i].compareTo(e) > 0){
63+
QuickSort.swap(arr,i,gt-1);
64+
gt--;
65+
}else {// ==v 的情况不用操作
66+
i++;
67+
}
68+
}
69+
//交换基准的位置
70+
QuickSort.swap(arr,l,lt);
71+
72+
//递归进行三路快排
73+
quickSort3Ways(arr,l,lt-1);
74+
quickSort3Ways(arr,gt,r);
75+
76+
}
77+
78+
79+
80+
public static void main(String[] args) {
81+
// Integer[] arr = {10,9,8,7,6,5,4,3,2,1};
82+
// QuickSort3Ways.quickSort3Ways(arr);
83+
// for( int i = 0 ; i < arr.length ; i ++ ){
84+
// System.out.print(arr[i]);
85+
// System.out.print(' ');
86+
// }
87+
// System.out.println();
88+
89+
//对于近乎有序的数组,优化后的归并排序效率更高
90+
int N = 200000;
91+
Integer[] arr1 = SortTestHelper.generateNearlyOrderedArray(N, 4);
92+
Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);
93+
Integer[] arr3 = Arrays.copyOf(arr1, arr1.length);
94+
Integer[] arr4 = Arrays.copyOf(arr1, arr1.length);
95+
System.out.println("处理近乎有序的数组:");
96+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.MergeSort","sortOptimize",arr1);
97+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.QuickSort","sort",arr2);
98+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.QuickSort2Ways","quickSort2Ways",arr3);
99+
SortTestHelper.testSort("com.zejian.structures.Sort.Sort_NLogN.QuickSort3Ways","quickSort3Ways",arr4);
100+
101+
102+
103+
}
104+
}

‎src/com/zejian/structures/Sort/Sort_N_2/InsertionSort.java‎

Lines changed: 25 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -74,23 +74,35 @@ public static <T extends Comparable<T>> void sort(T[] array){
7474
}
7575

7676

77-
public static <T extends Comparable<T>> void sort(T[] array,int l , int r){
78-
assert array != null;
77+
// public static <T extends Comparable<T>> void sort(T[] array,int l , int r){
78+
// assert array != null;
79+
//
80+
// //从第2个元素开始
81+
// for (int i = l+1; i <=r ; i++) {
82+
// T e = array[i];//先记录要比较的元素,确定其交换的位置后再移动到对应位置
83+
// int j;//记录j,最后交换时使用
84+
// //更优雅的写法
85+
// //(array[j-1].compareTo(e) > 0)这个比较确保了发现前面没有更大元素就停止,这点与选择排序不同.
86+
// for (j = i; j > l && array[j-1].compareTo(e) > 0; j--) {
87+
// array[j] = array[j-1];
88+
// }
89+
// array[j] = e;
90+
// }
91+
// }
7992

80-
//从第2个元素开始
81-
for (int i = l+1; i <=r ; i++) {
82-
T e = array[i];//先记录要比较的元素,确定其交换的位置后再移动到对应位置
83-
int j;//记录j,最后交换时使用
84-
//更优雅的写法
85-
//(array[j-1].compareTo(e) > 0)这个比较确保了发现前面没有更大元素就停止,这点与选择排序不同.
86-
for (j = i; j > l && array[j-1].compareTo(e) > 0; j--) {
87-
array[j] = array[j-1];
88-
}
89-
array[j] = e;
93+
94+
// 对arr[l...r]的区间使用InsertionSort排序
95+
public static <T extends Comparable<T>> void sort(T[] arr, int l, int r){
96+
97+
for( int i = l + 1 ; i <= r ; i ++ ){
98+
T e = arr[i];
99+
int j = i;
100+
for( ; j > l && arr[j-1].compareTo(e) > 0 ; j--)
101+
arr[j] = arr[j-1];
102+
arr[j] = e;
90103
}
91104
}
92105

93-
94106
private static <T extends Comparable<T>> void swap(T[] arr, int i, int j) {
95107
T t = arr[i];
96108
arr[i] = arr[j];

0 commit comments

Comments
 (0)