堆排序

2013-07-23 22:37:12

注意几点：

堆的性质虽然借助树的概念来定义的，但实际实现用数组即可，数组的下标可表征父节点与左右子树的关系；
数组下标从1开始时，下标为i的结点的左子树的下标为 2i，右子树下标为2i + 1;数组下标从0开始时，下标为i的结点的左子树的下标为 2i + 1，右子树下标为2i + 2;
注意循环结束条件；
下面的代码中输入数组是利用随机数产生函数rand()得到的，用srand()函数，可给rand()提供seed，这样每次运行时就会得到不同的随机数序列；但要注意其使用方法

代码：

  1 #include <iostream>
  2 #include <cassert>
  3 #include <time.h>
  4 using namespace std;
  5 
  6 typedef int DataType;
  7 const int MaxSize = 100000000;
  8 
  9 //显示数组元素，lengthOfArray为数组中元素个数
 10 void DisplayArray(const DataType arrayToDiaplay[],const size_t lengthOfArray)
 11 {
 12     assert(NULL != arrayToDiaplay);
 13 
 14     for (size_t index = 0;index < lengthOfArray;++index)
 15     {
 16         cout<<arrayToDiaplay[index]<<"	";
 17     }
 18 
 19     cout<<endl;
 20 }
 21 
 22  //判断在最大下标为lengthOfHeapArray（为数组中元素个数-1）的数组中，下标为positionToAdjust的元素是否有左子树
 23  bool IsHasLeftChild(const size_t lengthOfHeapArray,const size_t positionToAdjust)
 24  {
 25      size_t indexOfLeftChild = 2 * positionToAdjust + 1;
 26 
 27      return (indexOfLeftChild > lengthOfHeapArray) ? false : true;
 28  }
 29 
 30  //判断在最大下标为lengthOfHeapArray（为数组中元素个数-1）的数组中，下标为positionToAdjust的元素是否有右子树
 31  bool IsHasRightChild(const size_t lengthOfHeapArray,const size_t positionToAdjust)
 32  {
 33      size_t indexOfRightChild = 2 * positionToAdjust + 2;
 34 
 35      return (indexOfRightChild > lengthOfHeapArray) ? false : true;
 36  }
 37 
 38   //数组下标以1开始时，下标为i的结点的左子树下标为2i,左子树下标为2i+1
 39  //数组下标以0开始时，下标为i的结点的左子树下标为2i+1,左子树下标为2i+2
 40  //调用函数要保证positionToAdjust是小于
 41  void HeapAdjust(DataType heapArray[],const size_t lengthOfHeapArray,const size_t positionToAdjust)
 42  {
 43     DataType leftChildIndex = 2 * positionToAdjust + 1;
 44     DataType rightChildIndex = 2 * positionToAdjust + 2;
 45 
 46     size_t positionOfMax = positionToAdjust;   //只用positionOfMax记录最大数的下标即可
 47 
 48     if ( !IsHasLeftChild(lengthOfHeapArray,positionToAdjust)     //若为叶节点，直接返回
 49         && !IsHasRightChild(lengthOfHeapArray,positionToAdjust) )
 50     {
 51         return;
 52     }
 53          
 54     if ( IsHasLeftChild(lengthOfHeapArray,positionToAdjust)   
 55         && heapArray[leftChildIndex] > heapArray[positionOfMax])
 56     {
 57         //max = heapArray[leftChildIndex];
 58         positionOfMax = leftChildIndex;
 59     }
 60 
 61     if ( IsHasRightChild(lengthOfHeapArray,positionToAdjust) 
 62         && heapArray[rightChildIndex] > heapArray[positionOfMax])
 63     {
 64         //max = heapArray[rightChildIndex];
 65         positionOfMax = rightChildIndex;
 66     }
 67 
 68     if ( positionOfMax == positionToAdjust )    //结点大于左子树与右子树，不需调整
 69     {
 70         return;
 71     }
 72     else
 73     {
 74         //swap(heapArray[positionToAdjust],max);
 75         swap(heapArray[positionToAdjust],heapArray[positionOfMax]);
 76         HeapAdjust(heapArray,lengthOfHeapArray,positionOfMax);
 77     }
 78  }
 79 
 80  //堆排序,lengthOfHeapArray为数组的最大下标为（为数组中元素个数-1）
 81  void HeapSort(DataType heapArray[],const size_t lengthOfHeapArray)
 82  {
 83     assert(NULL != heapArray);
 84     //size_t index;  //使用size_t类型，下面的for循环不能结束0 - 1 = 2^32 - 1
 85     int index;
 86     
 87     for (index = (lengthOfHeapArray - 1)/2;index >= 0;--index)
 88     {
 89         HeapAdjust(heapArray,lengthOfHeapArray,index);
 90     }
 91 
 92     for (index = lengthOfHeapArray;index > 0;--index)
 93     {
 94         swap(heapArray[0],heapArray[index]);
 95         HeapAdjust(heapArray,index - 1,0);  //不是HeapAdjust(heapArray,lengthOfHeapArray,0);
 96     }
 97  }
 98 
 99  //产生在[lowBound,upperBound - 1]区间的随机数
100  int RandomIntGenerate(int lowBound, int upperBound)
101  {    
102      return (lowBound + (RAND_MAX * rand() + rand()) % (upperBound - lowBound + 1) );
103  }
104 
105  //测试“脚手架”
106 void TestDriver()
107 {    
108     DataType *unsortedArray = new int[MaxSize];
109     size_t lengthOfUnsortedArray = 0;
110     int MinRandomInt;
111     int MaxRandomInt;
112     size_t i;
113     int timeStart = 0;
114     double timeCostAverage = 0;
115 
116     DataType *heapArray = unsortedArray;
117     //size_t lengthOfHeapArray = lengthOfUnsortedArray;  //若lengthOfUnsortedArray未初始化，不能将其赋给其他变量，否则报错
118     size_t *lengthOfHeapArray = &lengthOfUnsortedArray;
119 
120     cout<<"please enter the length Of UnsortedArray,MinRandomInt and MaxRandomInt :"<<endl;
121     cin>>lengthOfUnsortedArray>>MinRandomInt>>MaxRandomInt;
122     
123     srand((unsigned) time(NULL));   //随机数产生的seed
124     for (i = 0;i < lengthOfUnsortedArray;++i)  //准备待排序数组
125     {
126         //srand((unsigned) time(NULL));   //随机数产生的seed,不能放在循环体内，否则unsortedArray将会是全部相同的数
127         unsortedArray[i] = RandomIntGenerate(MinRandomInt,MaxRandomInt);
128     }
129 
130     /*cout<<"the unsorted array is :"<<endl;
131     DisplayArray(unsortedArray,lengthOfUnsortedArray);*/
132     timeStart = clock();
133 
134     HeapSort(heapArray,*lengthOfHeapArray - 1);
135     
136     timeCostAverage = 1e9 * ( clock() - timeStart ) / ( CLOCKS_PER_SEC * lengthOfUnsortedArray );
137     cout<<"the average time cost per data is : "<<timeCostAverage<<" ns"<<endl;
138 
139     for (i = 0;i < lengthOfUnsortedArray - 1;++i)  //检查排序是否正确
140     {
141         if (unsortedArray[i] > unsortedArray[i + 1])
142         {
143             cout<<"sort bug i = "<<i<<endl;
144         }
145     }
146 
147     //cout<<"the sorted array is :"<<endl;
148     //DisplayArray(unsortedArray,lengthOfUnsortedArray);
149 
150     //cout<<endl;
151         
152     delete [] unsortedArray;
153 }
154 
155 //使用脚手架的测试程序
156 int main(void)
157 {
158     TestDriver();
159     return 0;
160 }

输入10个元素时，运行结果为：

please enter the length Of UnsortedArray,MinRandomInt and MaxRandomInt :
10 0 100
the unsorted array is :
20      34      24      36      5       43      6       92      75      82

the average time cost per data is : 0 ns
the sorted array is :
5       6       20      24      34      36      43      75      82      92

请按任意键继续. . .

可通过增加输入个数，测试时间性能，此处不再给出，后面在与其他算法进行比较。