/ 算法  

了解你使用的 Sort ( 实现剖析) - 2

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

往期:

直接选择

思路:

  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);
}
}