前端学习数据结构与算法系列(七)：堆排序与归并排序
堆排序
前言
堆排序相比冒泡排序、选择排序、插入排序而言，排序效率是最高的，本文从堆的属性和特点出发采用图文形式进行讲解并用JavaScript将其实现，欢迎各位感兴趣的开发者阅读本文?
堆属性
堆分为两种: 最大堆和最小堆，两者的差别在于节点的排序方式。
在不同类型的堆中，每一个节点都遵循堆的属性，下方所述内容即为堆的属性。
- 最大堆: 父节点的值大于子节点的值
- 最小堆: 父节点的值小于子节点的值
由一个完全二叉树组成，且树中的所有节点都满足堆属性，这个完全二叉树就是堆。
根据堆的属性可知:
堆的根节点中存放的是最大或最小元素，但是其他节点的排列顺序是未知的。例如，在一个最大堆中，最大的那一个元素总是位于index0的位置，但是最小的元素则未必是最后一个元素，唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。
- 最大堆根节点中的元素一定是树中的最大值
- 最小堆根节点中的元素一定是树中的最小值
数组实现堆
用数组来实现堆，堆中的节点在数组的位置与它的父节点以及子节点的索引之间有一个映射关系。
用公式来描述当前节点的父节点和子节点在数组中的位置（i为当前节点的索引）
// 父节点的位置，向下取整(floor)
parent(i) = floor( i - 1 ) / 2)
// 左子节点的位置
left(i) = 2i +1
// 右子节点的位置，左右节点总是处于相邻的位置
right(i) = left(i)+1 = 2i+2- 若计算出的索引不是一个有效的数组索引(小于0时)，则当前节点没有父节点
- 若计算出的索引大于数组的长度，则当前节点没有子节点。
- 父节点的值一定大于等于其子节点的值，即:
array[parent(i)] >= array[i]- 当前层级所有的节点未填满之前不允许开始下一层的填充
堆属性计算
堆是一个完全二叉树，树的高度是指从树的根节点到最低叶节点所需要的步数。
树高度正式的定义: 节点之间的边的最大值。
- 一个高度为h的堆有h+1层。
- 如果一个堆有n个节点，那么它的高度为 floor(log2(n))
// 例如，一个堆有15个节点，求这个堆的高度
h = floor(log2(15)) = floor(3.91) = 3
套入公式可得，堆的高度为3
// log2(n)，log为求次方运算，log以2为底，15的对数。若n为8，则运算结果为3，即2^3=8- 如果最下面一层已经填满，那这一层的节点为 2^h个。
// 高度为3，即最下面一层有8个节点
2^3 = 8;- 最下面已经填满的那一层以上的所有节点数目为 2^h -1个。
// 高度为3，即其他层的所有节点有7个
2^3 -1 = 7;- 整个堆中的节点数为: 2^(h+1)-1
// 高度为3,即堆中的节点数为15
2^4 -1 = 16 - 1 = 15;- 叶结点总是位于数组的floor(n/2)和n-1之间
用JS实现堆排序
实现堆排序之前，我们需要先将即将排序的数据构建成一个最大堆，构建完成后，根据最大堆的属性可知，堆顶部的值最大，我们将它取出，然后重新构建堆，直到堆中的所有数据被取出，堆排序也就完成了。
调整完全二叉树中的树为一个最大堆
在一个完全二叉树中，从一个节点出发，找到它的左子树和右子树，将当前节点与它的两颗子树进行大小比较，找到两颗树中较大的一方，将其与当前节点进行交换，交换完毕后，当前节点所在的树就是一个最大堆。我们称这个交换操作为heapify
接下来，我们来整理下实现思路
- 声明一个函数，参数为: 树，树的节点数，当前要进行heapify操作的节点
- 根据数组实现堆中所讲的，父节点和子节点在数组中位置的计算公式，找到当前节点的左子树和右子树的位置
- 假设最大值为当前要操作的节点，将最大值与左子树和右子树分别进行大小比较
- 进行大小比较后，如果最大值的位置不是当前操作节点的位置，则将其与当前操作节点位置的数据进行互换，递归调用heapify函数
- 退出递归: 当前操作的节点大于等于树的总节点数时，则退出递归。
- 当前节点与左子树和右子树进行大小比较时，如果左、右子树的位置大于树的总节点数时，不禁笑最大值赋值。
接下来我们将上述思路转化为代码：
/*
* 1. 从一个节点出发
* 2. 从它的左子树和右子树中选择一个较大值
* 3. 将较大值与这个节点进行位置交换
* 上述步骤,就是一次heapify的操作
* */
// n为树的节点数，i为当前操作的节点 (找到这颗树里的最大节点)
const heapify = function (tree, n, i) {
if(i >= n){
// 结束递归
return;
}
// 找到左子树的位置
let leftNode = 2 * i + 1;
// 找到右子树的位置
let rightNode = 2 * i +2;
/*
1. 找到左子树和右子树位置后，必须确保它小于树的总节点数
2. 已知当前节点与它的左子树与右子树的位置，找到最大值
*/
// 设最大值的位置为i
let max = i;
// 如果左子树的值大于当前节点的值则最大值的位置就为左子树的位置
if(leftNode < n && tree[leftNode] > tree[max]){
max = leftNode;
}
// 如果右子树的值大于当前节点的值则最大值的位置就为右子树的位置
if(rightNode < n && tree[rightNode] > tree[max]){
max = rightNode;
}
/*
* 1. 进行大小比较后，如果最大值的位置不是刚开始设的i，则将最大值与当前节点进行位置互换
* */
if(max !== i){
// 交换位置
swap(tree,max,i);
// 递归调用，继续进行heapify操作
heapify(tree,n,max)
}
};
// 交换数组位置函数
const swap = function (arr,max,i) {
[arr[max],arr[i]] = [arr[i],arr[max]];
};接下来我们测试下heapify函数
const dataArr = [23,15,34,11,23,4,19,80];
// 我们假设当前操作节点为数组的0号元素，我们对0号元素进行一次heapify才做
heapify(dataArr,dataArr.length,0);
// 打印结果
console.log(dataArr);执行结果如下，观察执行结果，我们发现，0号元素所在的树符合最大堆的属性
将乱序数据构建成一个堆
通常情况下，我们的数据是乱序的，没有规律可言，此时我们就需要将这些数据构建成堆，heapify实现堆的构建前提是:知道当前操作节点的位置，此时我们从数据的最后一个节点的父节点出发，进行heapify操作，直至当前操作节点为数组的0号元素时，那么这组数据就成了一个最大堆。
接下来，我们整理下实现思路：
- 找到树的最后一个节点
- 根据数组实现堆中所讲的，寻找父节点位置的公式，根据公式我们就可以找到当前操作节点的父节点
- 从树最后一个节点的父节点开始进行heapify操作,直至当前操作节点为0
接下来，我们将上述思路转化为代码:
/*
* 将完全二叉树构建成堆
* 1. 从树的最后一个父节点开始进行heapify操作
* 2. 树的最后一个父节点 = 树的最后一个子结点的父节点
* */
const buildHeap = function (tree,n) {
// 最后一个节点的位置 = 数组的长度-1
const lastNode = n -1;
// 最后一个节点的父节点
const parentNode = Math.floor((lastNode - 1) / 2);
// 从最后一个父节点开始进行heapify操作
for (let i = parentNode; i >= 0; i--){
heapify(tree, n, i);
}
};接下来我们测试下buildHeap函数
const dataArr = [23,15,34,11,23,4,19,80];
buildHeap(dataArr,dataArr.length);
console.log(dataArr);观察执行结果，我们发现数组中的数据已经满足最大堆的属性
实现堆排序
我们将最大堆构建完成后，根据最大堆的特性可知：堆的顶点为这个堆的最大值，我们将这个值取出，然后将堆的最后一个节点移动至堆的顶部，然后调用heapify，重新构建堆，直至最大堆中的数据全部被取出则排序完成。
接下来，我们整理下实现思路：
- 将数据先构建成一个最大堆
- 从堆的最后一个节点出发，将其与树的根节点进行位置交换
- 交换完毕后，调用heapify重新调整堆。
- 排序好一个数后，我们的数组长度就会-1，则调用swap和heapify时,树的高度就是当前循环到的i的值。
接下来，我们将上述思路转化为代码:
// 堆排序函数
const heapSort = function (tree,n) {
// 构建堆
buildHeap(tree,n);
// 从最后一个节点出发
for(let i = n - 1; i >= 0; i--){
// 交换根节点和最后一个节点的位置
swap(tree,i,0);
// 重新调整堆
heapify(tree,i,0);
}
};接下来我们测试下heapSort函数
const dataArr = [23,15,34,11,23,4,19,80];
heapSort(dataArr,dataArr.length);
console.log(dataArr);观察执行结果，我们发现数组中的数据已经按照从小到大进行排列
归并排序
前言
归并排序与堆排序的时间复杂度都为O(nlogn)，这两种算法的应用场景较为广泛，本文采用图文形式详细讲解归并排序的实现思路，并用JavaScript将其实现，欢迎各位感兴趣的前端开发者阅读本文。
概念
归并排序算法会将序列分成长度相同的两个子序列，当无法继续往下分时(每个子序列都只有一个数据时)，就对子序列进行归并。
归并是指把两个排序好的子序列，合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。
归并图解示例
如图所示，有两个已经排好序的数组1和2，我们把1号数组和2号数组的内容，按照从小到达的顺序放进3号数组里，即为归并操作,接下来就跟大家分享下如何进行归并操作。
- 如图所示，我们先将1号数组和2号数组的内容放进3号数组里
我们将1号数组区域标为left,将2号数组区域标为right,3号数组最左端的元素我们用L表示,3号数组最右端的元素我们用R表示，求出3号数组的中间值后我们用M表示。
- 如图所示，我么将数组拆分为两个小数组，left和right，用i指向left数组的0号元素，用j指向right数组的0号元素
如图所示，我们已知M的位置，则左边数组的大小为M - L,右边数组大小为R - M + 1，计算出左、右数组的大小后，我们对数组进行填充。 数组的填充规则为: 左数组:从L开始到M结束，右数组: 从M开始到R结束。
如图所示，我们分别用i、j、k三个字母指向左、右数组的0号元素、合并后的数组的0号元素。
如图所示，我们用左数组的0号元素和右数组的0号元素进行大小比较，将小的一方放进arr数组的k号位置，k移动至下一个位置。
如图所示，i号元素已经放入数组中，此时我们将i移动到下一个位置，将其与j进行大小比较，将小的一方放进arr数组中，k移动至下一个位置。
如图所示，j号元素已经放入数组中，此时我们将j移动到下一个位置，将其与i进行大小比较，将小的一方放进arr数组中，k移动至下一个位置。
重复，上述操作，直至一方数组全部都取完 如图所示，right数组的数据已被全部取出
若一方数组的数据被全取出后，直接将另一方数组中的元素放进arr数组即可。
归并排序图解示例
上述的归并操作，是将已经排序好的两组数据归并成一个数组，然后进行排序，正常情况下，我们传入的数组是乱序的，我们会把数组从中间分开，分为左和右，然后想办法让两方的数据按照从小到达进行排序，然后合并两方的数据，则排序完成。
例如，我们要将下方数据进行归并排序。
- 将序列对半分割（2段）
- 在继续往下分
- 分割完毕，结下来对分割后的元素进行合并
- 将6与4进行合并，合并后的顺序为4,6
- 接下来把3和7进行合并，合并后的顺序为3,7
- 此时，我们产生了两组从小到大排列的数据，符合了归并的要求，我们将这两组数据代归并中，进行合并。
- 此时，我们发现还剩余两组数据未进行排序，我们递归上述操作，将这两组数据进行合并
- 合并完后，我们发现又剩余两组数据，符合了归并的要求，我们继续调用归并，将这两组数据进行合并，排序完成。
用JS实现归并排序
归并的实现
正如归并图解所描述，要实现两个数组的合并，前提是两组数据中的数据已经排列按照从小到大的顺序进行排列。
- 声明归并函数：
- 参数arr为两组从小到大排序的数组，将其合并成一个以后的数组。
- 参数L为数组的起点索引
- 参数M为数组的中间点(分割点),用于标识两组从小到大排序的数组，M左边的数据为一个数组(leftArr)，M本身以及它右边的数据为一个数组(rightArr)。
- 参数R为数组的终点索引
- 分别计算左、右数组的长度
- 左边数组的长度为M - L
- 右边数组的长度为R - M + 1
- 声明左、右数组，初始化其长度
- 根据中间值，分别将arr中的数据填充到左、右数组
- 左数组: 从L填充到M(不包含M)
- 右数组: 从M(包含M)填充到R
- 将两组数据进行合并(从小到大进行排序)
- 如果左侧数组的数据已经比较完，右侧数组的数据还未比较完，则arr的k项就为右侧数组的剩余项。
- 如果右侧数组的数据已经比较完，左侧数组的数据还未比较完，则arr的k项就为左侧数组的剩余项。
- 当前遍历到左侧数组的数据 < 当前遍历到的右侧数组的数据，则arr的k项为当前左侧数组的数据。i自增，k自增。
- 当前遍历到左侧数组的数据 > 当前遍历到的右侧数组的数据，则arr的k项为当前右侧数组的数据。j自增，k自增。
- i指向左侧数组的每一项
- j指向右侧数组的每一项
- k指向合并后的数组的每一项
- 声明3个变量：i, j, k
- 将左侧数组的每一项数据与右侧数组的每一项数据进行大小比较
- 判断左、右数组是否比较完成
接下来，我们将上述思路用代码实现:
/**
* 归并函数
* @param arr
* @param L 数组的起点
* @param M 数组的分割点
* @param R 数组的终点
*/
const merger = function (arr, L, M, R) {
// 左边数组大小和右边数组大小
let left_size = M - L;
let right_size = R - M + 1;
// 声明左边数组和右边数组
let leftArr = new Array(left_size);
let rightArr = new Array(right_size);
let i,j,k;
// 填充左数组(从L开始到M结束)
for (i = L; i < M; i++){
leftArr[i-L] = arr[i];
}
// 填充右数组(从M开始到R结束)
for (i = M; i <= R; i++){
rightArr[i-M] = arr[i];
}
// 数组合并
i = 0; j = 0; k = L;
while (i < left_size && j < right_size){
// 如果左边数组的i项小于右边数组的j项，则数组的k项就为左边数组的i项。否则数组的k项就为右边数组的j项
if(leftArr[i] < rightArr[j]){
arr[k] = leftArr[i];
i++;
k++;
}else{
arr[k] = rightArr[j];
j++;
k++;
}
}
// 当右边数组到顶部后，左边数组还未到顶部，则将剩余元素放进arr中
while (i < left_size){
arr[k] = leftArr[i];
i++;
k++
}
// 当左边数组到顶部后，右边数组还未到顶部，则将剩余元素放进arr中
while (j < right_size){
arr[k] = rightArr[j];
j++;
k++;
}
};- 测试下我们写的归并函数
const dataArr = [2,8,9,10,4,5,6,7];
/*测试合并*/
merger(dataArr,0,4,7);
// 合并后的数据
console.log(dataArr);
归并排序的实现
实现归并排序，我们首先需要计算出数组的中间值，然后将乱序的数组进行分割(分割到无法继续分割位置),分割完毕后，将分割的两组数据进行合并，递归操作即可完成归并排序。
- 计算中间值: (L + R) / 2
- 分割左、右数组
- 合并分割后的数据
- 递归操作(直至L = R)
接下来，我们看下代码的实现:
const mergerSort = function (arr,L,R) {
if(L===R){
// 数据已经切割完毕
return false;
}
else{
// 计算中间值(向下取整)
let M = Math.floor((L + R) / 2);
// 分割后,把左边的数据进行一次归并排序
mergerSort(arr,L,M);
// 对右边的数据进行一次归并排序
mergerSort(arr,M+1,R);
// 合并两边的数据
merger(arr,L,M+1,R)
}
};- 测试下我们写的归并排序
const dataArr = [6,4,3,7,5,1,2];
/*测试排序*/
mergerSort(dataArr,0,dataArr.length - 1);
// 合并后的数据
console.log(dataArr);
写在最后
* 文中使用的图片源自《我的第一本算法书》，如若侵权，请联系图雀社区公众号小编，作者立即删除相关图片。
·END·