数据结构课程设计
实习
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
目：
排序
学 号：
1010549
姓 名：
张琳琳
年 级：
10级
学 院：
信科院
专 业：
计算机
完成日期：
授课教师：
辛运帏
1. 题目
给定N个int类型（自定N的上限M，例如M=100000，N的取值不能少于10000）的整数，分别使用插入排序、快速排序、归并排序和堆排序
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
进行升序排序。
具体要求：
1 四种排序方法均能得到正确的排序结果。
2 分别统计四种排序中关键字比较的次数和记录交换的次数，并将统计结果显示出来。
2. 要求
初始数据使用随机数发生器产生，并使用程序自动检验排序结果的正确性。同时，需要编写一个检验随机性的小测试程序，分别统计各数段间数据的个数。数段的划分自定。例如可以按1000为一单位，分别统计（0，999）、（1000，1999）、…（N-1000，N-1）之间的数据个数。如果N较大，也可以按10000为一单位。总之，只要能说明问题即可。在一个数段内，还可以再
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
各子数段中数据的个数，例如选定（1000，1999）数段，然后以100为一单位，统计这10个子数段中的数据个数。
程序实现
1 插入排序：
bool InSort(int a[],int n,double &ChaNum,double &ComNum)
{
for(int i=1;i
0;j--)
{
ComNum++;
if(a[j]pivot)
{
ComNum++;
}
ComNum++;
swap(a[r],a[--l]);
ChaNum++;
}while(l=left;i--)
{
b[i]=a[i];
}
for(int j=1;j<=right-mid;j++)
{
b[right-j+1]=a[j+mid];
}
int k;
for(i=left,j=right, k=left;k<=right;k++)
{
if(b[i]=0; i--)
PercolateDown(p, i, size,ChaNum,ComNum);
}
删除大根堆的根
void DeleteMax(int p[], int size,double &ChaNum,double &ComNum)
swap(p[0],p[size-1]);
ChaNum++;
PercolateDown(p, 0, --size,ChaNum,ComNum);
判断下标为hole的元素是否满足堆得条件
void PercolateDown(int array[],int hole, int size,double &ChaNum,double &ComNum)//不能满足进行调整
{
int tmp = array[hole];
int child=0;
for ( ; (hole*2+1)<=(size-1); hole=child)
{
child = hole*2 + 1;
if (child array[child]))
{
ComNum++;
child++;
}
ComNum++;
if (array[child]>tmp)
{
ComNum++;
array[hole] = array[child];
ChaNum++;
}
else
{
ComNum++;
break;
}
}
array[hole] = tmp;
}
堆排序函数
bool HeapSort(int p[], int size,double &ChaNum,double &ComNum)
{
BuildMaxHeap(p, size,ChaNum,ComNum);
for (int i=size; i>=1; i--)
{
DeleteMax(p, i,ChaNum,ComNum) }
return (testResult(p, size));
}
3.1程序运行及编译环境
给出该程序的运行环境：windows ,编译环境，如：vc++ 6.0等
3.2程序描述
用数组保存随机数，在main函数中调用相应的排序函数（如上），和检查函数，每次对交换和比较次数清零。再继续。
3.3实现功能
1 产生随机数 2 四种排序的实现
输入项
随机数个数 然后是排序方法
输出项
相应排序方法的结果的正确性
3.3.1.3数据结构的定义
int *a,*b;//.......................产生数组a
a=new int[n];
b=new int[n];
generateData(a,n); //产生随机数
for(int i=0;imax)
max=a[i];
}
TestDataFeature(a,n);
}
一 插入排序算法描述如下：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2
二 快速排序的算法是：
设要排序的数组是A[0]……A[N-1]
1.设置两个变量I、J，排序开始的时候：I=0，J=N-1；
2.以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；
3.从J开始向前搜索，即由后开始向前搜索（J=J-1即J--），找到第一个小于key的值A[j]，A[j]与A[i]交换；
4.从I开始向后搜索，即由前开始向后搜索（I=I+1即I++），找到第一个大于key的A[i]，A[i]与A[j]交换；
5.重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。）
三 归并排序
1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4.重复步骤3直到某一指针达到序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾
四 堆排序
用大根堆排序的基本思想
1.先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
2.再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
3.由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
3.4运行结果
3.5尚未解决的问题
对于进行检验的函数，比较和交换的次数在有些情况并不准确
PAGE
第6页
浙公网安备 33021202002483