归并排序实验报告
篇一：归并排序与快速排序实验报告
一、实验内容：
对二路归并排序和快速排序对于逆序的顺序数的排序时间复杂度比较。
二、所用算法的基本思想及复杂度分析：
1、归并排序
1）基本思想：运用分治法，其分治策略为：
①划分：将待排序列 r1,r2,……,rn划分为两个长度相等的子序列
r1,……,rn/2和rn/2+1,……,rn。
②求解子问题：分别对这两个子序列进行排序，得到两个有序子序列。
③合并：将这两个有序子序列合并成一个有序子序列。
2）复杂度分析：
二路归并排序的时间代价是o(nlog2n)。二路归并排序在合并过程中需要与原始记录序列同样数量的存储空间，因此其空间复杂性o(n)。
2、快速排序：
1）基本思想：运用分治法，其分治策略为：
①划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列
r1……ri-1和ri+1……rn，轴值的位置i在划分的过程中确定，并且前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值。
②求解子问题：分别对划分后的每一个子序列递归处理。
③合并：由于对子序列r1……ri-1和ri+1……rn的排序是就地进行的，所以合并不需要执行任何操作。
2）复杂度分析：
快速排序在平均时间复杂性是o(nlog2n)。最坏的情况下是o(n^2)。
三、源程序及注释：
1、归并排序
#include<iostream>
#include<fstream>
#include windows.h
using namespace std;
void merge(int r[],int r1[],int s,int m,int t )
}
int mergesort(int r[],int r1[],int s,int t)
{
}
void main()
int i=s; int j=m+1; int k=s; while(i<=m&&j<=t) {} if(i<=m)while(i<=m) r1[k++]=r[i++];//第一个没处理完，进行收尾if(r[i]<=r[j])r1[k++]=r[i++];//取r[i]和r[j]中较小的放入r1[k]中else r1[k++]=r[j++]; else while(j<=t) r1[k++]=r[j++];//第二个没处理完，进行收尾for(int l=0;l<k;l++) { } r[l]=r1[l];//将合并完成后的r1[]序列送回r[]中if(s==t)r1[s]=r[s]; else{int m; m=(s+t)/2; mergesort(r,r1,s,m);//归并排序前半个子序列 mergesort(r,r1,m+1,t); //归并排序后半个子序列 merge(r1,r,s,m,t);//合并两个已排序的子序列 }return 0;
int a[100000]; int a1[10000];
int n,i;
int b[3]= {1000,3000,5000};//产生3个数组。
for(int j=0; j<3; j++)
{
n=b[j];
for(i=1; i<=n; i++)
a[i]=n;
large_integer begaintime ;large_integer endtime ;large_integer frequency;queryperformancefrequency(&frequency);queryperformancecounter(& ;begaintime) ;int c=mergesort(a,a1,0,n-1); queryperformancecounter(&endtime); cout << 数据个数为<<n<<时归并排序的时间为（单位：s）：<<(double)( endtime1.quadpart - begaintime1.quadpart )/ frequency1.quadpart <<endl;
}
}
2、快速排序
#include<iostream>
#include<fstream>
#include windows.h
using namespace std;
int partition (int data[],int first,int end)
{
int i,j;
} while(i<j) { } return i; while(i<j&&data[i]<=data[j])j--;//从左侧扫描 if(i<j) {} while(i<j&&data[i]<=data[j])i++;//从右侧扫描if(i<j) {} int temp1; temp1=data[i]; data[i]=data[j]; data[j]=temp1; //将较小的放到后面 j--; int temp; temp=data[i]; data[i]=data[j]; data[j]=temp;//将较小的放到前面 i++;
int quicksort(int c[],int first,int end)
{
int i; if(first<end) { i=partition(c,first,end);//对c[hs]到c[ht]进行一次划分
} } quicksort(c,i+1,end);//递归处理右区间 return 0;
void main()
{
int a[100000],n,i;
int b[3]= {1000,3000,5000};//3个数据范围
for(int j=0; j<3; j++)
{
n=b[j];
for(i=1; i<=n; i++) a[i]=n;
large_integer begaintime ;large_integer endtime;large_integer frequency ;queryperformancefrequency(&frequency);queryperformancecounter(&am p;begaintime) ;int c= quicksort(a,0,n); queryperformancecounter(&endtime);
cout << 数据个数为<<n<<时快速排序的时间为（单位：s）：<<(double)( endtime.quadpart - begaintime.quadpart )/ frequency.quadpart <<endl;
}
}
四、运行输出结果：
归并排序篇二：算法分析与设计实验报告-合并排序、快速排序
实验报告实验一合并排序、快速排序
一．实验目的
（1）学习合并排序和快速排序算法的思想，掌握原理。
（2）运用合并排序和快速排序算法的思想进行编程实现，以加深理解。
二．实验内容
（1）输入几个整数，运用合并排序的思想进行编程实现，输出正确的排序结果。
（2）输入10个整数，运用快速排序的思想进行编程实现，输出正确的排序结果
三．实验代码
(1)合并排序源代码如下：
#include <iomanip.h>//调用setw
#include <iostream.h> //将b[0]至b[right-left+1]拷贝到a[left]至a[right] template <class t>
void copy(t a[],t b[],int left,int right)
{ int size=right-left+1;
for(int i=0;i<size;i++)
{
a[left++]=b[i];
}
} //合并有序数组a[left:i],a[i+1:right]到b,得到新的有序数组b
template <class t>
void merge(t a[],t b[],int left,int i,int right)
{ int a1cout=left,//指向第一个数组开头
a1end=i,//指向第一个数组结尾
a2cout=i+1,//指向第二个数组开头
a2end=right,//指向第二个数组结尾
bcout=0;//指向b中的元素
for(int j=0;j<right-left+1;j++)//执行right-left+1次循环
{ if(a1cout>a1end)
{b[bcout++]=a[a2cout++];
continue; } //如果第一个数组结束，拷贝第二个数组的元素到b if(a2cout>a2end) {
b[bcout++]=a[a1cout++];
continue; } //如果第二个数组结束，拷贝第一个数组的元素到 b if(a[a1cout]<a[a2cout])
{ b[bcout++]=a[a1cout++];
continue; } //如果两个数组都没结束，比较元素大小，把较小的放入belse
{ b[bcout++]=a[a2cout++];
continue;} } } //对数组a[left:right]进行合并排序 template <class t>
void mergesort(t a[],int left,int right)
{ t *b=new
int[right-left+1];
if(left<right)
{
int i=(left+right)/2;//取中点
mergesort(a,left,i);//左半边进行合并排序 mergesort(a,i+1,right);//右半边进行合并排序 merge(a,b,left,i,right);//左右合并到b中
copy(a,b,left,right);//从b拷贝回来
}
}
int main()
{ int n;
cout<<请输入您将要排序的数目:; cin>>n; int *a=new int[n]; cout<<请输入相应的数字：;for(int i=0;i<n;i++)
{ cin>>a[i]; }
mergesort( a, 0, n-1); cout<<排序结果:;
for(int j=0;j<n;j++)
{ cout<<setw(5)<<a[j]; }
cout<<endl;
return 1;
}
（2）快速排序源代码如下：
#include <iostream.h>
#define max 10
int quicksort(int a[],int l,int r)
{
int pivot; //枢轴
int i=l;
int j=r;
int tmp;
pivot=a[(l+r)/2];//取数组中间的数为枢轴 do {
while (a[i]<pivot) i++; //i右移
while (a[j]>pivot) j--;// j左移
if (i<=j)
{
tmp=a[i];a[i]=a[j];
a[j]=tmp; //交换a[i]和a[j] i++;
j--;
}
} while(i<=j);
if (l<j) quicksort(a,l,j);
if (i<r) quicksort(a,i,r);
return 1;
}
int main()
{
int array[max];
int i;
cout<<请输入<<max<< 个整数:; for (i=0;i<max;i++)
cin>>array[i];
quicksort(array,0,max-1); cout<<快速排序后：<<endl; for (i=0;i<max;i++)
cout<<array[i]<< ; cout<<endl;
return 0;
}
四．实验结果五．总结与思考篇三：合并、快速排序实验报告
合并、快速排序
一．实验目的：
1. 理解算法设计的基本步骤及各部的主要内容、基本要求；
2. 加深对分治设计方法基本思想的理解，并利用其解决现实生活中的问题；
3. 通过本次试验初步掌握将算法转化为计算机上机程序的方法。二．实验内容：
1. 设计和实现递归的合并排序算法、快速排序算法；
2. 设计和实现消除递归的合并排序算法、快速排序算法；
3. 设计有代表性的典型输入数据，分析算法的效率；
4. 对于给定的输入数据，给出算运行结果和运行结果，并给出实验结果分。三．实验操作：1. 合并排序思想：
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的思想，是一种稳定的排序方法。将以有序的子序列合并，得到完全有序的序列；及先使每个字序列有序，再使子序列段间有序。
归并过程：比较数组中两个元素的大小，如比较a[i]和a[j]的大小，若a[i]<=a[j]，
将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表剩下的元素复制到r中从下标k到下标t的单元。
如： 6，202，100，301，38，8，1
第一次归并：{6，202}，{100，301}，{8，38}，{1} 第二次归并：{6，100，202，301}，{1，8，38} 第三次归并：{1，6，8，38，100，202，301} 合并排序算法：
void merge(int array[],int low,int high){
int i=low,j,k;
int mid=(low+high)/2; j=mid+1; k=low;
int* list=new int[high+1]; while(i<=mid&&j<=high){
if(array[i]<=array[j]) list[k++]=array[i++];else list[k++]=array[j++];}
while(i<=mid) list[k++]=array[i++]; while(j<=high) list[k++]=array[j++]; for(int n=low;n<=high;n++)array[n]=list[n];
}
void mergesort(int array[],int low,int high){
if(low<high){
int mid=(low+high)/2;
mergesort(array,low,mid);
mergesort(array,mid+1,high); merge(array,low,high); }
}
2. 快速排序思想：
将要排序的数据存入数组中，首先任意去一个元素（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，值得注意的是，快速排序不是一种稳定的排序算法，即多个相同的值的相对位置也许会在算法结束时产生变动。
快速排序的过程：
1）设置两个变量i,j，排序开始的时候：i=0,j=n-1（n为元素个数）； 2）以第一个数组元素作为关键数据，赋给key，即key=a[0]； 3）从j开始向前搜索，即由后开始向前搜索（j--），找到第一个小于key
的值a[j]，将a[j]和a[i]互换；
4）从i开始向后搜索，即由前开始向后搜索（i++），找到第一个大于key
的a[i]，将a[i]和a[j]互换； 5）重复第3、4步，直到i=j；
如：快速排序的算法：
void qsort(int list[],int low,int high){ if(low>=high) return; int first=low; int last=high;
int key=list[first]; while(first<last){
while(first<last&&list[last]>=key) --last; list[first]=list[last];
while(first<last&&list[first]<=key) ++first; list[last]=list[first]; }
list[first]=key;
qsort(list,low,first-1); qsort(list,last+1,high);
}
3. 实验数据的输入：
本实验采用将数据输入与输出存储到文件中的方式，需要采用c++文件流操作，对于数据的输入，由于cin对数据的读取会忽略空格和换行操作，使用cin流输入来控制数据的输入。对于输出操作，首先要从文件中读取数据，为了区别各数据，用逗号隔离，经过处理后将数据存入到另一文件之中。
由于输入需要大量的数据，可采用从“随机数.txt”中读取数据。文件输入算法：
int input(){
ofstream outfile;
outfile.open(e://程序设计/practice 1/算法设计与分析文本文件夹/number2.txt,ios::trunc);
if(!outfile.is_open()) cout<<file cant open!<<endl;cout<<input numbers:<<endl;char num;int length=0;cin.get(num);while(num!=e){ length++; outfile<<num;cin.get(num);}
outfile.close(); return length;
}
文件输出算法：
void output(int length){
double start,end; ifstream infile; ofstream outfile;
infile.open(e://程序设计/practice 1/算法设计与分析/文本文件夹/number2.txt); outfile.open(e://程序设计/practice 1/算法设计与分析/文本文件夹/result.txt,ios::trunc);
char* array=new char[length]; int* list=new int[length]; int* ray=new int[length];
memset(list,0,length*sizeof(list)); int i=0,j=0;
outfile<<排序前的序列为：; while(!infile.eof()){array[i]=infile.get();
if(array[i]!= &&array[i]!=\n){if(array[i]!=,){
list[j]=list[j]*10+(array[i]-0); ray[j]=list[j];}
else{
outfile<<list[j]<< ; j++;} } i++; }
}
4．程序运行时间的测量：
为了了解两种算法时间运行效率，要对排序进行时间测量，调用time
标准库。
double start,end,time; start=clock(); 排序算法；
end=clock();time=end-start; 四．实验数据分析：
本实验比较了快速排序和合并排序的时间效率，当输入的数据较少时，如文件中的2000个数据，快速排序输出的时间是0.0022s，而合并排序的输出时间是0.0023s，故在少量数据的情况下，两种排序的时间开销可以认为是一样的，当输入的数据较多时，归并排序的时间效率要高，在输入数据量为5000时，归并排序要快0.01s，所以并不能直接认为快速排序更快，而且快速排序有受到输入数据顺序的限制。五．实验感受;
通过本次实验，了解到对于理解的东西并不能完全正确的写出程序，对于整数和逗号等字符一出现的情况可以利用字符处理的方式解决，但对于数字的统计需要细心，它还会影响到动态数组的开取问题，以及文件的导入流和导出流需要与普通数据输入有所区分。
《数据结构》实验报告——排序.docx
《数据结构》实验报告排序实验题目： 输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路： 1. 插入排序：直接插入排序的基本操作是，将一个记录到已排好序的有序表中，从而得到一个新的，记录增一得有序表。 一般情况下，第i 趟直接插入排序的操作为：在含有i-1 个记录的有序子序列r[1..i-1 ]中插入一个记录r[i ]后，变成含有i 个记录的有序子序列r[1..i ]；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r [0]处设置哨兵。在自i-1 起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1 趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第2 个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。 2. 快速排序：基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序的序列为{L.r[s] ,L.r[s+1],…L.r[t]}, 首先任意选取一个记录 （通常可选第一个记录L.r[s]）作为枢轴（或支点）（PiVOt ）,然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置i 作为界线，将序列{L.r[s] ，… ，L.r[t]} 分割成两个子序列{L.r[i+1],L.[i+2], …,L.r[t]}。这个过程称为一趟快速排序，或一次划分。 一趟快速排序的具体做法是：附设两个指针lOw 和high ，他们的初值分别为lOw 和high ，设枢轴记录的关键字为PiVOtkey ，则首先从high 所指位置起向前搜索找到第一个关键字小于PiVOtkey 的记录和枢轴记录互相交换，然后从lOw 所指位置起向后搜索，找到第一个关键字大于PiVOtkey 的记录和枢轴记录互相 交换，重复这两不直至low=high 为止。 具体实现上述算法是，每交换一对记录需进行3 次记录移动(赋值)的操作。而实际上，
排序操作实验报告
数据结构与算法设计 实验报告 （2016 — 2017 学年第1 学期） 实验名称： 年级： 专业： 班级： 学号： 姓名： 指导教师： 成都信息工程大学通信工程学院
一、实验目的 验证各种简单的排序算法。在调试中体会排序过程。 二、实验要求 （1）从键盘读入一组无序数据，按输入顺序先创建一个线性表。 （2）用带菜单的主函数任意选择一种排序算法将该表进行递增排序，并显示出每一趟排序过程。 三、实验步骤 1、创建工程（附带截图说明） 2、根据算法编写程序（参见第六部分源代码） 3、编译 4、调试 四、实验结果图 图1-直接输入排序
图2-冒泡排序 图3-直接选择排序 五、心得体会 与哈希表的操作实验相比，本次实验遇到的问题较大。由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念，设计思路特别混乱。虽然在理清思路后成功解决了直接输入和直接选择两种算法，但冒泡
排序的算法仍未设计成功。虽然在老师和同学的帮助下完成了冒泡排序的算法，但还需要多练习这方面的习题，平时也应多思考这方面的问题。而且，在直接输入和直接选择的算法设计上也有较为复杂的地方，对照书本做了精简纠正。 本次实验让我发现自己在算法设计上存在一些思虑不周的地方，思考问题过于片面，逻辑思维能力太过单薄，还需要继续练习。 六、源代码 要求：粘贴个人代码，以便检查。 #include 《排序问题求解》实验报告 一、算法的基本思想 1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中，从而得到一个新的， 记录数增1 的有序序列。 直接插入排序算法的伪代码称为InsertionSort，它的参数是一个数组A[1..n]，包含了n 个待排序的数。用伪代码表示直接插入排序算法如下： InsertionSort (A) for i←2 to n do key←A[i] //key 表示待插入数 //Insert A[i] into the sorted sequence A[1..i-1] j←i-1 while j>0 and A[j]>key do A[j+1]←A[j] j←j-1 A[j+1]←key 2、快速排序算法思想 快速排序算法的基本思想是，通过一趟排序将待排序序列分割成独立的两部分，其中一 部分记录的关键字均比另一部分记录的关键字小，则可对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序序列为数组A[1..n]，首先选取第一个数A[0]，作为枢轴（pivot），然后按照下述原则重新排列其余数：将所有比A[0]大的数都排在它的位置之前，将所有比A[0]小的数都排在它的位置之后，由此以A[0]最后所在的位置i 作为分界线，将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序，对子数组A[1..i-1]和A[i+1..n]排序。 一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey，则首先从high 所指位置起向前搜索，找到第一个小于pivotkey 的数，并将其移到低端，然后从low 所指位置起向后搜索，找到第一个大于pivotkey 的数，并将其移到高端，重复这两步直至low=high。最后，将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下： Partition ( A, low, high) A[0]←A[low] //用数组的第一个记录做枢轴记录 privotkey←A[low] //枢轴记录关键字 while low 电子科技大学实验报告 课程名称：数据结构与算法 学生姓名： 学号： 点名序号： 指导教师： 实验地点：基础实验大楼 实验时间： 5月20日 2014-2015-2学期 信息与软件工程学院 实验报告（二） 学生姓名学号：指导教师： 实验地点：基础实验大楼实验时间：5月20日 一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—排序与查找 三、实验学时：4 四、实验原理： 快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1）设置两个变量I、J，排序开始的时候I：=1，J：=N 2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]； 3）从J开始向前搜索，即（J：=J-1），找到第一个小于X的值，两者交换； 4）从I开始向后搜索，即（I：=I+1），找到第一个大于X的值，两者交换； 5）重复第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）确定该区间的中点位置：mid=（low+high）/2 min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置（2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间： A)如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中,这时high=mid-1; B)如果R[mid].key 实验七查找、排序的应用 一、实验目的 1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。 2、学会比较各种排序与查找算法的优劣。 3、学会针对所给问题选用最适合的算法。 4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。 二、实验内容 [问题描述] 对学生的基本信息进行管理。 [基本要求] 设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1．总成绩要求自动计算； 2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）； 3．排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。 [测试数据] 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握哈希表的定义，哈希函数的构造方法。 2、掌握一些常用的查找方法。 1、掌握几种常用的排序方法。 2、掌握直接排序方法。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。 五、算法设计 a、折半查找 设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时，令low=1,high=n,mid=(low+high)/2，让key与mid指向的记录比较， 若key==r[mid].key，查找成功 若key 2010级数据结构实验报告 实验名称：排序 姓名：袁彬 班级： 2009211120 班内序号： 09 学号： 09210552 日期： 2010 年12 月19 日 1．实验要求 试验目的： 通过选择试验内容中的两个题目之一，学习、实现、对比各种排序的算法，掌握各种排序算法的优缺点，以及各种算法使用的情况。 试验内容： 题目一： 使用简单数组实现下面各种排序算法，并进行比较。 排序算法如下： ①插入排序； ②希尔排序 ③冒泡排序； ④快速排序； ⑤简单选择排序； ⑥堆排序 ⑦归并排序 ⑧基数排序 ⑨其他。 具体要求如下： ①测试数据分为三类：正序，逆序，随机数据。 ②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。 ③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。 ④对②和③的结果进行分析，验证上述各种算法的时间复杂度。 ⑤编写main()函数测试各种排序算法的正确性。 题目二： 使用链表实现下面各种排序算法，并进行比较。 排序算法如下： ①插入排序； ②冒泡排序； ③快速排序； ④简单选择排序； ⑤其他。 具体要求如下： ①测试数据分为三类：正序，逆序，随机数据。 ②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。 ③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙（选作） ④对②和③的结果进行分析，验证上述各种算法的时间复杂度。 ⑤编写main()函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构 程序中每一个算法均是用一个类来表示的，类中有自己的构造函数、排序函数。 程序的储存结构采用数组。数组的第一个位置不存储数据。数据从第二个位置开始。数组中的相对位置为数组的下标。 2.2 关键算法分析 ㈠、关键算法： 1、插入排序函数：Insert s ort(int n) ①、从2开始做循环，依次和前面的数进行比较：for(int i=2;i<=n;i++) ②、如果后面的比前面的小，则进行前移：if(number[i] 【一】需求分析 课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。 为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。 【二】概要设计 1.堆排序 ⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。 ⑵程序实现及核心代码的注释： for(j=2*i+1; j<=m; j=j*2+1) { if(j temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为："< 《数据结构》实验报告一 学院：班级： 学号：姓名： 日期：程序名 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输入结点值。 2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找 不到，则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 二、源程序及注释： #include 一、实验目的 1、了解内排序都是在内存中进行的。 2、为了提高数据的查找速度，需要对数据进行排序。 3、掌握内排序的方法。 二、实验内容 1、设计一个程序e xp10—1.cpp实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序 过程。 （1）源程序如下所示： //文件名:exp10-1.cpp #include 实验四：查找与排序 【实验目的】 1.掌握顺序查找算法的实现。 2.掌握折半查找算法的实现。 【实验内容】 1.编写顺序查找程序，对以下数据查找37所在的位置。 5，13，19，21，37，56，64，75，80，88，92 2.编写折半查找程序，对以下数据查找37所在的位置。 5，13，19，21，37，56，64，75，80，88，92 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。 至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4．写好代码 5．编译－＞链接－＞调试 #include "stdio.h" #include "malloc.h" #define OVERFLOW -1 #define OK 1 #define MAXNUM 100 typedef int Elemtype; typedef int Status; typedef struct { Elemtype *elem; int length; }SSTable; Status InitList(SSTable &ST ) { int i,n; ST.elem = (Elemtype*) malloc (MAXNUM*sizeof (Elemtype)); if (!ST.elem) return(OVERFLOW); printf("输入元素个数和各元素的值:"); scanf("%d\n",&n); for(i=1;i<=n;i++) { scanf("%d",&ST.elem[i]); } ST.length = n; return OK; } int Seq_Search(SSTable ST,Elemtype key) { int i; ST.elem[0]=key; for(i=ST.length;ST.elem[i]!=key;--i); return i; } int BinarySearch(SSTable ST,Elemtype key) { int low,high,mid; low=1; high=ST.length; 数据结构实验报告 实验名称：实验四——排序 学生姓名：XX 班级： 班内序号： 学号： 日期： 1．实验要求 实验目的： 通过选择实验内容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 题目1： 使用简单数组实现下面各种排序算法，并进行比较。 排序算法如下： 1、插入排序； 2、希尔排序； 3、冒泡排序； 4、快速排序； 5、简单选择排序； 6、堆排序； 7、归并排序； 8、基数排序（选作）； 9、其他。 具体要求如下： 1、测试数据分成三类：正序、逆序、随机数据。 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关 键字交换记为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。 5、编写main（）函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构 存储结构：数组 2.2 关键算法分析 一、关键算法： 1、插入排序 a、取排序的第二个数据与前一个比较 b、若比前一个小，则赋值给哨兵 c、从后向前比较，将其插入在比其小的元素后 d、循环排序 2、希尔排序 a、将数组分成两份 b、将第一份数组的元素与哨兵比较 c、若其大与哨兵，其值赋给哨兵 d、哨兵与第二份数组元素比较，将较大的值赋给第二份数组 e、循环进行数组拆分 3、对数据进行编码 a、取数组元素与下一个元素比较 b、若比下一个元素大，则与其交换 c、后移，重复 d、改变总元素值，并重复上述代码 4、快速排序 a、选取标准值 b、比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后 指针前移，重新比较 c、否则后面元素赋给前面元素 d、若后指针元素小于标准值，前指针后移，重新比较 e、否则前面元素赋给后面元素 5、简单选择排序 a、从数组中选择出最小元素 b、若不为当前元素，则交换 c、后移将当前元素设为下一个元素 6、堆排序 a、生成小顶堆 b、将堆的根节点移至数组的最后 c、去掉已做过根节点的元素继续生成小顶堆 实验报告3 实验名称：数据结构与软件设计实习 题目：内部排序算法比较 专业：生物信息学班级：01 姓名：学号：实验日期：2010.07.24 一、实验目的： 比较冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序； 二、实验要求： 待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数； 对结果做简单的分析，包括各组数据得出结果的解释； 设计程序用顺序存储。 三、实验内容 对各种内部排序算法的时间复杂度有一个比较直观的感受，包括关键字比较次数和关键字移动次数。 将排序算法进行合编在一起，可考虑用顺序执行各种排序算法来执行，最后输出所有结果。 四、实验编程结果或过程： 1. 数据定义 typedef struct { KeyType key; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length; }SqList; 2. 函数如下，代码详见文件“排序比较.cpp”int Create_Sq(SqList &L) void Bubble_sort(SqList &L)//冒泡排序void InsertSort(SqList &L)//插入排序 void SelectSort(SqList &L) //简单选择排序int Partition(SqList &L,int low,int high) void QSort(SqList &L,int low,int high)//递归形式的快速排序算法 void QuickSort(SqList &L) void ShellInsert(SqList &L,int dk)//希尔排序 void ShellSort(SqList &L,int dlta[ ]) 3. 运行测试结果，运行结果无误，如下图语速个数为20 实验四——查找 一、实验目的 1.掌握顺序表的查找方法，尤其是折半查找方法； 2.掌握二叉排序树的查找算法。 二、实验内容 1.建立一个顺序表，用顺序查找的方法对其实施查找； 2.建立一个有序表，用折半查找的方法对其实施查找； 3.建立一个二叉排序树，根据给定值对其实施查找； 4.对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。 三、实验预习内容 实验一包括的函数有：typedef struct ，创建函数void create(seqlist & L)，输出函数void print(seqlist L)，顺序查找int find(seqlist L,int number)，折半查找int halffind(seqlist L,int number) 主函数main(). 实验二包括的函数有：结构体typedef struct，插入函数void insert(bnode * & T,bnode * S)，void insert1(bnode * & T)，创建函数void create(bnode * & T)，查找函数bnode * search(bnode * T,int number)，主函数main(). 四、上机实验 实验一： 1.实验源程序。 #include<> #define N 80 typedef struct { int number; umber; for(i=1;[i].number!=0;) { cin>>[i].name>>[i].sex>>[i].age; ++; cout< 《编程实训》 实验报告书 专业：计算机科学与技术 班级：151班 学号： 姓名： 指导教师： 日期：2016年6月30日 目录 一、需求分析 (3) 1.任务要求 (3) 2.软件功能分析 (3) 3.数据准备 (3) 二、概要设计 (3) 1.功能模块图 (4) 2.模块间调用关系 (4) 3.主程序模块 (5) 4.抽象数据类型描述 (5) 三、详细设计 (6) 1.存储结构定义 (6) 2.各功能模块的详细设计 (7) 四、实现和调试 (7) 1.主要的算法 (7) 2.主要问题及解决 (8) 3.测试执行及结果 (8) 五、改进 (9) 六、附录 (9) 1.查找源程序 (9) 2.排序源程序 (9) 目录 1 需求分析 1.1 任务要求 对于从键盘随机输入的一个序列的数据，存入计算机内，给出各种查找算法的实现； 以及各种排序算法的实现。 1.2 软件功能分析 任意输入n个正整数，该程序可以实现各类查找及排序的功能并将结果输出。 1.3 数据准备 任意输入了5个正整数如下： 12 23 45 56 78 2 概要设计（如果2，3合并可以省略2.4） 2.1 功能模块图（注：含功能说明） 2.2 模块间调用关系 2.3 主程序模块 2.4 抽象数据类型描述 存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。又称为存储结构。数据类型（data type）是一个“值”的集合和定义在此集合上的一组操作的总称。 3 详细设计 3.1 存储结构定义 查找： typedef int ElemType ; //顺序存储结构 typedef struct { ElemType *elem; //数据元素存储空间基址，建表时按实际长度分配，号单元留空 int length; //表的长度 河南工业大学实验报告 课程名称数据结构实验项目实验三查找和排序(二)——排序院系信息学院计科系专业班级计科1203 姓名张伟龙学号 201216010313 指导老师范艳峰日期 2013.6.5 批改日期成绩 一实验目的 掌握希尔排序、快速排序、堆排序的算法实现。 二实验内容及要求 实验内容：1．实现希尔排序。 2．实现快速排序。 3. 实现堆排序。 （三选一） 实验要求：1. 根据所选题目，用C语言编写程序源代码。 2. 源程序必须编译调试成功，独立完成。 三实验过程及运行结果 选择第三题： Source Code： #include int rchild=2*i+1; //i的右孩子节点序号 int max=i; //临时变量 if(i<=size/2) //如果i是叶节点就不用进行调整 { if(lchild<=size&&a[lchild]>a[max]) { max=lchild; } if(rchild<=size&&a[rchild]>a[max]) { max=rchild; } if(max!=i) { swap(a[i],a[max]); HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆 } } } void BuildHeap(int *a,int size) //建立堆 { int i; for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2 { HeapAdjust(a,i,size); } } 数据结构与算法》实验报告 一、需求分析 问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 基本要求： （l ）对以下 6 种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 （2 ）待排序表的表长不小于100000 ；其中的数据要用伪随机数程序产生；至少要用 5 组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为 3 次移动）。 （ 3 ）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。数据测试：二．概要设计 1. 程序所需的抽象数据类型的定义： typedef int BOOL; typedef struct StudentData { } Data; typedef struct LinkList { Data Record[MAXSIZE]; int num; // 存放关键字 int Length; // 数组长度// 用数组存放所有的随机数 // 说明BOOL 是int 的别名 } LinkList int RandArray[MAXSIZE]; // 定义长度为MAXSIZE 的随机数组 void RandomNum() // 随机生成函数 void InitLinkList(LinkList* L) // 初始化链表 // 比较所有排序 2 . 各程序模块之间的层次（调用）关系： BOOL LT(int i, int j,int* CmpNum) // 比较 i 和 j 的大小 void Display(LinkList* L) // 显示输出函数 void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum) void QuickSort (LinkList* L, // 快速排序 void HeapSort (LinkList* L, // 堆排序 void BubbleSort(LinkList* L, // 冒泡排序 void SelSort(LinkList* L, // 选择排序 int* CmpNum, int* ChgNum) int* CmpNum, int* ChgNum) int* CmpNum, int* ChgNum) * CmpNum, int* ChgNum) void Compare(LinkList* L,int* CmpNum, int* ChgNum) // 希尔排序 二叉排序树的实现 实验内容与要求 1) 实现二叉排序树，包括生成、插入，删除； 2) 对二叉排序树进行先根、中根、和后根非递归遍历； 3) 每次对树的修改操作和遍历操作的显示结果都需要在屏 幕上用树的形状表示出来。 实验方案 1. 选择链表的方式来构造节点，存储二叉排序树的节点。// 树的结构struct BSTNode { // 定义左右孩子指针 struct BSTNode *lchild,*rchild; // 节点的关键字 TElemType key; }; int depth=0; // 定义一个struct BSTNode 类型的指针typedef BSTNode *Tree; 2. 对树的操作有如下方法： // 创建二叉排序树 Tree CreatTree(Tree T) ； // 二叉树的深度，返回一个int 值为该树的深度 int TreeDepth(Tree T) // 树状输出二叉树，竖向输出 void PrintTree(Tree T , int layer) ； // 查找关键字，如果关键字存在则返回所在节点的父节点，如果关键字不存在则返回叶子所在的节点 Status SearchBST(Tree T , TElemType key , Tree f,Tree &p) ； // 向树中插入节点 Status InsertBST(Tree &T , TElemType e) ； // 删除节点 Status Delete(Tree &T) ； // 删除指定节点，调用Delete(Tree &T) 方法 Status DeleteData(Tree &T , TElemType key) ； // 非递归先序遍历void x_print(Tree T); // 非递归中序遍历 Void z_print(Tree T ); // 非递归后序遍历 void h_print(Tree T); 3. 对二叉排序树非递归先根、中根、后根遍历，采用栈来存储一次遍历过的节点的形式来辅助实现 // 自定义类型以SElemType 作为栈中指针返回的值的类型 // 也就是要返回一个节点的指针 typedef Tree SElemType; // 栈的结构 struct Stack { // 栈底指针SElemType *base; // 栈顶指针SElemType *top; // 栈的容量 int stacksize; }; 4. 栈的操作方法： // 创建一个空栈 Status InitStack(Stack &S) // 获取栈顶元素并删除栈中该位置的元素SElemType Pop(Stack &S,SElemType &elem) // 获取栈顶元素返回栈顶元素不对栈做任何修改SElemType getTop(Stack S,SElemType &elem) // 删除栈顶元素 Status DeleteTop(Stack &S) // 往栈中压入数据 Status Push(Stack &S,SElemType elem) // 判断栈是否为空 Status IsEmpty(Stack S) 三、代码实现 #include 《数据结构》课程设计报告 实验五排序 一、需求分析： 本演示程序用C++6.0编写，完成各种排序的实现，对输入的一组数字实现不同的排序方法，对其由小到大顺序输出。 （1）分别对直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序算法进行编写。 （2）、对存储的函数即输入的数字进行遍历。 （3）、初始化函数对输入的数字进行保存。 （4）、主函数实现使用者操作界面的编写，对输入、选择、保存、输出的各种实现。这当中还包括了各个函数的调用的实现。 （5）、程序所能达到的功能：完成对输入的数字的生成，并通过对各排序的选择实现 数字从小到大的输出。 二、程序主要功能以及基本要求： （1）、设计一个菜单，格式如下： 1、直接插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、选择排序 6、堆排序 7、退出 （2）、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。 三、系统框架图： 本程序包含了9个函数，它们分别是： （1）、直接插入排序的算法函数InsertSort（）。 （2）、希尔排序的算法函数ShellSort（）。 （4）、快速排序的算法函数Partition（）。 （5）、选择排序算法函数SelectSort（）。 （6）、堆排序算法函数HeapAdjust（）。 （7）、对存储数字的遍历函数Visit（）。 （8）、初始化函数InitSqList（）。 （9）、主函数main（）。 四、详细设计 实现各个算法的主要内容，下面是各个函数的主要信息： （1）各个排序函数的算法： 一、直接插入排序 void InsertSort(SqList &L) { int i,j; for( i=2; i<=L.length;i++) { if(L.r[i].key < L.r[i-1].key) { L.r[0] = L.r[i]; L.r[i] = L.r[i-1]; for( j=i-2; (L.r[0].key < L.r[j].key); j--) L.r[j+1] = L.r[j]; L.r[j+1] = L.r[0]; } } } 二、希尔排序 void ShellSort(SqList &L) { int i, j; int dk = 1;//增量 while(dk <=L.length/3) dk = 3*dk+1;//增大增量 while(dk>0) { dk /= 3;//减小增量 for (i = dk; i <=L.length; i++) { L.r[0].key = L.r[i].key; j = i;算法排序问题实验报告
实验报告-排序与查找
(完整word版)查找、排序的应用 实验报告
排序问题实验报告
各种排序实验报告
顺序表的查找、插入与删除实验报告
数据结构内排序实验报告
查找与排序实验报告
大数据结构实验四题目一排序实验报告材料
内部排序比较 (实验报告+源程序)C++
《数据结构》实验报告查找
查找排序实验报告
河南工业大学实验报告——查找和排序(排序)——张伟龙
数据结构(C语言版)实验报告-(内部排序算法比较)
二叉排序树实验报告
数据结构排序实验报告