堆排序
堆排序(英語:Heapsort)是指利用堆積這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構,並同時滿足堆積的性質:即子節點的鍵值或索引總是小於(或者大於)它的父節點。
堆排序 | |
---|---|
![]() 堆排序算法的演示。首先,將元素進行重排,以符合堆的條件。圖中排序過程之前簡單地繪出了堆樹的結構。 | |
概況 | |
類別 | 排序算法 |
資料結構 | 陣列 |
複雜度 | |
平均時間複雜度 | |
最壞時間複雜度 | |
最優時間複雜度 | [1] |
空間複雜度 | total, auxiliary |
最佳解 | 不是 |
相關變量的定義 |
概述
編輯若以升序排序說明,把陣列轉換成最大堆積(Max-Heap Heap),這是一種滿足最大堆積性質(Max-Heap Property)的二元樹:對於除了根之外的每個節點i, A[parent(i)] ≥ A[i]。
重複從最大堆積取出數值最大的結點(把根結點和最後一個結點交換,把交換後的最後一個結點移出堆),並讓殘餘的堆積維持最大堆積性質。
堆積節點的訪問
編輯通常堆積是通過一維數組來實現的。在陣列起始位置為0的情形中:
- 父節點i的左子節點在位置 ;
- 父節點i的右子節點在位置 ;
- 子節點i的父節點在位置 ;
堆積的操作
編輯在堆積的資料結構中,堆積中的最大值總是位於根節點(在優先隊列中使用堆積的話堆積中的最小值位於根節點)。堆積中定義以下幾種操作:
- 最大堆積調整(Max Heapify):將堆積的末端子節點作調整,使得子節點永遠小於父節點
- 建立最大堆積(Build Max Heap):將堆積中的所有數據重新排序
- 堆排序(HeapSort):移除位在第一個數據的根節點,並做最大堆積調整的遞迴運算
實作範例
編輯C語言
編輯#include <stdio.h>
#include <stdlib.h>
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 <= end) { // 若子節點指標在範圍內才做比較
if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小,選擇最大的
son++;
if (arr[dad] > 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 < len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
C++
編輯#include <iostream>
#include <algorithm>
using namespace std;
void max_heapify(int arr[], int start, int end) {
// 建立父節點指標和子節點指標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { // 若子節點指標在範圍內才做比較
if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小,選擇最大的
son++;
if (arr[dad] > 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 < len; i++)
cout << arr[i] << ' ';
cout << endl;
return 0;
}
Java
編輯import java.util.Arrays;
public class HeapSort {
private int[] arr;
public HeapSort(int[] arr) {
this.arr = arr;
}
/**
* 堆排序的主要入口方法,共两步。
*/
public void sort() {
/*
* 第一步:将数组堆化
* beginIndex = 第一个非叶子节点。
* 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
* 叶子节点可以看作已符合堆要求的节点,根节点就是它自己且自己以下值为最大。
*/
int len = arr.length - 1;
int beginIndex = (arr.length >> 1)- 1;
for (int i = beginIndex; 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 <= len && arr[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
編輯#!/usr/bin/env python
#-*-coding:utf-8-*-
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 and lst[child] < lst[child + 1]:
child += 1
if lst[root] < lst[child]:
lst[root], lst[child] = lst[child], lst[root]
root = child
else:
break
# 創建最大堆
for start in range((len(lst) - 2) // 2, -1, -1):
sift_down(start, len(lst) - 1)
# 堆排序
for end in range(len(lst) - 1, 0, -1):
lst[0], lst[end] = lst[end], lst[0]
sift_down(0, end - 1)
return lst
if __name__ == "__main__":
l = [9, 2, 1, 7, 6, 8, 5, 3, 4]
heap_sort(l)
JavaScript
編輯Array.prototype.heap_sort = function() {
var arr = this.slice(0);
function swap(i, j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
function max_heapify(start, end) {
//建立父節點指標和子節點指標
var dad = start;
var son = dad * 2 + 1;
if (son >= end)//若子節點指標超過範圍直接跳出函數
return;
if (son + 1 < end && arr[son] < arr[son + 1])//先比較兩個子節點大小,選擇最大的
son++;
if (arr[dad] < arr[son]) {//如果父節點小於子節點時,交換父子內容再繼續子節點和孫節點比較
swap(dad, son);
max_heapify(son, end);
}
}
var len = arr.length;
//初始化,i從最後一個父節點開始調整
for (var i = Math.floor(len / 2) - 1; i >= 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
編輯<?php
function swap(&$x, &$y) {
$t = $x;
$x = $y;
$y = $t;
}
function max_heapify(&$arr, $start, $end) {
//建立父節點指標和子節點指標
$dad = $start;
$son = $dad * 2 + 1;
if ($son >= $end)//若子節點指標超過範圍直接跳出函數
return;
if ($son + 1 < $end && $arr[$son] < $arr[$son + 1])//先比較兩個子節點大小,選擇最大的
$son++;
if ($arr[$dad] <= $arr[$son]) {//如果父節點小於子節點時,交換父子內容再繼續子節點和孫節點比較
swap($arr[$dad], $arr[$son]);
max_heapify($arr, $son, $end);
}
}
function heap_sort($arr) {
$len = count($arr);
//初始化,i從最後一個父節點開始調整
for ($i = ceil($len/2) - 1; $i >= 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 < count($arr); $i++)
echo $arr[$i] . ' ';
?>
Go
編輯package main
import (
"fmt"
)
func HeapSort(array []int) {
m := len(array)
s := m/2
for i := s; 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 <= end && array[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)
}
function HeapSort(array)
function adjust(l,u)
while true
j = 2*l # 左子點
if (j>u) # 代表沒有子點
break
end
if ((j+1) <= u) # 有右子點
if (array[j] < array[j+1])
j += 1 #比較左右子點
end
end
if (array[j] > 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<T: Ord + Copy>(data: &mut [T], pos: usize, end: usize) {
let mut dad = pos;
let mut son = dad * 2 + 1;
while son <= end {
if son < end && data[son] < data[son + 1] {
son += 1;
}
if data[dad] > data[son] {
return;
} else {
data.swap(dad, son);
dad = son;
son = dad * 2 + 1;
}
}
}
fn heap_sort<T:Ord+Copy>(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());
}
原地堆排序
編輯基於以上堆積相關的操作,我們可以很容易的定義堆排序。例如,假設我們已經讀入一系列數據並創建了一個堆積,一個最直觀的算法就是反覆的調用del_max()
函數,因為該函數總是能夠返回堆積中最大的值,然後把它從堆積中刪除,從而對這一系列返回值的輸出就得到了該序列的降序排列。真正的原地堆排序使用了另外一個小技巧。堆排序的過程是:
- 建立一個堆積
- 把堆積首(最大值)和堆積尾互換
- 把堆積的尺寸縮小1,並調用
shift_down(0)
,目的是把新的數組頂端數據調整到相應位置 - 重複步驟2,直到堆積的尺寸為1
平均複雜度
編輯參考
編輯- ^ R. Schaffer, R. Sedgewick. The Analysis of Heapsort. Journal of Algorithms. 1993-07, 15 (1): 76–100 [2022-10-02]. doi:10.1006/jagm.1993.1031. (原始內容存檔於2022-01-27) (英語).