堆排序 堆排序（）是指利用-{zh-cn:堆;堆积;堆积;这种数据结构所设计的一种排序算法。-{zh-cn:堆;堆积;堆积;是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。 概述. 若以升序排序说明，把阵列转换成最大堆积（Max-Heap Heap），这是一种满足最大堆积性质（Max-Heap Property）的二元树：对于除了根之外的每个节点i, A[parent(i)] ≥ A[i]。 重复从最大堆积取出数值最大的结点（把根结点和最后一个结点交换，把交换后的最后一个结点移出堆），并让残余的堆积维持最大堆积性质。 -{zh-cn:堆;堆积;堆积;节点的访问. 通常-{zh-cn:堆;堆积;堆积;是通过一维数组来实现的。在阵列起始位置为0的情形中： -{zh-cn:堆;堆积;堆积;的操作. 在-{zh-cn:堆;堆积;堆积;的资料结构中，-{zh-cn:堆;堆积;堆积;中的最大值总是位于根节点（在优先队列中使用-{zh-cn:堆;堆积;堆积;的话-{zh-cn:堆;堆积;堆积;中的最小值位于根节点）。-{zh-cn:堆;堆积;堆积;中定义以下几种操作： 实作范例. C语言. void swap(int *a, int *b) { int temp = *b; *b = *a; *a = temp; void max_heapify(int arr[], int start, int end) { // 建立父节点指标和子节点指标 int dad = start; int son = dad * 2 + 1; while (son arr[son]) //如果父节点大于子节点代表调整完毕，直接跳出函数 return; else { // 否则交换父子内容再继续子节点和孙节点比较 swap(&arr[dad], &arr[son]); dad = son; son = dad * 2 + 1; void heap_sort(int arr[], int len) { int i; // 初始化，i从最后一个父节点开始调整 for (i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1); // 先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕 for (i = len - 1; i > 0; i--) { swap(&arr[0], &arr[i]); max_heapify(arr, 0, i - 1); int main() { int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 }; int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr, len); int i; for (i = 0; i arr[son]) // 如果父节点大于子节点代表调整完毕，直接跳出函数 return; else { // 否则交换父子内容再继续子节点和孙节点比较 swap(arr[dad], arr[son]); dad = son; son = dad * 2 + 1; void heap_sort(int arr[], int len) { // 初始化，i从最后一个父节点开始调整 for (int i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1); // 先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕 for (int i = len - 1; i > 0; i--) { swap(arr[0], arr[i]); max_heapify(arr, 0, i - 1); int main() { int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 }; int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr, len); for (int i = 0; i = 0; i--) maxHeapify(i, len); * 第二步：对堆化数据排序 * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。 * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。 * 直至未排序的堆长度为 0。 for (int i = len; i > 0; i--) { swap(0, i); maxHeapify(0, i - 1); private void swap(int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; * 调整索引为 index 处的数据，使其符合堆的特性。 * @param index 需要堆化处理的数据的索引 * @param len 未排序的堆（数组）的长度 private void maxHeapify(int index, int len) { int li = (index « 1) + 1; // 左子节点索引 int ri = li + 1; // 右子节点索引 int cMax = li; // 子节点值最大索引，默认左子节点。 if (li > len) return; // 左子节点索引超出计算范围，直接返回。 if (ri arr[li]) // 先判断左右子节点，哪个较大。 cMax = ri; if (arr[cMax] > arr[index]) { swap(cMax, index); // 如果父节点被子节点调换， maxHeapify(cMax, len); // 则需要继续判断换下后的父节点是否符合堆的特性。 * 测试用例 * 输出： * [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9] public static void main(String[] args) { int[] arr = new int[] {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6}; new HeapSort(arr).sort(); System.out.println(Arrays.toString(arr)); Python. def heap_sort(lst): def sift_down(start, end): """最大堆调整""" root = start while True: child = 2 * root + 1 if child > end: break if child + 1 = end)//若子节点指标超过范围直接跳出函数 return; if (son + 1 = 0; i--) max_heapify(i, len); //先将第一个元素和已排好元素前一位做交换，再从新调整，直到排序完毕 for (var i = len - 1; i > 0; i--) { swap(0, i); max_heapify(0, i); return arr; var a = [3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6]; console.log(a.heap_sort()); PHP. = $end)//若子节点指标超过范围直接跳出函数 return; if ($son + 1 = 0; $i--) max_heapify($arr, $i, $len); //先将第一个元素和已排好元素前一位做交换，再从新调整，直到排序完毕 for ($i = $len - 1; $i > 0; $i--) { swap($arr[0], $arr[$i]); max_heapify($arr, 0, $i); return $arr; $arr = array(3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6); $arr = heap_sort($arr); for ($i = 0; $i -1; i-- { heap(array, i, m-1) for i := m-1; i > 0; i-- { array[i], array[0] = array[0], array[i] heap(array, 0, i-1) func heap(array []int, i, end int){ l := 2*i+1 if l > end { return n := l r := 2*i+2 if r array[l]{ n = r if array[i] > array[n]{ return array[n], array[i] = array[i], array[n] heap(array, n, end) func main() { array := []int{ 55, 94,87,1,4,32,11,77,39,42,64,53,70,12,9, HeapSort(array) fmt.Println(array) Julia (程式语言). function HeapSort(array) function adjust(l,u) while true j = 2*l # 左子点 if (j>u) # 代表没有子点 break end if ((j+1) array[l]) #比较父点跟子点 array[l], array[j]= array[j], array[l] l = j # 有交换 else break # 没交换跳出回圈 end end end n = length(array) for i in n:-1:1 # 建 max Heap adjust(i,n) end #持续把第一个(最大)的元素最后一个交换 array[n],array[1]=array[1],array[n] for i in n-1:-1:1 adjust(1,i) array[i],array[1]=array[1],array[i] end return array end Rust. fn max_heapify(data: &mut [T], pos: usize, end: usize) { let mut dad = pos; let mut son = dad * 2 + 1; while son data[son] { return; } else { data.swap(dad, son); dad = son; son = dad * 2 + 1; fn heap_sort(data: &mut[T]) { let len = data.len(); for i in (0..=len / 2 - 1).rev() { max_heapify(data, i, len - 1); for i in (1..=len - 1).rev() { data.swap(0, i); max_heapify(data, 0, i - 1); fn main() { let mut nums = vec![9, 2, 1, 7, 6, 8, 5, 3, 4]; heap_sort(nums.as_mut_slice()); 原地堆排序. 基于以上-{zh-cn:堆;堆积;堆积;相关的操作，我们可以很容易的定义堆排序。例如，假设我们已经读入一系列数据并创建了一个-{zh-cn:堆;堆积;堆积;，一个最直观的算法就是反复的调用codice_1函数，因为该函数总是能够返回-{zh-cn:堆;堆积;堆积;中最大的值，然后把它从-{zh-cn:堆;堆积;堆积;中删除，从而对这一系列返回值的输出就得到了该序列的降序排列。真正的原地堆排序使用了另外一个小技巧。堆排序的过程是： 平均复杂度. 堆排序的平均时间复杂度为formula_6，空间复杂度为formula_7。