1. 概述

  • 思路：利用大顶堆和小顶堆的完全二叉树的数据结构（存在一维数组中，按照从上到下，从左到右），来实现堆排序。将堆顶元素值与第n-k个元素交换，然后对n-k个元素进行一次（大/小）顶堆排序，递归执行到k=n的情况，此时的堆就是升序或降序的。

  • 稳定性：不稳定（当往一个完全二叉树的堆中，插入一个数值，就影响了数据存在的顺序）

    2. 实现代码

    ```php <?php class HeapSort { private array $ori; public array $new = []; public function __construct(array $arr) {

    1.   $this->ori = $arr;
    2.   $r = $this->heapSort($this->ori, count($this->ori));
    3.   $this->new = $r;

    }

    // 堆排序 private function heapSort(array $tree, int $n) {

    1.   $tree = $this->buildHeap($tree, $n);
    2.   for ($i = $n - 1; $i >= 0; $i--) {
    3.       $tree = $this->swap($tree, $i, 0);
    4.       $tree = $this->heapify($tree, $i, 0);
    5.   }
    6.   return $tree;

    }

    // 创建一个大顶堆 // 倒序节点，做heapify，（能将最大的数往二叉树上面提） private function buildHeap(array $tree, int $n) {

    1.   $lastNode = $n - 1;
    2.   $parent = floor(($lastNode - 1) / 2);
    3.   for ($i = $parent; $i >= 0; $i--) {
    4.       $tree = $this->heapify($tree, $n, $i);
    5.   }
    6.   return $tree;

    }

    // 对当前节点及其子节点做排序 private function heapify(array $arr, $n, $i) {

    1.   echo '$n: ' . $n . "\t" . '$i: ' . $i . "\n";
    2.   if ($i >= $n) return $arr;
    4.   $c1 = 2 * $i + 1;
    5.   $c2 = 2 * $i + 2;
    6.   $max = $i;
    7.   $c1 < $n && $arr[$c1] > $arr[$max] && $max = $c1;
    8.   $c2 < $n && $arr[$c2] > $arr[$max] && $max = $c2;
    10.   if ($max != $i) {
    11.       $arr = $this->swap($arr, $max, $i);
    12.       $arr = $this->heapify($arr, $n, $max);
    13.   }
    15.   return $arr;

    }

    // 交换两个数组值 private function swap(array $arr, int $i, int $j) {

    1.   $tmp = $arr[$i];
    2.   $arr[$i] = $arr[$j];
    3.   $arr[$j] = $tmp;
    4.   return $arr;

    } }

$arr = [9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2]; $cls = new HeapSort($arr); echo implode(‘,’, $cls->new); ```