数据结构排序实验源程序

#include

const int MaxSize=100;

class Sort

{

public:

Sort(int r[],int m[],int n); //构造函数，建立排序数组，采用顺序存储结构实现

void InsertSort(int r[], int n); //直接顺序排序

void ShellSort(int r[], int n); //希尔排序

void BubbleSort(int r[], int n); //起泡排序

int Partition(int r[], int first, int end); //快速排序一次划分

void QuickSort(int r[], int first, int end); //快速排序

void SelectSort(int r[ ], int n); //简单选择排序

void Sift(int r[], int k, int m); //筛选法调整堆

void HeapSort(int r[ ], int n); //堆排序

void Merge(int r[], int r1[], int s, int m, int t);//一次归并

void MergePass(int r[ ], int r1[ ], int n, int h); //一趟归并

void MergeSort1(int r[ ], int r1[ ], int n ); //归并排序的非递归算法

void MergeSort2(int r[], int r1[], int r2[],int s, int t);//归并排序的递归算法

void print(int n,int r[]);

void Devot(int r[],int n); //正负元素分离

void InsertHeap(int r[],int n,int x); //调整下根堆得算法

void Initialization(int r[],int m[],int n);

// int a[MaxSize];

private:

};

Sort::Sort(int r[],int m[],int n) //函数的传值调用显得尤为重要，这是函数的入口,注意形参中的参数必须和程序中的参数是一致的，不然的话就会出现未定义

{

cout<<"实际输入的元素个数为"<r[0]=0;

for(int i=1;i{

cout<<"请输入你要是排序的第"<cin>>r[i];

m[i]=r[i];

}

cout<<"您输入的元素如下：";

for(i=1;icout<cout<}

void Sort::print(int n,int r[])

{

for(int i=1;icout<}

/*直接插入排序算法思想：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序*/

void Sort::InsertSort(int r[],int n)

{

int count1,count2;

count1=count2=0;

for(int i=2;i<=n;i++)

{

r[0]=r[i]; //设置哨兵

for(int j=i-1;++count1&&r[0]{

r[j+1]=r[j];

count2++;

}

r[j+1]=r[0];

}

cout<<"比较的次数是："<cout<<"移动的次数是："<}

/*起泡排序算法思想：；两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止*/

void Sort::BubbleSort(int r[],int n)

{

int count1,count2;

count1=count2=0;

int exchange;

exchange=n;

int bound;

while(exchange)

{

bound=exchange;

exchange=0;

for(int j=1;jd;j++)

if(++count1&&r[j]>r[j+1])

{

int m;

m=r[j];

r[j]=r[j+1];

r[j+1]=m;

count2+=3;

exchange=j;

}

}

cout<<"比较的次数是："<cout<<"移动的次数是："<}

/*正负元素分离算法：设计思想：先设置好上下界和轴值，然后分别从线性表两端查找正数和负数，找到后交换，直到上下界相遇*/

void Sort::Devot(int r[],int n)

{

int i,j;

i=1;j=n;

while(i{

while(r[j]>0&&iwhile(r[i]<0&&iif(i{

int m;

m=r[i];

r[i]=r[j];

r[j]=m;

i++;

j--;

}

}

}

/*调整根堆得算法，设计思想：增加一个元素应从叶子向根方向调整，假设调整为小跟堆。还要弄清楚地是二叉树的层序遍历叶子节点与根节点数组下标的关系*/

void Sort::InsertHeap(int r[],int n,int x)

{

int i;

r[n+1]=x;

i=n+1;

while(i/2>0&&r[i/2]>x) //根节点元素大于叶子节点元素的值

{

r[i]=r[i/2];

i=i/2;

}

r[i]=x; //注意此处不要理解了是跟节点与叶子节点交换出错，而是从下到上逐步推进，直到跟为止，此时i的值已经就是x的数组下标了

}

void Sort::Initialization(int r[],int m[],int n) //将每次比较后的数组初始化为比较前的状态

{

for(int i=1;ir[i]=m[i];

}

/*希尔排序算法:基本思想：先将整个待排序记录序列分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列基本有序时，再

对全体记录进行一次直接插入排序*/

void Sort::ShellSort(int r[],int n)

{

int d,i,j;

for(d=n/2;d>=1;d=d/2)

{

for(i=d+1;i<=n;i++)

{

r[0]=r[i];

for(j=i-d;j>0&&r[0]r[j+d]=r[j];

r[j+d]=r[0];

}

}

}

void Sort::SelectSort(int r[],int n) //简单排序算法

{

int i,j,index;

for(i=1;i{

index=i;

for(j=i+1;j<=n;j++)

if(r[j]if(index!=i)

{

int m;

m=r[i];

r[i]=r[index];

r[index]=m;

}

}

}

void Sort::QuickSort(int r[],int first,int end) //快速排序算法

{

int pivot;

if(first{

pivot=Partition(r,first,end);

QuickSort(r,first,pivot-1);

QuickSort(r,pivot+1,end);

}

}

int Sort::Partition(int r[],int first,int end) //first 代表数组的首地址，end代表数组的末地址就是n

{

int i,j;

i=first;j=end;

while(i{

while(iif(i{

int m;

m=r[i];

r[i]=r[j];

r[j]=m;

i++;

}

while(iif(i{

int m;

m=r[j];

r[j]=r[i];

r[i]=m;

j--;

}

}

return i;

}

void Sort::MergeSor

t1(int r[],int r1[],int n) //归并非递归算法

{

int h;

h=1;

while(h{

MergePass(r,r1,n,h);

h=2*h;

MergePass(r1,r,n,h);

h=2*h;

}

}

void Sort::MergePass(int r[],int r1[],int n,int h) //一趟归并排序算法

{

int i;

i=1;

while(i<=n-2*h+1)

{

Merge(r,r1,i,i+h-1,i+2*h-1);

i+=2*h;

}

if(iMerge(r,r1,i,i+h-1,n);

else for(int k=i;k<=n;k++)

r1[k]=r[k];

}

void Sort::Merge(int r[], int r1[], int s, int m, int t) //r1是辅助存储数组

{

int i=s;

int j=m+1;

int k=s;

while (i<=m && j<=t)

{

if (r[i]<=r[j])

r1[k++]=r[i++]; //取r[i]和r[j]中较小者放入r1[k]

else

r1[k++]=r[j++];

}

if (i<=m)

while (i<=m) //若第一个子序列没处理完，则进行收尾处理

r1[k++]=r[i++];

else

while (j<=t) //若第二个子序列没处理完，则进行收尾处理

r1[k++]=r[j++];

}

//筛选法调整堆

void Sort::Sift(int r[], int k, int m) //k为根节点，即是首数组下标

{

int i;

int j;

int temp;

i=k;

j=2*i+1; //置i为要筛的结点，j为i的左孩子

while (j<=m) //筛选还没有进行到叶子

{

if (jj++; //比较i的左右孩子，j为较大者

if (r[i]>r[j]) break; //根结点已经大于左右孩子中的较大者

else

{

temp=r[i];

r[i]=r[j];

r[j]=temp; //将根结点与结点j交换

i=j;

j=2*i+1; //被筛结点位于原来结点j的位置

}

}

}

void Sort::HeapSort(int r[ ], int n) //归并算法

{

int i;

int temp;

for (i=n/2; i>=0; i--) //初始建堆，从最后一个非终端结点至根结点

Sift(r, i, n) ;

for (i=n-1; i>0; i--) //重复执行移走堆顶及重建堆的操作

{

temp=r[i];

r[i]=r[0];

r[0]=temp;

Sift(r, 0, i-1);

}

for(i=0;icout<cout<<"\

";

}

void main()

{

int b[MaxSize]; //辅助初始数组

int a[MaxSize]; //待排序数组

int c[MaxSize]; //归并排序临时数组

int n; //全局变量以便调用

cout<<"请输入你要排序的数据的个数：";

cin>>n;

Sort s(a,b,n);

/*====功能及操作界面提示===*/

int choice=0;

while(1)

{

cout<<"+-------------------------------------+"<cout<<"+---------欢迎使用数据排序系统--------+"<cout<<" 1,直接插入排序 "<cout<<" 2,希尔排序 "<cout<<" 3,归并排序 "<cout<<" 4,起泡排序 "<cout<<" 5,快速排序 "<cout<<" 6,简单选择排

序 "<cout<<" 7,堆排序 "<cout<<" 0,退出系统 "<cout<<"+--------------------------------------"<cin>>choice;

switch(choice)

{

case 1:

cout<<"您选择的是直接插入排序算法!"<s.InsertSort(a,n);

s.print(n,a);cout<s.Initialization(a,b,n);

break;

case 2:

cout<<"您选择的是希尔排序算法!"<s.ShellSort(a,n);

s.print(n,a);cout<s.Initialization(a,b,n);

break;

case 3:

cout<<"您选择的是归并排序算法!"<s.MergeSort1(a,c,n);

s.print(n,a);cout<s.Initialization(a,b,n);

break;

case 4:

cout<<"您选择的是起泡排序算法!"<s.BubbleSort(a,n);

s.print(n,a);cout<s.Initialization(a,b,n);

break;

case 5:

cout<<"您选择的是快速排序算法!"<s.QuickSort(a,1,n);

s.print(n,a);cout<s.Initialization(a,b,n);

break;

case 6:

cout<<"您选择的是简单选择排序算法!"<s.SelectSort(a,n);

s.print(n,a);cout<s.Initialization(a,b,n);

break;

case 7:

cout<<"您选择的是堆排序算法!"<s.HeapSort(a,n);

s.print(n,a);cout<s.Initialization(a,b,n);

break;

case 0:

exit(0);

default:

break;

}

}

}