各种排序实验报告
【一】需求分析
课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。
为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。
【二】概要设计
1.堆排序
⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(NlogN)。
⑵程序实现及核心代码的注释：
for(j=2*i+1; j<=m; j=j*2+1)
{
if(j<m-1&&(su[j]<su[j+1]))
j++;
if(temp>=su[j])
break;
su[i]=su[j];
i=j;
}
su[i]=temp;
}
void dpx() //堆排序
{
int i,temp;
cout<<"排序之前的数组为："<<endl;
output();
for(i=N/2-1; i>=0; i--)
{
head(i,N);
}
for(i=N-1; i>0; i--)
{
temp=su[i];
su[i]=su[0];
su[0]=temp;
head(0,i-1);
}
cout<<"排序之后的数组为："<<endl;
output();
}
2.归并排序
⑴算法思想：先将相邻的个数为1的每两组数据进行排序合并；然后对上次归并所得到的大小为2的组进行相邻归并；如此反复，直到最后并成一组，即排好序的一组数据。
⑵程序实现及核心代码的注释：
int is2[1000];
void bin(int low,int mid,int high)
{
int i=low,j=mid+1,k=low;
while(i<=mid&&j<=high)
if(su[i]<=su[j]) // 此处为排序顺序的关键，用小于表示从小到大排序
is2[k++]=su[i++];
else
is2[k++]=su[j++];
while(i<=mid)
is2[k++]=su[i++];
while(j<=high)
is2[k++]=su[j++];
for(i=low; i<=high; i++) // 写回原数组
su[i]=is2[i];
}
void g(int a,int b)
{
if(a<b)
{
int mid=(a+b)/2;
g(a,mid);
g(mid+1,b);
bin(a,mid,b);
}
}
3.希尔排序
⑴算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。其中，子序列的构成不是简单的“逐段分割”，而是将分隔某个“增量”的记录组成一个子序列。
⑵程序实现及核心代码的注释：
while(m)
{
m/=2;
if(m!=0)
{
for(i=m; i<N; i++)
if(su[i]< su[i-m])
{
temp=su[i];
for(j=i-m; j>=0&&(temp<su[j]); j-=m)
su[j+m]=su[j];
su[j+m]=temp;
}
}
}
4.冒泡排序
⑴算法思想：1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比较到第一个数，即可得到第一个数是所有数中最小的数；2、然后再将数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，依次比较到第二个数，3、如此循环到只剩最后两个比较，即得到排好序的一组数。
⑵程序实现及核心代码的注释：
for(i=0; i<N; i++)
{
flag=true;
for(j=0; j<N-1-i; j++)
{
if(su[j]>su[j+1])
{
temp=su[j];
su[j]=su[j+1];
su[j+1]=temp;
flag=false;
}
}
if(flag==true)
break;
}
cout<<"排序之后的数组为："<<endl;
output();
}
int K;
int find(int i,int j)
{
int temp;
bool flag=true;
temp=su[i];
while(i<j)
{
if(flag)
{
while(temp<=su[j])
{
j--;
if(i>=j)
break;
}
if(i>=j)
break;
su[i]=su[j];
while(temp>=su[i])
{
i++;
if(i>=j)
break;
}
if(i>=j)
break;
su[j]=su[i];
flag=false;
}
else
{
while(temp>=su[i])
{
i++;
if(i>=j)
break;
}
su[j]=su[i];
if(i>=j)
break;
while(temp<=su[j])
{
j--;
if(i>=j)
break;
}
su[i]=su[j];
flag=true;
}
}
for(i=1; i<N; i++)
{
head=su[i];
for(j=0; j<i; j++)
{
if(head<su[j])
{
for(k=i; k>j; k--)
{
su[k]=su[k-1];
}
su[j]=head;
break;
}
}
}
for(i=1; i<N; i++)
{
head=su[i];
for(j=0; j<i; j++)
{
if(head<su[j])
{
for(k=i; k>j; k--)
{
su[k]=su[k-1];
}
su[j]=head;
break;
}
}
}
5.快速排序
（1）任取待排序记录序列中的某个记录作为基准，按照该记录的关键字大小，将整个记录 序列划分为左右两个子序列。
左侧子序列中所有记录的关键字都小于或等于基准记录的关键字。 右侧子序列中所有记录的关键字都大于基准记录的关键字。
取序列第一个记录为枢轴记录，其关键字为Pivotkey；指针low指向序列第一个记录位置（low=1），指针high指向序列最后一个记录位置（High=SeqList.Len） (2) 从high指向的记录开始，向前找到第一个关键字的值小于Pivotkey的记录，将其放到low指向的位置，low++ (3) 从low指向的记录开始，向后找到第一个关键字的值大于Pivotkey的记录，将其放到high指向的位置，high—
重复2、3，直到low==high，将枢轴记录放在low（high）指向的位置。
（2）程序实现及核心代码的注释：
int find(int i,int j)
{
int temp;
bool flag=true;
temp=su[i];
while(i<j)
{
if(flag)
{
while(temp<=su[j])
{
j--;
if(i>=j)
break;
}
if(i>=j)
break;
su[i]=su[j];
while(temp>=su[i])
{
i++;
if(i>=j)
break;
}
if(i>=j)
break;
su[j]=su[i];
flag=false;
}
else
{
while(temp>=su[i])
{
i++;
if(i>=j)
break;
}
su[j]=su[i];
if(i>=j)
break;
while(temp<=su[j])
{
j--;
if(i>=j)
break;
}
su[i]=su[j];
flag=true;
}
}
su[i]=temp;
cout<<"排完 "<<K++<<" 次顺序后的结果"<<endl;
output();
return i;
}
void qsort(int low,int high)
{
if(low<high)
{
int mid=find(low,high);
qsort(low,mid-1);
qsort(mid+1,high);
}
}
6.基数排序
（1）算法的基本思想 ：
基数排序是属于“分配式排序”，又称“桶子法”，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。
最高位优先法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。
（2）程序实现及核心代码的注释：
for(i=0; i<N; i++)
{
if(max<su[i])
max=su[i];
a[H(su[i])][b[H(su[i])]++]=su[i];
}
k=0;
for(i=0; i<10; i++)
{
if(b[i]!=0)
{
for(j=0; j<b[i]; j++)
{
su[k++]=a[i][j];
}
}
}
cout<<"第一躺排序之后的数组为："<<endl;
output();
///第二次
if(max/10==0)
return ;
for(i=0; i<10; i++)
b[i]=0;
for(i=0; i<N; i++)
{
a[HH(su[i])][b[HH(su[i])]++]=su[i];
}
k=0;
for(i=0; i<10; i++)
{
if(b[i]!=0)
{
for(j=0; j<b[i]; j++)
{
su[k++]=a[i][j];
}
}
}
cout<<"第二躺排序之后的数组为："<<endl;
output();
///第三次
if(max/100==0)
return ;
for(i=0; i<10; i++)
b[i]=0;
for(i=0; i<N; i++)
{
a[HHH(su[i])][b[HHH(su[i])]++]=su[i];
}
k=0;
for(i=0; i<10; i++)
{
if(b[i]!=0)
{
for(j=0; j<b[i]; j++)
{
su[k++]=a[i][j];
}
}
}
7.折半排序
⑴算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，这般插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，这般插入排序的时间复杂度仍为O（n2）。
⑵程序实现及核心代码的注释：
for(i=1; i<N; i++)
{
temp=su[i];
low=0;
high=i-1;
while(low<=high)
{
m=(low+high)/2;
if(temp<su[m])
high=m-1;
else
low=m+1;
}
for(j=i; j>high+1; j--)
su[j]=su[j-1];
su[high+1]=temp;
}
8.直接插入排序
⑴算法思想：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增一的有序表。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。
⑵程序实现及核心代码的注释：
for(i=1; i<N; i++)
{
head=su[i];
for(j=0; j<i; j++)
{
if(head<su[j])
{
for(k=i; k>j; k--)
{
su[k]=su[k-1];
}
su[j]=head;
break;
}
}
}
【三】详细设计
程序代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define H(X) (X%10)
#define HH(X) (X%100/10)
#define HHH(X) (X/100)
using namespace std;
//int ss[10000]= {32,37,64,87,16,12,24,32}; //将要排序的数组
int ss[10000]= {372,209,53,942,547,234,645,468,7,83}; //将要排序的数组
int su[10000]; //将要排序的数组
int N=10; //数组的长度
void input() //数组的输入函数
{
cout<<"请输入要排序的数组的长度N：";
cin>>N;
cout<<"请输入需要排序的数组："<<endl;
for(int i=0; i<N; i++)
cin>>ss[i];
}
void output() //数组的输出函数
{
for(int i=0; i<N; i++)
cout<<su[i]<<" ";
cout<<endl;
}
void head(int i,int m) //堆排序的一个函数
{
int j;
int temp;
temp=su[i];
for(j=2*i+1; j<=m; j=j*2+1)
{
if(j<m-1&&(su[j]<su[j+1]))
j++;
if(temp>=su[j])
break;
su[i]=su[j];
i=j;
}
su[i]=temp;
}
void dpx() //堆排序
{
int i,temp;
cout<<"排序之前的数组为："<<endl;
output();
for(i=N/2-1; i>=0; i--)
{
head(i,N);
}
for(i=N-1; i>0; i--)
{
temp=su[i];
su[i]=su[0];
su[0]=temp;
head(0,i-1);
}
cout<<"排序之后的数组为："<<endl;
output();
}
int is2[1000];
void bing(int low,int mid,int high)
{
int i=low,j=mid+1,k=low;
while(i<=mid&&j<=high)
if(su[i]<=su[j]) // 此处为排序顺序的关键，用小于表示从小到大排序
is2[k++]=su[i++];
else
is2[k++]=su[j++];
while(i<=mid)
is2[k++]=su[i++];
while(j<=high)
is2[k++]=su[j++];
for(i=low; i<=high; i++) // 写回原数组
su[i]=is2[i];
}
void g(int a,int b)
{
if(a<b)
{
int mid=(a+b)/2;
g(a,mid);
g(mid+1,b);
bing(a,mid,b);
}
}
void gbpx() //归并 排序
{
cout<<"排序之前的数组为："<<endl;
output();
g(0,N-1);
cout<<"排序之后的数组为："<<endl;
output();
}
void xepx() //希尔 排序
{
int i,j,temp;
int m=N;
cout<<"排序之前的数组为："<<endl;
output();
while(m)
{
m/=2;
if(m!=0)
{
for(i=m; i<N; i++)
if(su[i]< su[i-m])
{
temp=su[i];
for(j=i-m; j>=0&&(temp<su[j]); j-=m)
su[j+m]=su[j];
su[j+m]=temp;
}
}
}
cout<<"排序之后的数组为："<<endl;
output();
}
void mppx() //冒泡 排序
{
int i,j,k;
int temp,min;
bool flag;
cout<<"排序之前的数组为："<<endl;
output();
for(i=0; i<N; i++)
{
flag=true;
for(j=0; j<N-1-i; j++)
{
if(su[j]>su[j+1])
{
temp=su[j];
su[j]=su[j+1];
su[j+1]=temp;
flag=false;
}
}
if(flag==true)
break;
}
cout<<"排序之后的数组为："<<endl;
output();
}
int K;
int find(int i,int j)
{
int temp;
bool flag=true;
temp=su[i];
while(i<j)
{
if(flag)
{
while(temp<=su[j])
{
j--;
if(i>=j)
break;
}
if(i>=j)
break;
su[i]=su[j];
while(temp>=su[i])
{
i++;
if(i>=j)
break;
}
if(i>=j)
break;
su[j]=su[i];
flag=false;
}
else
{
while(temp>=su[i])
{
i++;
if(i>=j)
break;
}
su[j]=su[i];
if(i>=j)
break;
while(temp<=su[j])
{
j--;
if(i>=j)
break;
}
su[i]=su[j];
flag=true;
}
}
su[i]=temp;
cout<<"排完 "<<K++<<" 次顺序后的结果"<<endl;
output();
return i;
}
void qsort(int low,int high)
{
if(low<high)
{
int mid=find(low,high);
qsort(low,mid-1);
qsort(mid+1,high);
}
}
void kspx() //快速 排序
{
K=0;
cout<<"排序之前的数组为："<<endl;
output();
qsort(0,N-1);
cout<<"排序之后的数组为："<<endl;
output();
}
void jspx() //基数 排序
{
int i,j,k;
int max=0;
int a[10][100];
int b[10]= {0};
cout<<"排序之前的数组为："<<endl;
output();
for(i=0; i<N; i++)
{
if(max<su[i])
max=su[i];
a[H(su[i])][b[H(su[i])]++]=su[i];
}
k=0;
for(i=0; i<10; i++)
{
if(b[i]!=0)
{
for(j=0; j<b[i]; j++)
{
su[k++]=a[i][j];
}
}
}
cout<<"第一躺排序之后的数组为："<<endl;
output();
///第二次
if(max/10==0)
return ;
for(i=0; i<10; i++)
b[i]=0;
for(i=0; i<N; i++)
{
a[HH(su[i])][b[HH(su[i])]++]=su[i];
}
k=0;
for(i=0; i<10; i++)
{
if(b[i]!=0)
{
for(j=0; j<b[i]; j++)
{
su[k++]=a[i][j];
}
}
}
cout<<"第二躺排序之后的数组为："<<endl;
output();
///第三次
if(max/100==0)
return ;
for(i=0; i<10; i++)
b[i]=0;
for(i=0; i<N; i++)
{
a[HHH(su[i])][b[HHH(su[i])]++]=su[i];
}
k=0;
for(i=0; i<10; i++)
{
if(b[i]!=0)
{
for(j=0; j<b[i]; j++)
{
su[k++]=a[i][j];
}
}
}
cout<<"第三次排序之后的数组为："<<endl;
output();
}
void zbcrpx() //折半插入排序
{
int i,j,k,m;
int low,high,temp;
cout<<"排序之前的数组为："<<endl;
output();
for(i=1; i<N; i++)
{
temp=su[i];
low=0;
high=i-1;
while(low<=high)
{
m=(low+high)/2;
if(temp<su[m])
high=m-1;
else
low=m+1;
}
for(j=i; j>high+1; j--)
su[j]=su[j-1];
su[high+1]=temp;
}
cout<<"排序之后的数组为："<<endl;
output();
}
void zjcrpx() //直接插入排序
{
int i,j,k;
int temp,head;
cout<<"排序之前的数组为："<<endl;
output();
for(i=1; i<N; i++)
{
head=su[i];
for(j=0; j<i; j++)
{
if(head<su[j])
{
for(k=i; k>j; k--)
{
su[k]=su[k-1];
}
su[j]=head;
break;
}
}
}
cout<<"排序之后的数组为："<<endl;
output();
}
void jiemian()
{
cout<<"********************************************************************************"<<endl;
cout<<"********************************************************************************"<<endl;
cout<<"****************************< 1: 堆排序 >***************************"<<endl;
cout<<"****************************< 2: 归并排序 >***************************"<<endl;
cout<<"****************************< 3: 希尔排序 >***************************"<<endl;
cout<<"****************************< 4: 冒泡排序 >***************************"<<endl;
cout<<"****************************< 5: 快速排序 >***************************"<<endl;
cout<<"****************************< 6: 基数排序 >***************************"<<endl;
cout<<"****************************< 7: 折半插入排序 >***************************"<<endl;
cout<<"****************************< 8: 直接插入排序 >***************************"<<endl;
cout<<"****************************< 9: 重新输入 >***************************"<<endl;
cout<<"****************************< 0: 退出 >***************************"<<endl;
cout<<"****************************< X[ 请选择 ]X >***************************"<<endl;
}
int main()
{
system("color 1a");
int test;
jiemian();
cin>>test;
while(test!=0)
{
for(int i=0;i<N;i++)
su[i]=ss[i];
switch(test)
{
case 1:
{
dpx();
break;
}
case 2:
{
gbpx();
break;
}
case 3:
{
xepx();
break;
}
case 4:
{
mppx();
break;
}
case 5:
{
kspx();
break;
}
case 6:
{
jspx() ;
break;
}
case 7:
{
zbcrpx();
break;
}
case 8:
{
zjcrpx();
break;
}
case 9:
{
input();
break;
}
default:
cout<<"排序之前为："<<endl;
output();
g(0,7);
cout<<"排序之后为："<<endl;
output();
{
cout<<"请输入序号："<<endl;
}
}
jiemian();
cin>>test;
}
}
【四】调试结果
1.界面
2.堆排序
3.归并排序
****************************************************************************** 略*******************************************************************************
9.直接插入排序
【五】总结
-
内部排序实验报告
深圳大学实验报告课程名称学院报告人实验时间实验报告提交时间教务部制深圳大学学生实验报告用纸2教师批改学生实验报告时间应在学生提交实…
-
数据结构排序实验报告
数据结构课程设计报告实验五排序一需求分析本演示程序用C60编写完成各种排序的实现对输入的一组数字实现不同的排序方法对其由小到大顺序…
-
实验报告_排序与查找
电子科技大学信息与软件工程学院实验报告电子科技大学实验报告课程名称学生姓名学号点名序号指导教师实验地点实验时间20xx20xx2学…
-
排序算法实验报告
实验课程算法分析与设计实验名称几种排序算法的平均性能比较验证型实验实验目标1几种排序算法在平均情况下哪一个更快2加深对时间复杂度概…
-
各种排序实验报告
一需求分析课程题目是排序算法的实现课程设计一共要设计八种排序算法这八种算法共包括堆排序归并排序希尔排序冒泡排序快速排序基数排序折半…
-
北理工微机原理实验报告
实验报告班级姓名学号实验1题目两个多位十进制数相加将两个多位十进制数相加要求加数均以ASCII码形式各自顺序存放在以DATA1和D…
-
实验报告-各种排序方法及其实现
计算机学院实验报告专用纸实验室网络实验室机号网38实验日期20xx年6月25日1计算机学院实验报告附页2计算机学院实验报告附页3计…
-
《数据结构》实验报告——排序
数据结构实验报告排序实验题目输入十个数从插入排序快速排序选择排序三类算法中各选一种编程实现实验所使用的数据结构内容及编程思路1插入…
-
数据结构排序实验报告
数据结构课程设计报告实验五排序一需求分析本演示程序用C60编写完成各种排序的实现对输入的一组数字实现不同的排序方法对其由小到大顺序…
- 数据结构排序算法实验报告
-
各种学术报告的心得
本次报告是由图书馆组织的有关学习并了解使用最全面的的爱思唯尔(Elsevier)数据库，通过本次的学习，我充分的了解到知识如下：爱…