排序算法-堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

1. 算法步骤

将待排序序列构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆；

把堆首（较大值）和堆尾互换；

把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

重复步骤 2，直到堆的尺寸为 1。

2. 动图演示

3. 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; 

arr = 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 **th 
for i in range(**th.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, arr[j] = arr[j], arr 


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

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, arr[j] = arr[j], arr 

}

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; 

arr = 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; 
}