数据结构试验报告 - 各种内排序算法的实现及性能比较(2)

while(child<=j){ if((child

A[(child-1)/2]=temp; }

//堆排序的C++程序 template

void HeapSort(T A[], int n) {

for(int i=(n-2)/2; i>-1; i--) AdjustDown(A,i,n-1); for(i=n-1; i>0; i--){ Swap(A[0],A[i]); AdjustDown(A,0,i-1); } }

Meau.h

#include #include #include #include

#include \#include \#include \#include \#include \#include \

#define SIZE 400 #define TIMES 1000 template class Menu {

public:

void printmenu();

void selectsort();//简单选择排序 void insertSort();//直接插入排序 void bubbleSort();//冒泡排序 void quickSort();//快速排序

void mergeSort();//两路合并排序

//构造最大堆 void heapSort();//堆排序 void childmenu();//子菜单1 void childmenu2();//子菜单2 void switcha(); private:

int a,b,c; };

template

void Menu::printmenu() { cout<<\ cout<<\ 内排序测试系统 \

cout<<\ cout<<\简单选择排序\ cout<<\直接插入排序\ cout<<\冒泡排序\ cout<<\快速排序\ cout<<\两路合并排序\ cout<<\堆排序\ cout<<\退出\ cout<<\：测试用的数组元素为\时间为重复运行\次的时间（包括了产生数据与析构的时间）\ this->switcha(); }

template

void Menu::childmenu() {

cout<<\ cout<<\最好情况\ cout<<\最坏情况\ cout<<\平均情况\ cout<<\返回主菜单\ cin>>b;

if(b==4)this->printmenu(); }

template

void Menu::childmenu2() {

cout<<\ cout<<\原始算法\ cout<<\改进算法\ cout<<\返回主菜单\

cin>>c;

if(c==3)this->printmenu(); }

template

void Menu::switcha() {

//cout<<\ cin>>a; switch(a) {

case 1:this->selectsort();break;//ok case 2:this->insertSort();break;//ok case 3:this->bubbleSort();break;//ok case 4:this->quickSort();break;//ok case 5:this->mergeSort();break;//ok case 6:this->heapSort();break;//ok case 7:exit(1);break;

default:cout<<\ } };

template

void printout(T A[],int n)//打印数组，测试时用 {

for(int i=0;itemplate

T *producedate(int x)//产生顺序，逆序，随机的数组 {

int i;

T *A=new T[SIZE]; switch(x) {

case 1: for(i=0;i

case 2:for(i=SIZE;i>0;i--)A[i-1]=SIZE-i;return A;//逆序 break;

case 3:srand(time(NULL)); for(i=0;i

} }

template

void Swap(T &a,T &b)//交换2个元素 {

T temp=a; a=b; b=temp; }

template

void Menu::bubbleSort() {

cout<<\冒泡排序\ this->childmenu(); T *A;

double duration; clock_t start,finish; start=clock();

cout<<\

for(int i=0;i(b); BubbleSort(A,SIZE); delete []A; }

finish=clock();

duration=(double)(finish-start)/CLOCKS_PER_SEC; //printout(A,SIZE);

cout<<\用时： \ system(\ //delete []A;

this->bubbleSort(); }/*ok*/

template

void Menu::heapSort() {

cout<<\堆排序\

cout<<\直接用随机数据测试\ T *A;

double duration; clock_t start,finish; start=clock();

cout<<\

for(int i=0;i(3); HeapSort(A,SIZE); delete []A; }

finish=clock();

duration=(double)(finish-start)/CLOCKS_PER_SEC;

cout<<\用时： \ system(\

this->printmenu(); }

template

void Menu::insertSort() {

cout<<\直接插入排序\ this->childmenu(); T *A;

double duration;

//A=producedate(b);

//if(A==NULL){cout<<\ //printout(A,SIZE); clock_t start,finish; start=clock();

cout<<\

for(int i=0;i(b); InsertSort(A,SIZE); delete []A; }

finish=clock();

duration=(double)(finish-start)/CLOCKS_PER_SEC; //printout(A,SIZE);

cout<<\用时： \ system(\ //delete []A;

this->insertSort(); }

template

void Menu::mergeSort() {