堆排序

真言

头会疼，但是总有停止的那一刻，抓住那一刻去总结。否则头白疼啦。

引言

堆排序算法在大量数据排序中还是比较实用的，现在有好几个排序算法啦，有什么优缺点，也可以总结了。

思路

堆排序的算法就是两步建堆和维护。 建堆一次，维护堆 n-2 次（第一次维护的时候 堆规模为 n-1，最后一次维护的时候堆规模为 2）。 举个例子吧，我喜欢图，我相信你们也喜欢。 一共有10个数据，如下
建堆过程中如下数据如下变化




建堆完毕。 交换数据，堆规模建减小，维护堆，直至堆规模为 1.过程如下 第一次
第二次
第三次

第四次
第五次
第六次
第七次
第八次
最后成为

实验

代码

test.cpp

// choice sort 
#include
     
      
#include
      
        #include
       
         using namespace std; // use 1000,00 to test int const size = 1000000; // template function declare template
        
          void Heap_sort(T *data,const int length); // template function template
         
           void Make_heap(T *data,const int length); // template function template
          
            void Heap_downcast(T *data,int i,const int length); int main() { DWORD S,E; int * data = new int[size]; for(int i =0 ; i
           
             void Heap_sort(T *data,const int length) { if(data != NULL && length >= 0) { Make_heap(data,length); T d; int L = length; while(L>1) { d=data[L-1]; data[L-1] = data[0]; data[0] =d; L--; Heap_downcast(data,0,L); } cout<
            
              void Make_heap(T *data,const int length) { if(data != NULL && length >= 0) { for(int i=length/2-1;i>=0;i--) { Heap_downcast(data,i,length); } } else { cout<<"exception of input make heap"<
             
               void Heap_downcast(T *data,int i,const int length) { if(data != NULL && length >= 0) { T max ; // have two children while(i*2+2 
              
               = data[i*2+1] && max >= data[2*i+2]) break; // right child bigger if( data[i*2+2]>data[2*i+1] && data[i*2+2]>max) { max = data[i*2+2]; data[i*2+2] = data[i]; data[i] = max; i = i*2+2; } // left child bigger else if( data[i*2+1] >= data[2*i+2] && data[i*2+1]>max ) { max = data[i*2+1]; data[i*2+1] = data[i]; data[i] = max; i = i*2+1; } } // have one child if(i*2+1 < length) { if(data[i*2+1]>data[i]) { max = data[i*2+1]; data[i*2+1] = data[i]; data[i] = max; } } } else { cout<<"exception of input Heap_downcast"<