先上图， 本篇文章涉及 选择排序 中两种算法

往期：

直接选择

思路：

  1. 遍历数组a[0]-a[n]并得出最小值a[j], 将a[0]与a[j]互换
  2. 遍历数组a[1]-a[n]并得出最小值a[j], 将a[1]与a[j]互换
  3. 循环直至结束

 

参考动画去理解 ↓

堆排序

核心：将数组构造成二叉堆↓（左侧数组，右侧对应二叉堆）

二叉堆（英语：binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”。

思路：

  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

// JS 实现
// 调用如 heapSort(arr)
function heapSort(iArr) {
	var n = iArr.length;
	// 若只有一个或者没有，则返回
	if (n <= 1) { return iArr; }
	// 逐层建堆
	for (var i = Math.floor(n / 2); i >= 0; i--) {
		maxHeapify(iArr, i, n);
	}
	// 解构：堆排序
	for (var j = 0; j < n; j++) {
		swap(iArr, 0, n - 1 - j) // 根节点与"最后一个"节点交换
		maxHeapify(iArr, 0, n - 2 - j); // 根节点开始重新调整
	}
	return iArr;
}

function swap(arr, a, b) {
	if (a == b) { return; }
	var c = arr[a];
	arr[a] = arr[b];
	arr[b] = c;
}

function maxHeapify(Arr, i, size) {
	var l = 2 * i + 1, r = 2 * i + 2; // 父节点为i，左子节点为2i + 1，右子节点为2i + 2
	var largest = i;
	// 若子节点比节点大，则标记
	if (l <= size && Arr[l] > Arr[largest]) {
		largest = l;
	}
	if (r <= size && Arr[r] > Arr[largest]) {
		largest = r;
	}
	// 若标记有子节点，则交换父子位置，并递归计算
	if (largest !== i) {
		swap(Arr, i, largest);
		maxHeapify(Arr, largest, size);
	}
}