【Sort】HeapSort

　　堆排序，时间复杂度O(N log N)，实际使用中慢于使用Sedgewick增量的增量排序。

　　大致思路：

　　1.先在数组中建堆，如果是增量排序，则需要建一个大堆

　　2.每循环一次，把最大的数，也就是nums[0]，放入堆尾，同时把nums[0]下滤

 void heapsort(int *nums,int n)

 {

     int i;

     for(i=n/;i>=;i--)

         percdown(nums,i,n);

     for(i=n-;i>;i--)

     {

         nums[]^=nums[i];

         nums[i]^=nums[];

         nums[]^=nums[i];

         percdown(nums,,i);

     }

 }

 void percdown(int *nums,int p,int n)

 {

     int tmp;

     int child;

     for(tmp=nums[p];*p+<n;p=child)

     {

         child=*p+;

         if(*p+!=n&&nums[*p+]>nums[child])

             child++;

         if(nums[child]>tmp)

             nums[p]=nums[child];

             else

                 break;

     }

     nums[p]=tmp;

 }

巴特西

【Sort】HeapSort

最新文章

热门文章