排序

1. 快速排序

时间复杂度：平均复杂度为O(n·log n)，最差情况下的复杂度为O(n²)

空间复杂度：平均复杂度为O(log n)，最差情况下的复杂度为O(n)

 1 package org.example.sort;
 2 
 3 import java.util.List;
 4 
 5 /**
 6  * @description: 快速排序
 7  **/
 8 
 9 public class QuickSort {
10 
11     public static void sort(List<Integer> list) {
12         sort(list, 0, list.size() - 1);
13     }
14 
15     private static void sort(List<Integer> list, int begin, int end) {
16 
17         if (begin >= end) return;
18 
19         int left = begin;
20         int right = end;
21         int midVal = list.get(left);
22         while (left < right) {
23             // 基准值是最左侧的值，所以可以认为左边已经遇到的不满足条件的值
24             // 因此循环从右侧开始
25             while (list.get(right) > midVal && left < right) {
26                 right--;
27             }
28             // 找到第一个小于等于midVal的值，交换到左边
29             if (left < right) {
30                 list.set(left, list.get(right));
31                 left++;
32             }
33 
34             while (list.get(left) < midVal && left < right) {
35                 left++;
36             }
37             // 找到第一个大于等于midVal的值，交换到右边
38             if (left < right) {
39                 list.set(right, list.get(left));
40                 right--;
41             }
42         }
43         // 把midVal放到中间位置
44         list.set(left, midVal);
45         sort(list, begin, left - 1);
46         sort(list, left + 1, end);
47     }
48 }