堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:
大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;
堆排序的平均时间复杂度为 Ο(nlogn)。
将待排序序列构建成一个堆 H[0……n-1],根据(升序降序需求)选择大顶堆或小顶堆;
把堆首(最大值)和堆尾互换;
把堆的尺寸缩小 1,并调用 shift_down(0),目的是把新的数组顶端数据调整到相应位置;
重复步骤 2,直到堆的尺寸为 1。
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;}
def buildMaxHeap(arr):import mathfor i in range(math.floor(len(arr)/2),-1,-1):heapify(arr,i)def heapify(arr, i):left = 2*i+1right = 2*i+2largest = iif left < arrLen and arr[left] > arr[largest]:largest = leftif right < arrLen and arr[right] > arr[largest]:largest = rightif 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 arrLenarrLen = len(arr)buildMaxHeap(arr)for i in range(len(arr)-1,0,-1):swap(arr,0,i)arrLen -=1heapify(arr, 0)return arr
func heapSort(arr []int) []int {arrLen := len(arr)buildMaxHeap(arr, arrLen)for i := arrLen - 1; i >= 0; i-- {swap(arr, 0, i)arrLen -= 1heapify(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 + 1right := 2*i + 2largest := iif 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]}
public class HeapSort implements IArraySort {@Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝,不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);int len = arr.length;buildMaxHeap(arr, len);for (int i = len - 1; i > 0; i--) {swap(arr, 0, i);len--;heapify(arr, 0, len);}return arr;}private void buildMaxHeap(int[] arr, int len) {for (int i = (int) Math.floor(len / 2); i >= 0; i--) {heapify(arr, i, len);}}private void heapify(int[] arr, int i, int len) {int left = 2 * i + 1;int right = 2 * i + 2;int 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, len);}}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}
function buildMaxHeap(&$arr){global $len;for ($i = floor($len/2); $i >= 0; $i--) {heapify($arr, $i);}}function heapify(&$arr, $i){global $len;$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){$temp = $arr[$i];$arr[$i] = $arr[$j];$arr[$j] = $temp;}function heapSort($arr) {global $len;$len = count($arr);buildMaxHeap($arr);for ($i = count($arr) - 1; $i > 0; $i--) {swap($arr, 0, $i);$len--;heapify($arr, 0);}return $arr;}