堆排序

堆排序（英语: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 < arr)             //先比较两个子节点大小，选择最大的            son++;        if (arr > arr) //如果父节点大於子节点代表调整完毕，直接跳出函数            return;        else  //否则交换父子内容再继续子节点和孙节点比较        {            swap(&arr, &arr);            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, &arr);        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);    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 < arr) //先比较两个子节点大小，选择最大的            son++;        if (arr > arr) //如果父节点大於子节点代表调整完毕，直接跳出函数            return;        else  //否则交换父子内容再继续子节点和孙节点比较        {            swap(arr, arr);            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, arr);        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 << ' ';    cout << endl;    system("pause");}

堆排序Java语言

        public static int heapSort(int array) {        //这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1        for (int i = array.length / 2 - 1; i >= 0; i--) {              adjustHeap(array, i, array.length);  //调整堆        }         // 上述逻辑，建堆结束        // 下面，开始排序逻辑        for (int j = array.length - 1; j > 0; j--) {            // 元素交换,作用是去掉大顶堆            // 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置            swap(array, 0, j);            // 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。            // 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因            // 而这里，实质上是自上而下，自左向右进行调整的            adjustHeap(array, 0, j);        }        return array;    }         public static void adjustHeap(int array, int i, int length) {        // 先把当前元素取出来，因为当前元素可能要一直移动        int temp = array;        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {  //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树            // 让k先指向子节点中最大的节点            if (k + 1 < length && array < array) {  //如果有右子树,并且右子树大于左子树                k++;            }            //如果发现结点(左右子结点)大于根结点，则进行值的交换            if (array > temp) {                swap(array, i, k);                // 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断                    i  =  k;                        } else {  //不用交换，直接终止循环                break;            }        }    }         public static void swap(int arr, int a, int b) {        int temp = arr;        arr = arr;        arr = temp;    }

堆排序Python语言

def big_endian(arr,start,end):        root=start        child=root*2+1 #左孩子        while child<=end:    #孩子比最后一个节点还大，也就意味着最后一个叶子节点了，就得跳出去一次循环，已经调整完毕             if child+1<=end and arr<arr:        #为了始终让其跟子元素的较大值比较，如果右边大就左换右，左边大的话就默认                       child+=1                    if arr<arr:        #父节点小于子节点直接交换位置，同时坐标也得换，这样下次循环可以准确判断：是否为最底层，        #是不是调整完毕                            arr,arr=arr,arr                            root=child                            child=root*2+1                    else:                       break        def heap_sort(arr): #无序区大根堆排序        first=len(arr)//2 - 1        for start in range(first,-1,-1):    #从下到上，从左到右对每个节点进行调整，循环得到非叶子节点                big_endian(arr,start,len(arr)-1) #去调整所有的节点        for end in range(len(arr)-1,0,-1):                arr,arr=arr,arr #顶部尾部互换位置                big_endian(arr,0,end-1) #重新调整子节点的顺序，从顶开始调整        return arr    def main():        l=        print(heap_sort(l))if __name__=="__main__":        main()

堆排序PHP语言

function hsort(array &$arr, $len){    $idx = $len - 1;    //创建堆操作，并使得堆有序    for($k=floor($len/2); $k>=0; $k--){        sink($arr, $k, $idx);    }     //排序操作    while($idx>0){        //获取最大值操作        list($arr, $arr) = , $arr];        $idx--;        //堆调整下沉        sink($arr, 0, $idx);            }}//堆调整下沉，小数字下沉function sink(array &$arr, $low, $high){    //从$low开始找子节点    while($low*2+1<=$high){        //获取low的直接左子节点        $j = $low*2+1;        //判断$low位置节点子节点中的较大子节点        if($j<$high && $arr<$arr){            $j++;        }        if($arr>$arr){            break;        }        //交换low节点和子节点的值        list($arr, $arr) = , $arr];        //继续排查下沉后子节点是否需要进行下沉操作        $low = $j;    }}$a = ;hsort($a, count($a));print_r($a);