JavaScirpt基础-数组排序之堆排序

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序的平均时间复杂度为Ο(nlogn) 。

堆的底层实际上就是一棵完全二叉树，可以用数组实现。

根节点最大的堆叫作大根堆，根节点最小的堆叫作小根堆，可以根据从大到小排序或者从小到大来排序，分别建立对应的堆就可以。

var a = [1, 3, 8, 6, 15, 3, 4, 23, 76, , 34, 232, 6, 9, 456, 221];

function heap_sort(arr) {

var len = arr.length

var k = 0

function swap(i, j) {

var temp = arr[i]

arr[i] = arr[j]

arr[j] = temp

        

          
        
        
        

          

          AI 代码解读
        
      
      

}

function max_heapify(start, end) {

var dad = start

var son = dad * 2 + 1

if (son >= end) return

if (son + 1 < end && arr[son] < arr[son + 1]) {

  son++

}

if (arr[dad] <= arr[son]) {

  swap(dad, son)

  max_heapify(son, end)

}

        

          
        
        
        

          

          AI 代码解读
        
      
      

}

for (var i = Math.floor(len / 2) - 1; i >= 0; i--) {

max_heapify(i, len)

        

          
        
        
        

          

          AI 代码解读
        
      
      

}

for (var j = len - 1; j > k; j--) {

swap(0, j)

max_heapify(0, j)

        

          
        
        
        

          

          AI 代码解读
        
      
      

}

return arr

}

heap_sort(a); // [, 1, 3, 3, 4, 6, 6, 8, 9, 15, 23, 34, 76, 221, 232, 456]