算法图解
冒泡排序的优化
分治的思想,
- 随机找到第一个数字 6, 将比6小的挪到6左边, 比6大的挪到6右边, 分成两堆
- 递归6的左边和右边
- 重复1~2直到分解成最小单元(左右两边只有1个/0个元素)
如何实现 将比6小的挪到6左边, 比6大的挪到6右边 , 参考 1.挖坑法 2.双指针法, 本文采用挖坑法实现
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
private static void doSort(int[] arr, int start, int end) {
if (start >= end) {
return;
}
int pivot = arr[start];
int pivotIndex = start;
int left = start;
int right = end;
while (left < right) {
// 坑在左边,往右边找
while (left == pivotIndex && left < right) {
if (arr[right] > pivot) {
right--;
} else {
arr[pivotIndex] = arr[right];
pivotIndex = right;
break;
}
}
// 坑在右边,往左边找
while (right == pivotIndex && left < right) {
if (arr[left] < pivot) {
left++;
} else {
arr[pivotIndex] = arr[left];
pivotIndex = left;
break;
}
}
}
arr[left] = pivot;
doSort(arr, start, left);
doSort(arr, left + 1, end);
}
算法时间复杂度
O(n^2) ~ O(nlogn)
取决于树的平衡性, 最差的n各节点的树的层次是n,最好的是log2n, 树的每层遍历比对的时间是n次
空间复杂度
O(1)
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class QuickSort {
private static void sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int start = 0;
int end = arr.length - 1;
doSort(arr, start, end);
}
private static void doSort(int[] arr, int start, int end) {
if (start >= end) {
return;
}
int pivot = arr[start];
int pivotIndex = start;
int left = start;
int right = end;
while (left < right) {
// 坑在左边,往右边找
while (left == pivotIndex && left < right) {
if (arr[right] > pivot) {
right--;
} else {
arr[pivotIndex] = arr[right];
pivotIndex = right;
break;
}
}
// 坑在右边,往左边找
while (right == pivotIndex && left < right) {
if (arr[left] < pivot) {
left++;
} else {
arr[pivotIndex] = arr[left];
pivotIndex = left;
break;
}
}
}
arr[left] = pivot;
doSort(arr, start, left);
doSort(arr, left + 1, end);
}
public static void main(String[] args) {
int[] array = {111, 52, 77, 98, 36, 12, 13, 48};
sort(array);
System.out.println(arrayToString(array));
}
private static String arrayToString(int[] array) {
StringBuilder builder = new StringBuilder();
for (int t : array) {
builder.append(t + " ");
}
return builder.toString();
}
}
参考
https://www.sohu.com/a/246785807_684445/
