|
13 | 13 | * 左数组元素小于等于切分元素，右数组大于等于切分元素， |
14 | 14 | * 将左右子数组排序，整个数组也就有序了 |
15 | 15 | * |
| 16 | + * 平均情况为O(nlog(n)),最差情况O(n~2),存储空间O(log(n)) |
| 17 | + * V1.1.0 sort、partition写法参照<<程序员面试金典>>重写 |
| 18 | + * |
16 | 19 | * @author Jian Shen |
17 | | - * @version V1.0.0 |
| 20 | + * @version V1.1.0 |
18 | 21 | * @date 2019/7/23 |
19 | 22 | */ |
20 | 23 | public class QuitSort<T extends Comparable<T>> extends Sort<T> { |
21 | 24 |
|
22 | 25 | @Override |
23 | | - public void sort(@NotNull T[] array) { |
24 | | - shuffle(array); |
25 | | - sort(array, 0 , array.length - 1); |
| 26 | + public void sort(@NotNull T[] arr) { |
| 27 | + shuffle(arr); |
| 28 | + sort(arr, 0 , arr.length - 1); |
26 | 29 | } |
27 | 30 |
|
28 | | - private void sort(T[] array, int left, int right) { |
29 | | - if (right <= left) { |
30 | | - return ; |
| 31 | + private void sort(T[] arr, int left, int right) { |
| 32 | + int index = partition(arr, left, right); |
| 33 | + if (left < index - 1) { // 排序左半部分 |
| 34 | + sort(arr, left, index - 1); |
| 35 | + } |
| 36 | + if (index < right) { // 排序右半部分 |
| 37 | + sort(arr, index, right); |
31 | 38 | } |
32 | | - int middle = partition(array, left, right); |
33 | | - sort(array, left, middle - 1); |
34 | | - sort(array, middle + 1, right); |
35 | 39 | } |
36 | 40 |
|
37 | | - private int partition(T[] array, int left, int right) { |
38 | | - int i = left; |
39 | | - int j = right + 1; |
40 | | - T k = array[left]; |
41 | | - while (true) { |
42 | | - while (less(array[++i], k) && i != right); // 循环1，直到找到大于等于k的元素或i增加为right |
43 | | - while (less(k, array[--j]) && j != left); // 循环2，直到找到比小于等于k的元素或j减小为left |
44 | | - if (i >= j) { |
45 | | - break; |
| 41 | + private int partition(T[] arr, int left, int right) { |
| 42 | + T pivot = arr[(left + right) / 2]; // 挑选一个基准点 |
| 43 | + while (left <= right) { |
| 44 | + // 找到左边应被放到右边的元素 |
| 45 | + while (arr[left].compareTo(pivot) < 0) { |
| 46 | + left++; |
| 47 | + } |
| 48 | + // 找到右边应被放到左边的元素 |
| 49 | + while (arr[right].compareTo(pivot) > 0) { |
| 50 | + right--; |
| 51 | + } |
| 52 | + if (left <= right) { |
| 53 | + swap(arr, left, right); // 交换元素 |
| 54 | + left++; |
| 55 | + right--; |
46 | 56 | } |
47 | | - swap(array, i, j); // 交换当前轮次找到的元素 |
48 | 57 | } |
49 | | - // array[left]必定小于等于array[j], happens-before原则，前置条件为break执行， |
50 | | - // break前置条件为循环2执行完毕，故需交换从而保证当前切分元素必定大于等于左侧数组值，小于等于右侧数组值 |
51 | | - swap(array, left, j); |
52 | | - return j; |
| 58 | + return left; |
53 | 59 | } |
54 | 60 |
|
55 | | - private void shuffle(T[] array) { |
56 | | - List<Comparable> list = Arrays.asList(array); |
57 | | - Collections.shuffle(list); // 防止最坏的情况，第一次从最小的元素切分，第二次从次小的元素切分。时间复杂度N^2/2 |
58 | | - list.toArray(array); |
| 61 | + private void shuffle(T[] arr) { |
| 62 | + List<Comparable> list = Arrays.asList(arr); |
| 63 | + Collections.shuffle(list); // 防止最坏的情况，第一次从最小的元素切分，第二次从次小的元素切分。时间复杂度N^2 |
| 64 | + list.toArray(arr); |
59 | 65 | } |
60 | 66 |
|
61 | 67 | public static void main(String[] args) { |
62 | 68 | Sort sort = new QuitSort(); |
63 | | - Integer[] array = new Integer[]{2, 1, 4, 6, 3, 7, 3}; |
64 | | - sort.sort(array); |
65 | | - System.out.println(Arrays.asList(array)); |
| 69 | + Integer[] arr = new Integer[]{2, 1, 4, 6, 3, 7, 3}; |
| 70 | + sort.sort(arr); |
| 71 | + System.out.println(Arrays.asList(arr)); |
66 | 72 | } |
67 | 73 | } |
0 commit comments