学步园

题目：编写“简单选择排序”和“堆排序”算法，对它们在排序过程中的关键字比较次数和关键字移动次数进行比较。

测试数据：

（1）随机产生100个测试数据；

（2）写出测试结果。 

插入元素，向上调整堆：

删除元素后，向下调整堆：

4．调试分析

本程序一共实现了5种排序方法，可以选择执行。

各种排序算法中关键字的比较次数和交换次数是和要排序的数据的个数有关系的，如果在每一次的交换和比较之后计数统计（当然我试过了），虽然有准确的数字，但是不足以进行总体的分析。进行大量的数据排序的时候，我们考虑的是整体的性能，而非准确的比较了多少次，交换了多少次，所以我进行了画出了排序算法的流程图，这对于分析关键字的比较次数和交换次数，更加直观，也能从整体上分析。

本程序中的数据，在经过一次排序后，已经是有序的了，这时候如果接着进行下一个排序，很可能导致算法的性能不能很好地发挥出来。所以，建议执行一次排序后，重新启动程序，这样会再次生成随机的数据，进行排序。

5．使用说明

运行程序，按照提示即可。

6．测试结果

1、随机生成10000个数据时，各个算法的执行时间为：

直接插入排序，耗时141

堆排序，耗时0

冒泡排序，耗时500

直接选择排序，耗时219

快速排序，耗时0

2、随机生成100000个数据时，各个算法的执行时间为：

直接插入排序，耗时15109

堆排序，耗时47

冒泡排序，耗时50000

直接选择排序，耗时23297

快速排序，耗时16

        可以看出，快速排序果然快，堆排序也不逊色，冒泡、直接插入、直接选择随着数据数量的增加，他们的耗时也是快速增长的。

7．附录

源程序文件清单。

main.cpp#include "stdafx.h"#include <iostream>#include <stdlib.h>#include <time.h>#include <math.h>#include "MinHeap.h"using namespace std;#define DataType int#define N 100000DataType A[N];//输出数组元素void Print(){for (int i=0;i<N;i++){cout<<"A["<<i<<"]="<<A[i]<<" ";}}//直接插入排序void InsertSort(DataType array[],int n){cout<<"直接插入排序"<<endl;int i,j;DataType temp;for ( i=0;i<n-1;i++){temp=array[i+1];j=i;while(j>=0 &&temp<array[j]){array[j+1]=array[j];j--;}array[j+1]=temp;}}//直接选择排序，也叫简单选择排序void SelectSort(DataType array[],int n){cout<<"直接选择排序"<<endl;int i,j,small;DataType temp;for (i=0;i<n;i++){small=i;for (j=i+1;j<n;j++){if (array[small]>array[j]){small=j;}}if (small!=i){temp=array[i];array[i]=array[small];array[small]=temp;}}}//堆排序,小顶堆void HeapSort(DataType array[],int n){cout<<"堆排序"<<endl;MinHeap H(array,n);//制成堆int i,j; DataType temp;for(i=n-1;i>0;i--){temp=H.Delete();array[i]=temp;}//反转，换成从小到大的顺序for (j=0;j<n/2;j++){temp=array[j];array[j]=array[n-1-j];array[n-1-j]=temp;}}//冒泡排序void BubbleSoort(DataType array[],int n){cout<<"冒泡排序"<<endl;int i,j,flag=1;DataType temp;for (i=1;i<n && flag==1;i++){flag=0;for (j=0;j<n-i;j++){if (array[j]>array[j+1]){flag=1;temp=array[j];array[j]=array[j+1];array[j+1]=temp;}}}}//快速排序void QuickSort(DataType array[],int low,int high){int i=low;int j=high;DataType temp=array[low];while(i<j){//从右往左while (i<j && temp<array[j]){j--;}if (i<j){array[i]=array[j];i++;}//从左往右while (i<j && array[i]<temp){i++;}if (i<j){array[j]=array[i];j--;}}array[i]=temp;if (low<i){QuickSort(array,low,i-1);}if (i<high){QuickSort(array,j+1,high);}}int _tmain(int argc, _TCHAR* argv[]){// cout<<N<<"个数据进行测试，依次为："<<endl;//生成数据srand( (int)time( NULL ) );for (int i=0;i<N;i++){A[i]=rand();// cout<<"A["<<i<<"]="<<A[i]<<" ";}/*printf("/n/n%d 插入排序/n",1);printf("%d 堆排序/n",2);printf("%d 冒泡排序/n",3);printf("%d 选择排序/n",4);printf("%d 快速排序/n",5);printf("/n非法输入，程序将退出/n");printf("/n/n请选择操作/n");int n;while(1){cin>>n;switch (n){case 1:InsertSort(A,N);cout<<"结果为：";Print();cout<<endl;break;case 2:HeapSort(A,N);cout<<"结果为：";Print();cout<<endl;break;case 3:BubbleSoort(A,N);cout<<"结果为：";Print();cout<<endl;break;case 4:SelectSort(A,N);cout<<"结果为：";Print();cout<<endl;break;case 5:QuickSort(A,0,N-1);cout<<"结果为：";Print();cout<<endl;break;default:exit(1);}}*/clock_t start,finish;start=clock();// InsertSort(A,N);// HeapSort(A,N);// BubbleSoort(A,N);// SelectSort(A,N);QuickSort(A,0,N-1);finish=clock();cout<<"耗时"<<double(finish-start)<<endl<<endl;system("pause");return 0;}MinHeap.h//小顶堆头文件#pragma once#include <iostream>#include <stdlib.h>#include <stdio.h>using namespace std;#define DataType intclass MinHeap{private:DataType *heapArray;//存放数据元素的数组int markArray;//标记int MaxHeapSize;//最大元素个数int heaapSize;//当前元素个数void FilterUp(int i);//插入元素后，调整的过程void FilterDown(int i);//删除元素后，调整的过程public:int count_compare;//比较次数int count_move;//移动次数public:MinHeap(int maxSize);MinHeap(DataType arr[],int n);//拷贝构造函数，把n个元素调整make为堆void Insert(DataType &item);//插入元素DataType Delete();//删除堆顶，即最小元素DataType GetHeapTop()//返回堆顶元素{return heapArray[0];}int HeapSize()//返回当前堆中元素的个数{return heaapSize;}int HeapEmpty()//堆是否为空{return heaapSize==0;}int HeapFull()//堆是否已满{return heaapSize==MaxHeapSize;}void Print();//输出当前堆中的元素~MinHeap(void)//没有标记的时候，删除堆{if (markArray==0){delete heapArray;}// cout<<endl<<"堆排序。"<<"比较次数"<<count_compare<<" , 移动次数"<<count_move<<endl;}};MinHeap.cpp//小顶堆源文件#include "StdAfx.h"#include "MinHeap.h"//制成堆，调整为堆MinHeap::MinHeap(int maxSize){if (maxSize<=0){// cout<<"参数非法";exit(1);}MaxHeapSize=maxSize;heaapSize=0;heapArray=new DataType[maxSize];markArray=0;count_compare=0;count_move=0;}//把数组制成堆，调整为堆MinHeap::MinHeap(int arr[], int n){if (n<=0){// cout<<"参数非法";exit(1);}this->count_compare=0;this->count_move=0;MaxHeapSize=n;heaapSize=n;heapArray=arr;int currentPos=(n-1)/2;while(currentPos>=0){FilterDown(currentPos);currentPos--;count_compare++;//比较了}count_compare++;//比较了markArray=1;}//插入元素后，调整堆void MinHeap::FilterUp(int i){int currentPos,parentPos;DataType target;currentPos=i;target=heapArray[i];parentPos=(i-1)/2;while(currentPos!=0){if (heapArray[parentPos]<=target){break;}else{heapArray[currentPos]=heapArray[parentPos];currentPos=parentPos;parentPos=(currentPos-1)/2;}}heapArray[currentPos]=target;//插入新元素}//插入新元素void MinHeap::Insert(DataType &item){if (heaapSize==MaxHeapSize){// cout<<"堆已满";exit(1);}heapArray[heaapSize]=item;FilterUp(heaapSize);heaapSize++;}//删除堆顶元素,调整void MinHeap::FilterDown(int i){int currenrPos,childPos;DataType target;currenrPos=i;target=heapArray[i];childPos=2*i+1;while(childPos<heaapSize){count_compare++;//比较了if ((childPos+1<heaapSize) && (heapArray[childPos+1]<=heapArray[childPos])){childPos=childPos+1;count_compare+=2;//比较了}if (target<=heapArray[childPos]){count_compare++;//比较了break;}else{heapArray[currenrPos]=heapArray[childPos];currenrPos=childPos;childPos=2*currenrPos+1;count_move++;//交换了}count_compare++;//比较了}count_compare++;//比较了heapArray[currenrPos]=target;}//删除堆顶，即最小元素DataType MinHeap::Delete(){if (heaapSize==0){// cout<<"已空";exit(1);}DataType item=heapArray[0];heapArray[0]=heapArray[heaapSize-1];heaapSize--;count_move++;//交换了FilterDown(0);return item;}//输出元素void MinHeap::Print(){for (int i=0;i<this->heaapSize;i++){printf("%d ",this->heapArray[i]);}}