2.18【问】堆排序的实现思路
参考下图
首先建立一个大顶堆，堆顶元素就是最大元素，把它交换到数组尾部，最大元素就排好序了
交换到堆顶的元素破坏了堆特性，对它下潜，下潜完成后堆顶就成了第二大元素，再把它交换到数组尾部，二大元素也排好了
这样依此类推，下潜=>堆顶元素交换=>下潜=>堆顶元素交换 ... 直至剩余一个元素，算法结束
P.S.
参考代码
2.19【追问】堆排序与其它排序算法比较
堆排序同级别排序方法有快排、归并等，它们的时间复杂度都是 O(n * log{n})
堆排序中的下潜操作涉及到父元素与它的左右孩子交换，数据量较大时，父元素距离它的孩子较远，这样可能会造成（CPU）缓存未命中，增加内存访问成本。快排和归并则没有这个问题
P.S.
个人认为，堆相对于堆排序更为重要，它可以应用于优先级队列、TopK 问题 ...
3、字符串类
3.1、字符串反转
源于 Leetcode 344 题
举一反三 Leetcode 151 题（反转单词）
思路 - 双指针
一开始，i 指针指向数组起始元素，j 指针指向数组结束元素，交换 i、j 指向的元素。
i 向后移动，j 向前移动，重复以上过程 ，直至 i、j 相遇，算法结束。
参考代码
Plain Text
复制代码
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
public static void sort(int[] a) {
heapify(a, a.length);
for (int right = a.length - 1; right > 0; right--) {
swap(a, 0, right);
down(a, 0, right);
}
}
// 建堆 O(n)
private static void heapify(int[] array, int size) {
for (int i = size / 2 - 1; i >= 0; i--) {
down(array, i, size);
}
}
// 下潜 O(log n)
private static void down(int[] array, int parent, int size) {
// 比较 parent 和它的左、右孩子
while (true) {
int left = parent * 2 + 1;
int right = left + 1;
// max 代表 parent 和它的左、右孩子中最大值
int max = parent;
if (left < size && array[left] > array[max]) {
max = left;
}
if (right < size && array[right] > array[max]) {
max = right;
}
// 最大的就是 parent 自己
if (max == parent) {
break;
}
// parent 与孩子中较大者交换
swap(array, max, parent);
// 继续下潜
parent = max;
}
}
Plain Text
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void reverseString(char[] s) {
reverseString(s, 0, s.length - 1);
}
static void reverseString(char[] s, int begin, int end) {
int i = begin;
int j = end;
while (i < j) {
swap(s, i, j);
i++;
j--;
}
}
static void swap(char[] array, int i, int j) {
char c = array[i];
array[i] = array[j];
array[j] = c;
}
