【大话数据结构C语言】68 堆排序

堆排序算法是利用堆进行排序的方法

基本思想是将待排序的序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根结点。

将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值，如此反复执行，最后就可以得到一个有序序列了

堆排序的时间复杂度为nlogn，这个性能要远远好于冒泡，简单选择，直接插入排序的时间复杂度

空间复杂度上，它只有一个用来交换的暂存单元，也是非常的不错

但是由于记录的比较与交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法

另外，由于初始构建堆需要比较次数很多，所以不适合待排序个数比较少的情况

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int count = 0;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void swap(int k[], int i, int j)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int temp;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          temp = k[i];
     
    
   

    

     

    
    

     

          k[i] = k[j];
     
    
   

    

     

    
    

     

          k[j] = temp;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void HeapAdjust(int k[], int s, int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int i, temp;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          temp = k[s];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    for( i=2*s; i <= n; i*=2 )
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              count++;
     
    
   

    

     

    
    

     
        if( i < n && k[i] < k[i+1] )
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  i++;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        if( temp >= k[i] )
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            break;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

              k[s] = k[i];
     
    
   

    

     

    
    

     

              s = i;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          k[s] = temp;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void HeapSort(int k[], int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int i;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

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

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        HeapAdjust(k, i, n);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

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

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        swap(k, 1, i);
     
    
   

    

     

    
    

     
        HeapAdjust(k, 1, i-1);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int i, a[10] = {-1, 5, 2, 6, 0, 3, 9, 1, 7, 4};
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    HeapSort(a, 9);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    printf("总共执行 %d 次比较!", count);
     
    
   

    

     

    
    

     
    printf("排序后的结果是：");
     
    
   

    

     

    
    

     
    for( i=1; i < 10; i++ )
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        printf("%d", a[i]);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    printf("\n\n");
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。

原文链接：allen5g.blog.csdn.net/article/details/117173481