• 堆排序
    • 1. 算法步骤
    • 2. 动图演示
    • 3. JavaScript 代码实现
    • 4. Python 代码实现
    • 5. Go 代码实现
    • 6. Java 代码实现

    堆排序

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

    1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
    2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

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

    1. 算法步骤

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

    2. 把堆首（最大值）和堆尾互换；

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

    4. 重复步骤 2，直到堆的尺寸为 1。

    2. 动图演示

    动图演示

    3. JavaScript 代码实现

    1. var len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
    3. function buildMaxHeap(arr) {   // 建立大顶堆
    4.     len = arr.length;
    5.     for (var i = Math.floor(len/2); i >= 0; i--) {
    6.         heapify(arr, i);
    7.     }
    8. }
    10. function heapify(arr, i) {     // 堆调整
    11.     var left = 2 * i + 1,
    12.         right = 2 * i + 2,
    13.         largest = i;
    15.     if (left < len && arr[left] > arr[largest]) {
    16.         largest = left;
    17.     }
    19.     if (right < len && arr[right] > arr[largest]) {
    20.         largest = right;
    21.     }
    23.     if (largest != i) {
    24.         swap(arr, i, largest);
    25.         heapify(arr, largest);
    26.     }
    27. }
    29. function swap(arr, i, j) {
    30.     var temp = arr[i];
    31.     arr[i] = arr[j];
    32.     arr[j] = temp;
    33. }
    35. function heapSort(arr) {
    36.     buildMaxHeap(arr);
    38.     for (var i = arr.length-1; i > 0; i--) {
    39.         swap(arr, 0, i);
    40.         len--;
    41.         heapify(arr, 0);
    42.     }
    43.     return arr;
    44. }

    4. Python 代码实现

    1. def buildMaxHeap(arr):
    2.     import math
    3.     for i in range(math.floor(len(arr)/2),-1,-1):
    4.         heapify(arr,i)
    6. def heapify(arr, i):
    7.     left = 2*i+1
    8.     right = 2*i+2
    9.     largest = i
    10.     if left < arrLen and arr[left] > arr[largest]:
    11.         largest = left
    12.     if right < arrLen and arr[right] > arr[largest]:
    13.         largest = right
    15.     if largest != i:
    16.         swap(arr, i, largest)
    17.         heapify(arr, largest)
    19. def swap(arr, i, j):
    20.     arr[i], arr[j] = arr[j], arr[i]
    22. def heapSort(arr):
    23.     global arrLen
    24.     arrLen = len(arr)
    25.     buildMaxHeap(arr)
    26.     for i in range(len(arr)-1,0,-1):
    27.         swap(arr,0,i)
    28.         arrLen -=1
    29.         heapify(arr, 0)
    30.     return arr

    5. Go 代码实现

    1. func heapSort(arr []int) []int {
    2.     arrLen := len(arr)
    3.     buildMaxHeap(arr, arrLen)
    4.     for i := arrLen - 1; i >= 0; i-- {
    5.         swap(arr, 0, i)
    6.         arrLen -= 1
    7.         heapify(arr, 0, arrLen)
    8.     }
    9.     return arr
    10. }
    12. func buildMaxHeap(arr []int, arrLen int) {
    13.     for i := arrLen / 2; i >= 0; i-- {
    14.         heapify(arr, i, arrLen)
    15.     }
    16. }
    18. func heapify(arr []int, i, arrLen int) {
    19.     left := 2*i + 1
    20.     right := 2*i + 2
    21.     largest := i
    22.     if left < arrLen && arr[left] > arr[largest] {
    23.         largest = left
    24.     }
    25.     if right < arrLen && arr[right] > arr[largest] {
    26.         largest = right
    27.     }
    28.     if largest != i {
    29.         swap(arr, i, largest)
    30.         heapify(arr, largest, arrLen)
    31.     }
    32. }
    34. func swap(arr []int, i, j int) {
    35.     arr[i], arr[j] = arr[j], arr[i]
    36. }

    6. Java 代码实现

    1. public class HeapSort implements IArraySort {
    3.     @Override
    4.     public int[] sort(int[] sourceArray) throws Exception {
    5.         // 对 arr 进行拷贝，不改变参数内容
    6.         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    8.         int len = arr.length;
    10.         buildMaxHeap(arr, len);
    12.         for (int i = len - 1; i > 0; i--) {
    13.             swap(arr, 0, i);
    14.             len--;
    15.             heapify(arr, 0, len);
    16.         }
    17.         return arr;
    18.     }
    20.     private void buildMaxHeap(int[] arr, int len) {
    21.         for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
    22.             heapify(arr, i, len);
    23.         }
    24.     }
    26.     private void heapify(int[] arr, int i, int len) {
    27.         int left = 2 * i + 1;
    28.         int right = 2 * i + 2;
    29.         int largest = i;
    31.         if (left < len && arr[left] > arr[largest]) {
    32.             largest = left;
    33.         }
    35.         if (right < len && arr[right] > arr[largest]) {
    36.             largest = right;
    37.         }
    39.         if (largest != i) {
    40.             swap(arr, i, largest);
    41.             heapify(arr, largest, len);
    42.         }
    43.     }
    45.     private void swap(int[] arr, int i, int j) {
    46.         int temp = arr[i];
    47.         arr[i] = arr[j];
    48.         arr[j] = temp;
    49.     }
    51. }