排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是堆排序算法：
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
- 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
- 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。
1. 算法步骤
创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。
2. 动图演示
代码实现
JavaScript
实例
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;
}
Python
实例
def buildMaxHeap(arr):
import math
for i in range(math.floor(len(arr)/2),-1,-1):
heapify(arr,i)
def heapify(arr, i):
left = 2*i+1
right = 2*i+2
largest = i
if left < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right
if 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 arrLen
arrLen = len(arr)
buildMaxHeap(arr)
for i in range(len(arr)-1,0,-1):
swap(arr,0,i)
arrLen -=1
heapify(arr, 0)
return arr
Go
实例
func heapSort(arr []int) []int {
arrLen := len(arr)
buildMaxHeap(arr, arrLen)
for i := arrLen - 1; i >= 0; i-- {
swap(arr, 0, i)
arrLen -= 1
heapify(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 + 1
right := 2*i + 2
largest := i
if 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]
}
Java
实例
public class HeapSort implements IArraySort {
@Override
public 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;
}
}
PHP
实例
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;
}
C
实例
#include
#include
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("
");
return 0;
}
C++
实例
#include #include 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;} 参考文章：
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/7.heapSort.md
https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F
以下是热心网友对堆排序算法的补充，仅供参考：
热心网友提供的补充1：
上方又没些 C# 的堆排序，艾孜尔江补充如下：
///
/// 堆排序
///
/// 待排序数组
static void HeapSort(int[] arr)
{
int vCount = arr.Length;
int[] tempKey = new int[vCount + 1];
// 元素索引从1开始
for (int i = 0; i < vCount; i++)
{
tempKey[i + 1] = arr[i];
}
// 初始数据建堆（从含最后一个结点的子树开始构建，依次向前，形成整个二叉堆）
for (int i = vCount / 2; i >= 1; i--)
{
Restore(tempKey, i, vCount);
}
// 不断输出堆顶元素、重构堆，进行排序
for (int i = vCount; i > 1; i--)
{
int temp = tempKey[i];
tempKey[i] = tempKey[1];
tempKey[1] = temp;
Restore(tempKey, 1, i - 1);
}
//排序结果
for (int i = 0; i < vCount; i++)
{
arr[i] = tempKey[i + 1];
}
}
///
/// 二叉堆的重构（针对于已构建好的二叉堆首尾互换之后的重构）
///
///
/// 根结点j
/// 结点数
static void Restore(int[] arr, int rootNode, int nodeCount)
{
while (rootNode <= nodeCount / 2) // 保证根结点有子树
{
//找出左右儿子的最大值
int m = (2 * rootNode + 1 <= nodeCount && arr[2 * rootNode + 1] > arr[2 * rootNode]) ? 2 * rootNode + 1 : 2 * rootNode;
if (arr[m] > arr[rootNode])
{
int temp = arr[m];
arr[m] = arr[rootNode];
arr[rootNode] = temp;
rootNode = m;
}
else
{
break;
}
}
}
热心网友提供的补充2：
堆排序是不稳定的排序！
既然如此，每次构建大顶堆时，在 父节点、左子节点、右子节点取三者中最大者作为父节点就行。我们追寻的只是最终排序后的结果，所以可以简化其中的步骤。
我将个人写的 Java 代码核心放在下方，有兴趣的同学可以一起讨论下：
public int[] sort(int a[]) {
int len = a.length - 1;
for (int i = len; i > 0; i--) {
maxHeap(a, i);
//交换 跟节点root 与 最后一个子节点i 的位置
swap(a, 0, i);
//i--无序数组尺寸减少了
}
return a;
}
/**构建一个大顶堆（完全二叉树 ）
* 从 最后一个非叶子节点 开始，若父节点小于子节点，则互换他们两的位置。然后依次从右至左，从下到上进行！
* 最后一个非叶子节点，它的叶子节点 必定包括了最后一个（叶子）节点，所以 最后一个非叶子节点是 a[（n+1）/2-1]
* @param a
* @param lastIndex 这个数组的最后一个元素
*/
static void maxHeap(int a[], int lastIndex) {
for (int i = (lastIndex + 1) / 2 - 1; i >= 0; i--) {
//反正 堆排序不稳定，先比较父与左子，大则交换；与右子同理。（不care 左子与右子位置是否变了！）
if (i * 2 + 1 <= lastIndex && a[i] < a[i * 2 + 1]) {
swap(a, i, i * 2 + 1);
}
if (i * 2 + 2 <= lastIndex && a[i] < a[i * 2 + 2]) {
swap(a, i, i * 2 + 2);
}
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
以上为堆排序算法详细介绍，插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点，用一张图概括：
关于时间复杂度
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
名词解释：
n：数据规模
k："桶"的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
