Skip to content

Commit 8254fac

Browse files
coderbruiscoderbruis
committed
[A] 添加快排代码实现；添加两路、三路快排代码实现；
1 parent 9d23f23 commit 8254fac

5 files changed

Lines changed: 255 additions & 56 deletions

File tree

‎notes/algorithms/快速排序算法.md‎

Lines changed: 132 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -13,59 +13,145 @@
1313

1414
## 正文
1515

16-
### 1. 代码实现
16+
### 1. 普通版快速排序
1717

18+
此版本快速排序没有考虑特殊情况，为最简易版本。
19+
20+
参考代码如下：
1821
```
19-
private int partition2(int[] nums, int lt, int gt) {
20-
int p = nums[n];
21-
int j = lt;
22-
for(int i = lt; i <= gt; i++) {
23-
if(nums[i] < p) {
24-
swap(nums, ++j, i);
25-
}
26-
}
27-
swap(nums, lt, j);
28-
return j;
29-
}
22+
/**
23+
*
24+
* 快速排序
25+
*
26+
* @author LuoHaiYang
27+
*/
28+
public class QuickSort {
3029
31-
private int partition(int[] nums, int n, int m) {
32-
int p = nums[n];
33-
int j = n;
34-
int k = m + 1;
35-
int i = n + 1;
36-
while(i < k) {
37-
if(nums[i] < p) {
38-
swap(nums, ++j, i++);
39-
} else if(nums[i] > p) {
40-
swap(nums, --k, i);
41-
} else {// nums[i] == p
42-
i++;
43-
}
44-
}
45-
swap(nums, n, j);
46-
return j;
47-
}
48-
private void swap(int[] nums, int n, int m) {
49-
int tmp = nums[n];
50-
nums[n] = nums[m];
51-
nums[m] = tmp;
52-
}
53-
private void sort(int[] nums, int n, int m) {
54-
if(n > m) {
55-
return;
56-
}
57-
int p = partition(nums, n, m);
58-
sort(nums, n, p - 1);
59-
sort(nums, p + 1, m);
60-
}
61-
public void sort(int[] nums) {
62-
sort(nums, 0, nums.length);
63-
}
30+
/**
31+
* 对arr[left...right]部分进行partition操作
32+
* 返回p, 使得arr[left...p-1] < arr[p] ; arr[p+1...right] > arr[p]
33+
*
34+
* @param arr
35+
* @param left
36+
* @param right
37+
* @return
38+
*/
39+
private static int partition(int[] arr, int left, int right) {
40+
41+
int p = arr[left];
42+
43+
// arr[left+1...j] < p; arr[j+1...i) > p
44+
int j = left;
45+
for (int i = left + 1; i <= right; i++) {
46+
if (arr[i] < p) {
47+
j++;
48+
swap(arr, j, i);
49+
}
50+
}
51+
swap(arr, left, j);
52+
return j;
53+
}
54+
55+
private static void sort(int[] arr, int left, int right) {
56+
if (left >= right) {
57+
return;
58+
}
59+
int p = partition(arr, left, right);
60+
sort(arr, left, p-1);
61+
sort(arr, p+1, right);
62+
}
6463
64+
public static void sort(int[] arr) {
65+
int n = arr.length;
66+
sort(arr, 0, n-1);
67+
}
68+
69+
private static void swap(int[] arr, int i, int j) {
70+
int tmp = arr[i];
71+
arr[i] = arr[j];
72+
arr[j] = tmp;
73+
}
74+
}
6575
```
6676

6777
### 2. 快速排序算法的优化
6878

69-
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
79+
快速排序的最坏运行情况是 O(N^2)，比如说顺序数列的快排。但它的平摊期望时间是 O(NlogN)，且 O(NlogN) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
80+
81+
此处有两点可以进行优化。
82+
83+
1. 对于数组数小于15时，使用插入排序; 数据量较小时，插入排序效率跟高；
84+
2. 对于快速排序的基准值，取随机数，防止数组退化为顺序数组，即快速排序平均时间复杂度退化为O(N^2)
85+
86+
参考代码如下：
87+
```
88+
/**
89+
* 快速排序的优化
90+
*
91+
* 对于近乎有序的数组，快速排序会退化为O(N^2)。
92+
*
93+
* @author LuoHaiYang
94+
*/
95+
public class QuickSort2 {
96+
97+
/**
98+
* 对arr[left...right]部分进行partition操作
99+
* 返回p, 使得arr[left...p-1] < arr[p] ; arr[p+1...right] > arr[p]
100+
*
101+
* @param arr
102+
* @param left
103+
* @param right
104+
* @return
105+
*/
106+
private static int partition(int[] arr, int left, int right) {
107+
108+
//int p = arr[left];
109+
// ===================================== 优化2 =====================================
110+
// 避免快排退化为O(N^2)
111+
swap(arr, left, (int)Math.random()*(right - left + 1) + left);
112+
113+
int p = arr[left];
114+
115+
// arr[left+1...j] < p; arr[j+1...i) > p
116+
int j = left;
117+
for (int i = left + 1; i <= right; i++) {
118+
if (arr[i] < p) {
119+
j++;
120+
swap(arr, j, i);
121+
}
122+
}
123+
swap(arr, left, j);
124+
return j;
125+
}
126+
127+
private static void sort(int[] arr, int left, int right) {
128+
// ===================================== 优化1 =====================================
129+
// 如果左右数值小于15，则通过插入排序来进行排序
130+
if (right - left <= 15) {
131+
InsertionSort.sort(arr);
132+
return;
133+
}
134+
135+
int p = partition(arr, left, right);
136+
sort(arr, left, p-1);
137+
sort(arr, p+1, right);
138+
}
139+
140+
public static void sort(int[] arr) {
141+
int n = arr.length;
142+
sort(arr, 0, n-1);
143+
}
144+
145+
private static void swap(int[] arr, int i, int j) {
146+
int tmp = arr[i];
147+
arr[i] = arr[j];
148+
arr[j] = tmp;
149+
}
150+
}
151+
```
152+
153+
### 3. 双路快排
154+
155+
70156

71157
## 参考

‎src/main/java/com/bruis/algorithminjava/algorithm/sort/QuickSort.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -28,8 +28,8 @@ private static int partition(int[] arr, int left, int right) {
2828
j++;
2929
swap(arr, j, i);
3030
}
31-
swap(arr, left, j);
3231
}
32+
swap(arr, left, j);
3333
return j;
3434
}
3535

‎src/main/java/com/bruis/algorithminjava/algorithm/sort/QuickSort2.java‎

Lines changed: 6 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,8 @@
11
package com.bruis.algorithminjava.algorithm.sort;
22

33
/**
4-
*
54
* 快速排序的优化
65
*
7-
*
86
* 对于近乎有序的数组，快速排序会退化为O(N^2)。
97
*
108
* @author LuoHaiYang
@@ -22,6 +20,11 @@ public class QuickSort2 {
2220
*/
2321
private static int partition(int[] arr, int left, int right) {
2422

23+
//int p = arr[left];
24+
// ===================================== 优化2 =====================================
25+
// 避免快排退化为O(N^2)
26+
swap(arr, left, (int)Math.random()*(right - left + 1) + left);
27+
2528
int p = arr[left];
2629

2730
// arr[left+1...j] < p; arr[j+1...i) > p
@@ -31,18 +34,12 @@ private static int partition(int[] arr, int left, int right) {
3134
j++;
3235
swap(arr, j, i);
3336
}
34-
swap(arr, left, j);
3537
}
38+
swap(arr, left, j);
3639
return j;
3740
}
3841

3942
private static void sort(int[] arr, int left, int right) {
40-
/*
41-
if (left >= right) {
42-
return;
43-
}
44-
*/
45-
4643
// ===================================== 优化1 =====================================
4744
// 如果左右数值小于15，则通过插入排序来进行排序
4845
if (right - left <= 15) {

‎src/main/java/com/bruis/algorithminjava/algorithm/sort/QuickSort2Ways.java‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package com.bruis.algorithminjava.algorithm.sort;
2+
3+
/**
4+
*
5+
* 双路快排
6+
*
7+
* @author LuoHaiYang
8+
*/
9+
public class QuickSort2Ways {
10+
11+
private static int partition(int[] arr, int left, int right) {
12+
13+
swap(arr, left, (int)Math.random()*(right - left + 1) + left);
14+
15+
int p = arr[left], i = left + 1, j = right;
16+
17+
while(true) {
18+
19+
while(i <= right && arr[i] < p) {
20+
i++;
21+
}
22+
23+
while(j >= 0 && arr[j] > p) {
24+
j--;
25+
}
26+
27+
if (i > j) {
28+
break;
29+
}
30+
31+
swap(arr, i++, j--);
32+
}
33+
swap(arr, left, j);
34+
return j;
35+
}
36+
37+
private static void sort(int[] arr, int left, int right) {
38+
if (right - left <= 15) {
39+
InsertionSort.sort(arr);
40+
return;
41+
}
42+
43+
int p = partition(arr, left, right);
44+
sort(arr, left, p - 1);
45+
sort(arr, p + 1, right);
46+
}
47+
48+
public static void sort(int[] arr) {
49+
int n = arr.length;
50+
sort(arr, 0, n - 1);
51+
}
52+
53+
public static void swap(int[] arr, int i, int j) {
54+
int tmp = arr[i];
55+
arr[i] = arr[j];
56+
arr[j] = tmp;
57+
}
58+
}

‎src/main/java/com/bruis/algorithminjava/algorithm/sort/QuickSort3Ways.java‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package com.bruis.algorithminjava.algorithm.sort;
2+
3+
/**
4+
*
5+
* 三路快排
6+
*
7+
* @author LuoHaiYang
8+
*/
9+
public class QuickSort3Ways {
10+
11+
private static void sort(int[] arr, int left, int right) {
12+
if (right - left <= 15) {
13+
InsertionSort.sort(arr);
14+
return;
15+
}
16+
// 增加随机值，防止快排退化为O(N^2)
17+
swap(arr,left, (int)Math.random()*(right - left - 1) + left);
18+
19+
int p = arr[left];
20+
21+
// [p...................................................right]
22+
// p
23+
// lt
24+
// i
25+
// gt
26+
// arr[left+1...lt] < p arr[lt+1...i) = p arr[gt...right] > p
27+
int lt = left, gt = right + 1, i = left + 1;
28+
29+
while ( i < gt) {
30+
if (arr[i] < p) {
31+
swap(arr, lt+1, i);
32+
i++;
33+
lt++;
34+
} else if (arr[i] > p) {
35+
swap(arr, i, gt-1);
36+
gt--;
37+
} else {// arr[i] == v
38+
i++;
39+
}
40+
}
41+
swap(arr, left, lt);
42+
// 继续对[left,lt]进行排序
43+
sort(arr, left, lt-1);
44+
// 继续对[gt, right]进行排序
45+
sort(arr, gt, right);
46+
}
47+
48+
public static void sort(int[] arr) {
49+
int n = arr.length;
50+
sort(arr, 0, n-1);
51+
}
52+
53+
private static void swap(int[] arr, int i, int j) {
54+
int tmp = arr[i];
55+
arr[i] = arr[j];
56+
arr[j] = tmp;
57+
}
58+
}

0 commit comments

Comments
 (0)