堆排序

堆排序(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设置成为全局变量
  2. function buildMaxHeap(arr) { // 建立大顶堆
  3. len = arr.length;
  4. for (var i = Math.floor(len/2); i >= 0; i--) {
  5. heapify(arr, i);
  6. }
  7. }
  8. function heapify(arr, i) { // 堆调整
  9. var left = 2 * i + 1,
  10. right = 2 * i + 2,
  11. largest = i;
  12. if (left < len && arr[left] > arr[largest]) {
  13. largest = left;
  14. }
  15. if (right < len && arr[right] > arr[largest]) {
  16. largest = right;
  17. }
  18. if (largest != i) {
  19. swap(arr, i, largest);
  20. heapify(arr, largest);
  21. }
  22. }
  23. function swap(arr, i, j) {
  24. var temp = arr[i];
  25. arr[i] = arr[j];
  26. arr[j] = temp;
  27. }
  28. function heapSort(arr) {
  29. buildMaxHeap(arr);
  30. for (var i = arr.length-1; i > 0; i--) {
  31. swap(arr, 0, i);
  32. len--;
  33. heapify(arr, 0);
  34. }
  35. return arr;
  36. }

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)
  5. def heapify(arr, i):
  6. left = 2*i+1
  7. right = 2*i+2
  8. largest = i
  9. if left < arrLen and arr[left] > arr[largest]:
  10. largest = left
  11. if right < arrLen and arr[right] > arr[largest]:
  12. largest = right
  13. if largest != i:
  14. swap(arr, i, largest)
  15. heapify(arr, largest)
  16. def swap(arr, i, j):
  17. arr[i], arr[j] = arr[j], arr[i]
  18. def heapSort(arr):
  19. global arrLen
  20. arrLen = len(arr)
  21. buildMaxHeap(arr)
  22. for i in range(len(arr)-1,0,-1):
  23. swap(arr,0,i)
  24. arrLen -=1
  25. heapify(arr, 0)
  26. 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. }
  11. func buildMaxHeap(arr []int, arrLen int) {
  12. for i := arrLen / 2; i >= 0; i-- {
  13. heapify(arr, i, arrLen)
  14. }
  15. }
  16. func heapify(arr []int, i, arrLen int) {
  17. left := 2*i + 1
  18. right := 2*i + 2
  19. largest := i
  20. if left < arrLen && arr[left] > arr[largest] {
  21. largest = left
  22. }
  23. if right < arrLen && arr[right] > arr[largest] {
  24. largest = right
  25. }
  26. if largest != i {
  27. swap(arr, i, largest)
  28. heapify(arr, largest, arrLen)
  29. }
  30. }
  31. func swap(arr []int, i, j int) {
  32. arr[i], arr[j] = arr[j], arr[i]
  33. }

4. Java 代码实现

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

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. }
  8. function heapify(&$arr, $i)
  9. {
  10. global $len;
  11. $left = 2 * $i + 1;
  12. $right = 2 * $i + 2;
  13. $largest = $i;
  14. if ($left < $len && $arr[$left] > $arr[$largest]) {
  15. $largest = $left;
  16. }
  17. if ($right < $len && $arr[$right] > $arr[$largest]) {
  18. $largest = $right;
  19. }
  20. if ($largest != $i) {
  21. swap($arr, $i, $largest);
  22. heapify($arr, $largest);
  23. }
  24. }
  25. function swap(&$arr, $i, $j)
  26. {
  27. $temp = $arr[$i];
  28. $arr[$i] = $arr[$j];
  29. $arr[$j] = $temp;
  30. }
  31. function heapSort($arr) {
  32. global $len;
  33. $len = count($arr);
  34. buildMaxHeap($arr);
  35. for ($i = count($arr) - 1; $i > 0; $i--) {
  36. swap($arr, 0, $i);
  37. $len--;
  38. heapify($arr, 0);
  39. }
  40. return $arr;
  41. }