经典排序算法之堆排序-JavaScript/Python/Go/C++实现代码

前端算法-堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;

小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;

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

1. 算法步骤

创建一个堆 H[0……n-1];

把堆首(最大值)和堆尾互换;

把堆的尺寸缩小 1,并调用 shift_down(0),目的是把新的数组顶端数据调整到相应位置;

重复步骤 2,直到堆的尺寸为 1。

2. 动图演示

3. JavaScript 代码实现

var len;    // 因为声明的多个函数都需要数据长度,所以把len设置成为全局变量
function buildMaxHeap(arr) {   // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}
function heapify(arr, i) {     // 堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
function heapSort(arr) {
    buildMaxHeap(arr);
    for (var i = arr.length-1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

4. Python 代码实现

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):
        heapify(arr,i)
def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1
        heapify(arr, 0)
    return arr

5. Go 代码实现

func heapSort(arr []int) []int {
    arrLen := len(arr)
    buildMaxHeap(arr, arrLen)
    for i := arrLen - 1; i >= 0; i-- {
        swap(arr, 0, i)
        arrLen -= 1
        heapify(arr, 0, arrLen)
    }
    return arr
}
func buildMaxHeap(arr []int, arrLen int) {
    for i := arrLen / 2; i >= 0; i-- {
        heapify(arr, i, arrLen)
    }
}
func heapify(arr []int, i, arrLen int) {
    left := 2*i + 1
    right := 2*i + 2
    largest := i
    if left < arrLen && arr[left] > arr[largest] {
        largest = left
    }
    if right < arrLen && arr[right] > arr[largest] {
        largest = right
    }
    if largest != i {
        swap(arr, i, largest)
        heapify(arr, largest, arrLen)
    }
}
func swap(arr []int, i, j int) {
    arr[i], arr[j] = arr[j], arr[i]
}


本文由 w3cmark_前端笔记 版权所有,转载时请注明出处。
注明出处格式:w3cmark (http://www.w3cmark.com/2017/heap-sort.html)

分享到:

关注w3cmark
微信公众号 w3cmark_com