直接插入排序、直接选择排序、堆排序、快速排序、冒泡排序的实验报告

XXX大学实验 学院：计算计科学与信息学院    专业：数字媒体技术    班级：数媒091 姓名 学号 实验组   实验时间   指导教师 成绩   实验项目名称 实验目的 1．熟练掌握顺序表和有序表的查找方法。 2．熟悉静态查找树的构造方法和查找算法，熟练掌握二叉排序树的构造方法和查找算法。 3．掌握描述查找过程的判定树的构造方法，掌握各种查找方法在等概率情况下查找成功时的平均查找长度。 实验要求 1．了解散列表的构造和查找算法。 2．了解各种排序方法的执行过程及其所依据的原则，掌握各种排序方法时间复杂度的分析方法。 3．熟练掌握希尔排序、快速排序、堆排序等高效排序算法。 实验原理 在visual c++编程环境中编写程序源代码，并编译、运行程序结果 实验仪器 奔腾2计算机或以上机型、visual c++编程环境 实验步骤 1、 确定数据的结构 2、 编写头文件、函数及变量声明 3、 设计子函数 4、 写主函数，并调用子函数 5、 调试编写好的程序 6、 编译正确后，运行，观察分析结果 实验内容 程序1 内部排序算法比较 [问题描述] 编写常用的排序算法，并编写主程序测试。 [基本要求] （1）对以下常用的6种排序算法进行比较：直接插入排序、直接选择排序、堆排序、快速排序、冒泡排序。 （2）待排序表的表长不小于100；其中的数据用自行设计。 （3）对结果作出分析。 直接插入排序 void InsertSort ( ElemType A[], int n ) { int i, j; ElemType x; for ( i=1; i=0; j-- ) { //从第i-1个开始往前找插入点 if ( x.stn < A[j].stn ) A[j+1]=A[j]; else break; } A[j+1]=x; //插入 } } 直接选择排序 void SelectSort(ElemType A[], int n) { int i, j, k; ElemType x; for ( i=0; i<=n-2; i++ ) { //每一趟选择最小元素并与A[i]交换 k=i; for (j=i+1; j<=n-1; j++) //查找最小元素的下标 if (A[j].stn = 0; i--) Sift(A, n, i); //调整A[i..n-1]使之为一个堆 } void Sift(ElemType A[], int n, int i) { // 调整A[i..n-1]成为一个堆（它的左右子树已是一个堆） ElemType x=A[i]; int j = 2 * i + 1; // j为i的左孩子 while (j <= n-1) { // i有左子树 if ( j +1 < n && A[j].stn < A[j+1].stn ) j++; // 使j指向左右孩子中排序码大的孩子 if ( x.stn < A[j].stn) { //将A[j]上移，以便向下筛 A[i]=A[j]; i=j; j=2*i+1; } else break; } A[i]=x; } void HeapSort(ElemType A[], int n) { //A为待排序表， n为表的长度 int i; ElemType x； CreatHeap(A, n); // 把A建成一个堆 for (i = n - 1; i >= 1; i- -) { x = A[0]; //第0个元素与第i个元素交换 A[0] = A[i]; A[i] = x; Sift(A, i, 0); //调整A[0..i-1]使之为一个堆 } } 冒泡排序 void BubbleSort( ElemType A[], int n ) { int i, j, flag; //flag为交换标记 ElemType x; for (i=1; i<=n-1; i++) { // 最多n-1趟排序 flag=0; //假设本次没有交换 for (j=n-1; j>=i; j--) //第i 趟 if ( A[j].stn < A[j-1].stn ) { flag=1; //出现交换 x=A[j]; A[j]=A[j-1]; A[j-1]=x; } if (flag==0) return; } } 快速排序 void QuickSort(ElemType A[ ], int s, int t) { //递归算法，对区间 A[s] ～A[t] 进行快速排序 int i=s+1, j=t; ElemType temp, x = A[s]; //第一个为基准元素 while ( i<=j ) { while ( i<=j && A[i].stn <= x.stn ) i++; //从左到右 while ( i<=j && A[j].stn >= x.stn ) j--; //从右到左 if ( i < j ) { temp=A[i]; A[i]=A[j]; A[j]=temp; i++; j--; } } if (s!=j) { //交换基准元素 A[s]=A[j]; A[j]=x; } if (s using namespace std; typedef int ElemType; //直接插入排序 void InsertSort ( ElemType A[], int n ) { int i, j; ElemType x; for ( i=1; i=0; j-- ){ //从第i-1个开始往前找插入点 if ( x< A[j] ) A[j+1]=A[j]; else break; } A[j+1]=x; //插入 } } //直接选择排序 void SelectSort(ElemType A[], int n) { int i, j, k; ElemType x; for ( i=0; i<=n-2; i++ ) { //每一趟选择最小元素并与A[i]交换 k=i; for (j=i+1; j<=n-1; j++) //查找最小元素的下标 if (A[j]= 0; i--) Sift(A, n, i); //调整A[i..n-1]使之为一个堆 } void Sift(ElemType A[], int n, int i) { // 调整A[i..n-1]成为一个堆（它的左右子树已是一个堆） ElemType x=A[i]; int j = 2 * i + 1; // j为i的左孩子 while (j <= n-1) { // i有左子树 if ( j +1 < n && A[j]< A[j+1]) j++; // 使j指向左右孩子中排序码大的孩子 if ( x< A[j]) { //将A[j]上移，以便向下筛 A[i]=A[j]; i=j; j=2*i+1; } else break; } A[i]=x; } void HeapSort(ElemType A[], int n) { //A为待排序表，n为表的长度 int i; ElemType x; CreatHeap(A, n); // 把A建成一个堆 for(i=n-1;i>=1;i--){ x = A[0]; //第个元素与第i个元素交换 A[0] = A[i]; A[i] = x; Sift(A, i, 0); //调整A[0..i-1]使之为一个堆 } } //冒泡排序 void BubbleSort( ElemType A[], int n ) { int i, j, flag; //flag为交换标记 ElemType x; for (i=1; i<=n-1; i++) { // 最多n-1趟排序 flag=0; //假设本次没有交换 for (j=n-1; j>=i; j--) //第i 趟 if ( A[j]< A[j-1]) { flag=1; //出现交换 x=A[j]; A[j]=A[j-1]; A[j-1]=x; } if (flag==0) return; } } //快速排序 void QuickSort(ElemType A[], int s, int t) { //递归算法，对区间A[s] ～A[t] 进行快速排序 int i=s+1, j=t; ElemType temp, x = A[s]; //第一个为基准元素 while ( i<=j ){ while ( i<=j && A[i]<= x ) i++; //从左到右 while ( i<=j && A[j]>=x) j--; //从右到左 if ( i < j ) { temp=A[i]; A[i]=A[j]; A[j]=temp; i++; j--; } } if (s!=j){ //交换基准元素 A[s]=A[j]; A[j]=x; } if (s>A[j]; cout<<"排序前为："<总结

初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf