堆排序

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

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

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

1. 算法步骤

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

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

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

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

2. 动图演示

动图演示

3. 代码实现

1. 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. }

2. 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

3. 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. }

4. 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. }

5. PHP 代码实现

  1. function buildMaxHeap(&$arr)
  2. {
  3.     global $len;
  4.     for ($i = floor($len/2); $i >= 0; $i--) {
  5.         heapify($arr, $i);
  6.     }
  7. }
  9. function heapify(&$arr, $i)
  10. {
  11.     global $len;
  12.     $left = 2 * $i + 1;
  13.     $right = 2 * $i + 2;
  14.     $largest = $i;
  16.     if ($left < $len && $arr[$left] > $arr[$largest]) {
  17.         $largest = $left;
  18.     }
  20.     if ($right < $len && $arr[$right] > $arr[$largest]) {
  21.         $largest = $right;
  22.     }
  24.     if ($largest != $i) {
  25.         swap($arr, $i, $largest);
  26.         heapify($arr, $largest);
  27.     }
  28. }
  30. function swap(&$arr, $i, $j)
  31. {
  32.     $temp = $arr[$i];
  33.     $arr[$i] = $arr[$j];
  34.     $arr[$j] = $temp;
  35. }
  37. function heapSort($arr) {
  38.     global $len;
  39.     $len = count($arr);
  40.     buildMaxHeap($arr);
  41.     for ($i = count($arr) - 1; $i > 0; $i--) {
  42.         swap($arr, 0, $i);
  43.         $len--;
  44.         heapify($arr, 0);
  45.     }
  46.     return $arr;
  47. }