- Notifications
You must be signed in to change notification settings - Fork24
Open
Description
堆排序相比其他几种排序代码会有些复杂，不过没关系，我们先来看一些前置知识，可以帮助我们更好的理解堆排序。
堆排序顾名思义就是要利用堆这种数据结构进行排序。堆是一种特殊的树，满足以下两点就是堆：
- 堆是一个完全二叉树
- 堆中每一个节点的值都必须大于等于(或小于等于)其子树中的每个节点的值
每个节点的值都大于等于子树中每个节点值的堆，叫做大顶堆，每个节点的值都小于等于子树中每个节点值的堆，叫做小顶堆。
也就是说，大顶堆中，根节点是堆中最大的元素。小顶堆中，根节点是堆中最小的元素。
如果你对树这种数据结构还不是很了解，可以移步我的这篇专栏“树”业有专攻
堆如果用一个数组表示的话，给定一个节点的下标 i (i从1开始)，那么它的父节点一定为 A[i / 2]，左子节点为 A[2i]，右子节点为 A[2i + 1]。
堆排序包含两个过程，建堆和排序。首先构建一个大顶堆，也就是将最大值存储在根节点(i = 1)，每次取大顶堆的根节点与堆的最后一个节点进行交换，此时最大值放入了有效序列的最后一位，并且有效序列减 1，有效堆依然保持完全二叉树的结构，然后进行堆化成为新的大顶堆。重复此操作，直到有效堆的长度为 0，排序完成。
constheapSort=function(arr){buildHeap(arr,arr.length-1)letheapSize=arr.length-1// 初始化堆的有效序列长度for(leti=arr.length-1;i>1;i--){swap(arr,1,i)// 交换堆顶元素与最后一个有效子元素heapSize--// 有效序列长度减 1heapify(arr,heapSize,1)// 堆化有效序列}returnarr}// 构建大顶堆constbuildHeap=function(items,heapSize){// 从后往前并不是从序列的最后一个元素开始，而是从最后一个非叶子节点开始，这是因为，叶子节点没有子节点，不需要自上而下式堆化。// 最后一个子节点的父节点为 n/2 ，所以从 n/2 位置节点开始堆化for(leti=Math.floor(heapSize/2);i>=1;i--){heapify(items,heapSize,i)}}// 堆化constheapify=function(arr,heapSize,i){while(true){letmaxIndex=iif(2*i<=heapSize&&arr[i]<arr[i*2]){maxIndex=i*2}if(2*i+1<=heapSize&&arr[maxIndex]<arr[i*2+1]){maxIndex=i*2+1}if(maxIndex===i)breakswap(arr,i,maxIndex)i=maxIndex}}// 交换工具函数constswap=function(arr,i,j){lettemp=arr[i]arr[i]=arr[j]arr[j]=temp}
- 时间复杂度: O(nlogn)
- 空间复杂度: O(1)
- 不稳定
Metadata
Metadata
Assignees
Labels
No labels