22
33快速排序又是一种分而治之思想在排序算法上的典型应用。
44
5- - 时间复杂度：O(NlogN )
6- - 空间复杂度：O(N )
5+ - 时间复杂度：O(nlogn )
6+ - 空间复杂度：O(n )
77- 稳定性：稳定
88
99排序动画图：
@@ -76,19 +76,19 @@ public class QuickSort {
7676
7777### 2. 快速排序算法的优化
7878
79- 快速排序的最坏运行情况是 O(N ^2)，比如说顺序数列的快排。但它的平摊期望时间是 O(NlogN )，且 O(NlogN ) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
79+ 快速排序的最坏运行情况是 O(n ^2)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn )，且 O(nlogn ) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
8080
8181此处有两点可以进行优化。
8282
83831 . 对于数组数小于15时，使用插入排序; 数据量较小时，插入排序效率跟高；
84- 2 . 对于快速排序的基准值，取随机数，防止数组退化为顺序数组，即快速排序平均时间复杂度退化为O(N ^2)
84+ 2 . 对于快速排序的基准值，取随机数，防止数组退化为顺序数组，即快速排序平均时间复杂度退化为O(n ^2)
8585
8686参考代码如下：
8787```
8888/**
8989 * 快速排序的优化
9090 *
91- * 对于近乎有序的数组，快速排序会退化为O(N ^2)。
91+ * 对于近乎有序的数组，快速排序会退化为O(n ^2)。
9292 *
9393 * @author LuoHaiYang
9494 */
@@ -107,7 +107,7 @@ public class QuickSort2 {
107107
108108 //int p = arr[left];
109109 // ===================================== 优化2 =====================================
110- // 避免快排退化为O(N ^2)
110+ // 避免快排退化为O(n ^2)
111111 swap(arr, left, (int)Math.random()*(right - left + 1) + left);
112112
113113 int p = arr[left];
@@ -150,8 +150,152 @@ public class QuickSort2 {
150150}
151151```
152152
153- ### 3. 双路快排
153+ ### 3. 双路（两路）快排
154154
155+ 如果存在和 基准值p相等的值，则会出现不平衡的情况，而此时快速排序的平均时间复杂度会退化为O(n^2)。而双路（两路）快排就是为了解决这种情况。
155156
157+ 下面直接展示实现代码：
158+ ```
159+ /**
160+ *
161+ * 双路快排
162+ *
163+ * @author LuoHaiYang
164+ */
165+ public class QuickSort2Ways {
166+
167+ private static int partition(int[] arr, int left, int right) {
168+
169+ swap(arr, left, (int)Math.random()*(right - left + 1) + left);
170+
171+ int p = arr[left], i = left + 1, j = right;
172+
173+ while(true) {
174+
175+ /**
176+ * 这里arr[i] < p 和 arr[j] > p 是为了避免出现 arr[i] == p 和 arr[j] == p的情况。
177+ * 如果arr[i] == p，则直接进行了i++了，则数组的p会变得极度不平衡，即 所有小于等于p的值都分在了左边，
178+ * 这种情况下，快速排序的平均时间复杂度会退化成：O(n^2)
179+ *
180+ */
181+
182+ while(i <= right && arr[i] < p) {
183+ i++;
184+ }
185+ while(j >= 0 && arr[j] > p) {
186+ j--;
187+ }
188+
189+ if (i > j) {
190+ break;
191+ }
192+
193+ swap(arr, i++, j--);
194+ }
195+ swap(arr, left, j);
196+ return j;
197+ }
198+
199+ private static void sort(int[] arr, int left, int right) {
200+ if (right - left <= 15) {
201+ InsertionSort.sort(arr);
202+ return;
203+ }
204+
205+ int p = partition(arr, left, right);
206+ sort(arr, left, p - 1);
207+ sort(arr, p + 1, right);
208+ }
209+
210+ public static void sort(int[] arr) {
211+ int n = arr.length;
212+ sort(arr, 0, n - 1);
213+ }
214+
215+ public static void swap(int[] arr, int i, int j) {
216+ int tmp = arr[i];
217+ arr[i] = arr[j];
218+ arr[j] = tmp;
219+ }
220+ }
221+ ```
222+
223+ 这里需要注意一点，对于双路快排的小于基准值p和大于基准值p的判断，是不能用相等的，正如上述代码中while循环中的：
224+ ```
225+ while(i <= right && arr[i] < p) {
226+ i++;
227+ }
228+ while(j >= 0 && arr[j] > p) {
229+ j--;
230+ }
231+ ```
232+ 这里就是为了避免出现极度不平衡的情况出现，上述代码注释以及解释了。
233+
234+ ### 4. 三路快排
235+
236+ 然而，对于大量重复值的情况，两路快排还有优化的空间。下面先看下三路快排的代码实现：
237+
238+ ```
239+ /**
240+ *
241+ * 三路快排
242+ *
243+ * @author LuoHaiYang
244+ */
245+ public class QuickSort3Ways {
246+
247+ private static void sort(int[] arr, int left, int right) {
248+ if (right - left <= 15) {
249+ InsertionSort.sort(arr);
250+ return;
251+ }
252+ // 增加随机值，防止快排退化为O(n^2)
253+ swap(arr,left, (int)Math.random()*(right - left - 1) + left);
254+
255+ int p = arr[left];
256+
257+ // [p...................................................right]
258+ // p
259+ // lt
260+ // i
261+ // gt
262+ // arr[left+1...lt] < p arr[lt+1...i) = p arr[gt...right] > p
263+ int lt = left, gt = right + 1, i = left + 1;
264+
265+ while ( i < gt) {
266+ if (arr[i] < p) {
267+ swap(arr, lt+1, i);
268+ i++;
269+ lt++;
270+ } else if (arr[i] > p) {
271+ swap(arr, i, gt-1);
272+ gt--;
273+ } else {// arr[i] == v
274+ i++;
275+ }
276+ }
277+ swap(arr, left, lt);
278+ // 继续对[left,lt]进行排序
279+ sort(arr, left, lt-1);
280+ // 继续对[gt, right]进行排序
281+ sort(arr, gt, right);
282+ }
283+
284+ public static void sort(int[] arr) {
285+ int n = arr.length;
286+ sort(arr, 0, n-1);
287+ }
288+
289+ private static void swap(int[] arr, int i, int j) {
290+ int tmp = arr[i];
291+ arr[i] = arr[j];
292+ arr[j] = tmp;
293+ }
294+ }
295+ ```
296+
297+ 三路快排相对于两路快排的优化之处在于，当出现大量重复元素时直接进行判断加速排序过程，直接进行lt++或者是gt--，这样避免了大量重复元素是的替换过程。
298+
299+ ## 参考
156300
157- ## 参考
301+ - [ 动态图参考 ] ( https://www.runoob.com/w3cnote/bubble-sort.html )
0 commit comments