堆排序

概述

一种树型选择排序，时间复杂度为O(n*log2(n))。

实现原理

1.子堆调整函数adjustdown
将不超过3个元素的小堆，调整成大顶堆
2.将排序表从1到n的位置理解成堆，可见排序表由n/2个小堆构成
3.从最后一个小堆开始向前循环，将每个小堆调整成大顶堆，当第一个小堆调整完成时，1号位存放的就是最大的数
4.将1号位的数据和8号位的数据互换，将排序表从1到n-1的位置理解成堆，从n-1位置向前循环调整成大顶堆……

代码(C语言)

    #include "pch.h"  
    #include <iostream>  

    using namespace std;  

    void adjustdown(int A[], int k,int len) {  
        A[0] = A[k];  
        for (int j = k * 2; j <=len; j++) {  
            if (A[j] < A[j + 1]&&j+1<=len) {  
                j++;  
            }  
            if (A[0] < A[j]) {  
                A[k] = A[j];  
                A[j] = A[0];  
            }  
            break;  
        }  
    }  

    void heap_sort(int A[],int length) {  
        for (int i = length; i >=1; i--) {  
            for (int k = i / 2; k >= 1; k--) {  
                adjustdown(A, k,i);  
            }  
            A[0] = A[1];  
            A[1] = A[i];  
            A[i] = A[0];  
        }  

    }  

    int main()  
    {  
        int A[] = {999, 2,8,4,1,5,9,7,6};//定义数组A,0号位999占位  
        heap_sort(A,7);//对数组A排序  
        //循环输出A数组  
        int i;  
        for ( i = 1; i < 8; i++) {  
            cout <<"-----"<< A[i] << endl;  
        }  

        system("pause");  
    }