堆排序相比冒泡排序、选择排序、插入排序而言,排序效率是最高的,本文从堆的属性和特点出发采用图文形式进行讲解并用JavaScript将其实现,欢迎各位感兴趣的开发者阅读本文?
堆分为两种: 最大堆和最小堆,两者的差别在于节点的排序方式。
在不同类型的堆中,每一个节点都遵循堆的属性,下方所述内容即为堆的属性。
由一个完全二叉树组成,且树中的所有节点都满足堆属性,这个完全二叉树就是堆。
根据堆的属性可知:
堆的根节点中存放的是最大或最小元素,但是其他节点的排列顺序是未知的。例如,在一个最大堆中,最大的那一个元素总是位于index0的位置,但是最小的元素则未必是最后一个元素,唯一能够保证的是最小的元素是一个叶节点,但是不确定是哪一个。
用数组来实现堆,堆中的节点在数组的位置与它的父节点以及子节点的索引之间有一个映射关系。
用公式来描述当前节点的父节点和子节点在数组中的位置(i为当前节点的索引)
// 父节点的位置,向下取整(floor)
parent(i) = floor( i - 1 ) / 2)
// 左子节点的位置
left(i) = 2i +1
// 右子节点的位置,左右节点总是处于相邻的位置
right(i) = left(i)+1 = 2i+2
array[parent(i)] >= array[i]
堆是一个完全二叉树,树的高度是指从树的根节点到最低叶节点所需要的步数。
树高度正式的定义: 节点之间的边的最大值。
// 例如,一个堆有15个节点,求这个堆的高度
h = floor(log2(15)) = floor(3.91) = 3
套入公式可得,堆的高度为3
// log2(n),log为求次方运算,log以2为底,15的对数。若n为8,则运算结果为3,即2^3=8
// 高度为3,即最下面一层有8个节点
2^3 = 8;
// 高度为3,即其他层的所有节点有7个
2^3 -1 = 7;
// 高度为3,即堆中的节点数为15
2^4 -1 = 16 - 1 = 15;
实现堆排序之前,我们需要先将即将排序的数据构建成一个最大堆,构建完成后,根据最大堆的属性可知,堆顶部的值最大,我们将它取出,然后重新构建堆,直到堆中的所有数据被取出,堆排序也就完成了。
在一个完全二叉树中,从一个节点出发,找到它的左子树和右子树,将当前节点与它的两颗子树进行大小比较,找到两颗树中较大的一方,将其与当前节点进行交换,交换完毕后,当前节点所在的树就是一个最大堆。我们称这个交换操作为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号元素时,那么这组数据就成了一个最大堆。
接下来,我们整理下实现思路:
接下来,我们将上述思路转化为代码:
/*
* 将完全二叉树构建成堆
* 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,重新构建堆,直至最大堆中的数据全部被取出则排序完成。
接下来,我们整理下实现思路:
接下来,我们将上述思路转化为代码:
// 堆排序函数
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号数组区域标为left,将2号数组区域标为right,3号数组最左端的元素我们用L表示,3号数组最右端的元素我们用R表示,求出3号数组的中间值后我们用M表示。
如图所示,我们已知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数组即可。
上述的归并操作,是将已经排序好的两组数据归并成一个数组,然后进行排序,正常情况下,我们传入的数组是乱序的,我们会把数组从中间分开,分为左和右,然后想办法让两方的数据按照从小到达进行排序,然后合并两方的数据,则排序完成。
例如,我们要将下方数据进行归并排序。
正如归并图解所描述,要实现两个数组的合并,前提是两组数据中的数据已经排列按照从小到大的顺序进行排列。
接下来,我们将上述思路用代码实现:
/**
* 归并函数
* @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);
实现归并排序,我们首先需要计算出数组的中间值,然后将乱序的数组进行分割(分割到无法继续分割位置),分割完毕后,将分割的两组数据进行合并,递归操作即可完成归并排序。
接下来,我们看下代码的实现:
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·