《算法三部曲》 之 排序和查找算法（中篇）

Knuth学徒

排序和查找算法目录:
      

上篇:https://www.chinapyg.com/viewthr ... mp;extra=#pid519519

     算法类的帖子曾经我写过不少, 由于进来专业课繁忙,  一直没时间更新, 我非常愧疚。   

     今天抽空讲一讲另一个比较高效的排序算法 —— 堆排序 .

     堆排序, 顾名思义 和堆有关,  这里的堆指的是 二叉堆 , 如果对于堆这个数据结构不是很熟悉的朋友可以参见我写的这篇帖子:  
     https://www.chinapyg.com/viewthr ... &extra=page%3D1

     于是, 我先说下堆排的原理：

     首先, 根据 堆的性质 ，堆顶元素一定是整个堆中最（大）小的元素 , 于是呢, 我们可以把堆顶元素放到数组的首位,  然后将堆顶元素从堆中去除, 记得在去除的时候堆会自动进行调整, 使它保持堆的性质.

     然后, 再将堆顶元素放到数组的第二位 , 再将这个堆顶元素从堆中去除，重新调整堆结构.

     ……

     这样进行 N 次 后，N个数据都有序的存放在 数组中了.
     也许有人会问, 为什么这样就是有序的呢？   

     我证明如下:  假设堆中初始有 N 个元素 ，分别是 （a1 , a2 , a3 , .... , aN）
     每次我们拿出 堆中的最小的元素， 即 Min{a1,a2,a3.....aN},将它放在数组的第i个位置
     那么,可以保证 最后数组从第i+1位到第N位 都比 第i位要大！

     因为 i 具有任意性, 所以最后线性表中的每个元素都比它后面的元素要大, 就相当于是从小到大有序了.（证毕 #）

     既然这种算法可以被证明是正确的, 我们就可以拿来使用.

     注: 这里堆的实现方法我并不采用 C++ 中的STL , 因为也许有朋友认为我是借助了库函数, 所以, 这里的堆实现我全部是手写的.

     首先在 Heap.h 头文件中加入如下的代码:

1. 
   
2.      #ifndef Heap_H
   
3.      #define Heap_H
   
4. 
   
5.      class MinHeap{
   
6.             private:
   
7.                    int count;            
   
8.                    int val [MAX];     
   
9.                    void down(int position);     //最小堆的调整函数
   
10.                    //void up(int position)        最大堆的调整函数
    
11.             public:
    
12.                   MinHeap();                       //构造函数
    
13.                   void Insert(int data );      
    
14.                   int  Top_Remove() ;      
    
15.                   bool  is_empty();           
    
16.                   int size();                       
    
17.      };
    
18. 
    
19.      #endif
    
20. 
    
21.      

复制代码

以上都是堆结构的类声明, 这些都可以在我之前发的帖子里找到, 这里就做一下搬运了, 保持这篇文章的完整性。

     接着就是这个 堆结构的 实现部分:

     一下代码放在 Heap.cpp 文件中:

1. 
   
2.     //这里的代码风格借鉴了 Nisy老师上次共享的 DebuggerVC代码中的风格,好的代码风格就应该模仿。
   
3. 
   
4.      #include"Heap.h"
   
5. 
   
6.      ///////////////////////////////////////////////////////////
   
7.      //     函数名：MinHeap()
   
8.      //     描述：构造函数,生成一个空堆
   
9.      //     参数：None
   
10.      //     前提：None
    
11.      //     用法：MinHeap  对象名
    
12.      ///////////////////////////////////////////////////////////
    
13.      MinHeap :: MinHeap(){
    
14.                count = 0;
    
15.      }
    
16.      ///////////////////////////////////////////////////////////
    
17.      //     函数名：is_empty()
    
18.      //     描述：判断堆是否为空
    
19.      //     参数：None
    
20.      //     前提：None
    
21.      //     用法：对象名.is_empty()
    
22.      ///////////////////////////////////////////////////////////
    
23.      bool  MinHeap :: is_empty(){
    
24.                  return (count == 0);
    
25.      }
    
26.      ///////////////////////////////////////////////////////////
    
27.      //     函数名：size()
    
28.      //     描述：返回堆的大小
    
29.      //     参数：None
    
30.      //     前提：None
    
31.      //     用法：对象名.size()
    
32.      ///////////////////////////////////////////////////////////
    
33.     int  MinHeap :: size(){
    
34.                    return count;
    
35.     }
    
36.      ///////////////////////////////////////////////////////////
    
37.      //     函数名：Insert()
    
38.      //     描述：往堆中插入一个元素，并重新调整堆结构
    
39.      //     参数：Data 表示插入元素的键值
    
40.      //     前提：None
    
41.      //     用法：对象名.Insert( xx )
    
42.      ///////////////////////////////////////////////////////////
    
43.      void MinHeap :: Insert( int data)
    
44.      {
    
45.                     val [++ count ] = data;       //先将元素放入堆尾
    
46.                     int  p = count ;                    //调整用指针
    
47.                     while(p > 1) {                      //在到达根节点之前
    
48.                               if( val[ p>>1 ] > val [p] ){     //如果p的父节点键值＞p,进行交换
    
49.                                          int tmp = val [p] ;
    
50.                                          val [p] = val [ p>>1 ] ;
    
51.                                          val[p>>1] = tmp;
    
52.                                          p >> = 1;                //指针向上移
    
53.                              }
    
54.                              else break;                          //如果没有破坏堆结构直接跳出。
    
55.                     }
    
56.       }
    
57.      ///////////////////////////////////////////////////////////
    
58.      //     函数名：down(int position)
    
59.      //     描述：将当前破坏了的堆 通过下降调整为堆
    
60.      //     参数：position 表示需要调整的位置
    
61.      //     前提：None
    
62.      //     用法：None
    
63.      ///////////////////////////////////////////////////////////   
    
64.      void MinHeap :: down(int position)
    
65.      {
    
66.                while( (position << 1) <= size )   //如果位置还没下降到叶子节点
    
67.                {
    
68.                           int tmp = position << 1;
    
69.                            if( ( position << 1 ) + 1 <= size && val[ (position<<1)+1] < val[tmp] )
    
70.                                     //如果当前节点的右孩子小于当前节点的左孩子
    
71.                                            tmp = ( possition<<1 )+ 1;
    
72.                            if( val [tmp] < val[position] ) {
    
73.                                     //如果当前节点的右孩子 小于当前节点
    
74.                                     int temp = val [tmp] ;
    
75.                                     val [tmp ] = val[position];
    
76.                                     val [position ] = temp;
    
77.                                     position = tmp;
    
78.                          }
    
79.                          else break;
    
80.                }
    
81.      }
    
82.      ///////////////////////////////////////////////////////////
    
83.      //     函数名：Top_Remove()
    
84.      //     描述：返回堆顶元素，并删除之，再重新调整堆结构
    
85.      //     参数：None
    
86.      //     前提：None
    
87.      //     用法：对象名.Top_Remove()
    
88.      ///////////////////////////////////////////////////////////
    
89.      int MinHeap :: Top_Remove(){
    
90.                    int temp = val[1] ; //保存堆顶元素
    
91.                    val [1] = val [ count];
    
92.                    val [count ] = temp;
    
93.                    count --;
    
94.                    down(1);  调整整个堆
    
95.                    return val[count + 1];
    
96.     }
    
97.    

复制代码

这样, 堆的结构都声明完了, 接着就是排序了.

    其实按照先前那个算法, 我们可以很容易的写出排序的方法:

1. 
   
2. 
   
3. #include<cstdio>
   
4. #include"Heap.h"
   
5. 
   
6. int main()
   
7. {
   
8.       MinHeap heap;  // 声明heap作为MinHeap类
   
9.       int n;
   
10.       int data[1000];  //1000在这里作为示范的大小
    
11.       printf(" Input the number of the Arrays ! \n");
    
12.       scanf("%d",&n);
    
13.       printf(" One by one Input the Arrays! \n");
    
14.       for( int i = 0 ; i < n ;++ i )
    
15.       {
    
16.             scanf("%d", data + i );
    
17.             heap.Insert( data[i] );
    
18.       }
    
19. 
    
20.       // 以下是堆排序的过程
    
21.       for( int k = 0; k < n ; ++k )
    
22.       {
    
23.             data[k] = Top_Remove();
    
24.            //将堆顶元素放在数组中, 并删除堆顶元素重新调整堆结构
    
25.       }
    
26.       
    
27.       //此时 data 数组已经有序!
    
28.   
    
29.       // 将排序后的 data 数组输出
    
30.       for(int j = 0 ; j < n ; ++ j , printf("%d ",data[j]));
    
31. 
    
32.       printf("\n");
    
33.       return 0;
    
34. }
    
35.    

复制代码

嗯，写到这里，家人催我吃晚饭了, 所以不能再写太多了, 把查找放在 （下篇）中吧, 接着就接个尾了.

    算法分析: (这一章个人觉得有点重要，当然如果不感兴趣就不用仔细看了)

    时间复杂度分析:

    令 T(N) 为排序 N 个数组所需要的时间.
    则:
    T(N) = N + N * log2(N) ~ O( N log2(N) )

    其速度和快排在同一个阶上的, 但是由于堆结构比较复杂, 所以在操作上会有比较大的常数 , 实际上比 快速排序要慢一点.
   
    但是由于 二叉堆 的平衡性 , 所以可以保证它最慢的情况 不会超过 O( Nlog2(N) ) , 比快排要快!

    ///////////////////////////////////////////////////////////
    //   堆排序就讲到这里了， 谢谢大家.
    //////////////////////////////////////////////////////////

jmgsdz

好好学习天天向上