数据结构实验七 排序

数据结构排序实验报告数据结构排序实验报告引言：数据结构是计算机科学中的重要概念之一，它涉及到数据的组织、存储和操作方式。

排序是数据结构中的基本操作之一，它可以将一组无序的数据按照特定的规则进行排列，从而方便后续的查找和处理。

本实验旨在通过对不同排序算法的实验比较，探讨它们的性能差异和适用场景。

一、实验目的本实验的主要目的是通过实际操作，深入理解不同排序算法的原理和实现方式，并通过对比它们的性能差异，选取合适的排序算法用于不同场景中。

二、实验环境和工具实验环境：Windows 10 操作系统开发工具：Visual Studio 2019编程语言：C++三、实验过程1. 实验准备在开始实验之前，我们需要先准备一组待排序的数据。

为了保证实验的公正性，我们选择了一组包含10000个随机整数的数据集。

这些数据将被用于对比各种排序算法的性能。

2. 实验步骤我们选择了常见的五种排序算法进行实验比较，分别是冒泡排序、选择排序、插入排序、快速排序和归并排序。

- 冒泡排序：该算法通过不断比较相邻元素的大小，将较大的元素逐渐“冒泡”到数组的末尾。

实现时，我们使用了双重循环来遍历整个数组，并通过交换元素的方式进行排序。

- 选择排序：该算法通过不断选择数组中的最小元素，并将其放置在已排序部分的末尾。

实现时，我们使用了双重循环来遍历整个数组，并通过交换元素的方式进行排序。

- 插入排序：该算法将数组分为已排序和未排序两部分，然后逐个将未排序部分的元素插入到已排序部分的合适位置。

实现时，我们使用了循环和条件判断来找到插入位置，并通过移动元素的方式进行排序。

- 快速排序：该算法通过选取一个基准元素，将数组分为两个子数组，并对子数组进行递归排序。

实现时，我们使用了递归和分治的思想，将数组不断划分为更小的子数组进行排序。

- 归并排序：该算法通过将数组递归地划分为更小的子数组，并将子数组进行合并排序。

实现时，我们使用了递归和分治的思想，将数组不断划分为更小的子数组进行排序，然后再将子数组合并起来。

数据结构实验报告排序一、实习目的熟悉几种典型的排序方法，并对各种算法的特点、使用范围和效率有进一步的了解。

二、实例排序是计算机科学中非常基本且使用频繁的运算，在计算机系统软件和应用软件中都有广泛的应用。

下面给出的是冒泡排序、快速排序的实现与比较。

/* 源程序的头文件sort.h */void getra ndat(Data ary[],i nt cou nt) /* 产生一批随机数，准备排序*/{ long int a=100001;int i;for(i=0;i<cou nt;i++){ a=(a*125)%2796203;ary[i].key=(i nt)a;}} /* getra ndat */void prdata(Data ary[],i nt count) I*输出数据的函数*/{ int i; char ch;printf( n“)；for(i=0;i<count;i++) printf( “ ％6c”，ary[i].key);printf( n“)；printf( "\n\n 打回车键，结束显示。

“)；ch=getch();} I* prdata *I[两种排序方法的比较源程序]I* sortcmp.c *I#in clude <stdio.h>#in clude <stdlib.h>#define MAX 1000 I*数组最大界限*Itypedef int ElemType; I* 关键字的类型*Itypedef struct{ ElemType key;int shu;}Data;Data ar[MAX],br[MAX];typedef struct{ int lo,hi;}Selem;typedef struct{ Selem elem[MAX];int top;}SqStack;SqStack s1;/* 函数声明*/void bubble(Data ary[],int n);void getrandat(Data ary[],int count) ; void qksort(Data ary[],int n);void hoare(Data ary[],int l,int h); void init_s(SqStack *s);void push(SqStack *s,Selem e); Selem pop(SqStack *s);void prdata(Data ary[],int count); int empty(SqStack s);/* 主函数*//* 其它属性域*//* 一个纪录的结构体类型*//* 栈的元素结构体类型*//* 一维数组子域*//* 栈顶指针子域*//* 栈的顺序结构体类型*//* 产生一批随机数，准备排序*//* 进栈一个元素*/ /* 输出数据的函数*/void main(){ int k,n,j; j; char ch;do { printf("\n\n\n");printf("\n\n 1. 产生一批随机数准备排序");printf("\n\n 2. 一般情况的起泡排序");printf("\n\n 3. 有序情况的起泡排序");printf("\n\n 4. 一般情况的快速排序");printf("\n\n 5. 有序情况的快速排序");printf("\n================== printf("\n 请输入您的选择 scanf("%d",&k); switch(k){ case 1:{ printf("the number ofdatas:"); /*scanf("%d",&n);getrandat(ar,n); for(j=0;j<n;j++)br[j]=ar[j]; prdata(ar,n); } break;case 2:{ for(j=0;j<n;j++) ar[j]=br[j];bubble(ar,n); prdata(ar,n); } break;case 3: { bubble( ar,n); prdata(ar,n);} break;=================="); (1,2,3，4，5，6)");输入数据个数 *//*产生 n 个随机数 *//* 保留复原始数据 *//* 恢复原始数据 */ /* 对 n 个数据起泡排序 *//* 排序后输出 *//* 有序情况的起泡排序 */ 恢复原始数据*//* 对 n 个数据快速排序 *//* 排序后输出 *//* 有序情况的快速排序 */case 4:{ for(j=0;j<n;j++) ar[j]=br[j]; /*qksort(ar,n); prdata(ar,n);} break;case 5:{ qksort(ar,n);prdata(ar,n);} break;case 6: exit(0);} /* switch */printf("\n --------------- ");}while(k>=1 && k<6);printf("\n 打回车键，返回。

本章共8道实验题目。

一、直接插入排序1. 定义顺序表的存储结构2. 初始化顺序表为空表3. 输入10个元素创建含有10个元素的顺序表4. 输出顺序表5. 对顺序表进行直接插入排序（InsertSort）6. 输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 60211 938 669 507 117 261 708 343 300 60211 117 261 300 343 507 602 669 708 938程序:#include <iostream>#include <algorithm>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;//此处定义直接插入排序函数int a[20];int main(){int InsertSort;for (int i = 0; i < 10; ++i){cin >> a[i];cout << a[i] << " ";}cout << endl;sort(a, a+10);for (int i = 0; i < 10; ++i)cout << a[i] << " ";return 0;}二、折半插入排序1. 定义顺序表的存储结构2. 初始化顺序表为空表3. 输入10个元素创建含有10个元素的顺序表4. 输出顺序表5. 对顺序表进行折半插入排序（BInsertSort）6. 输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 60211 938 669 507 117 261 708 343 300 60211 117 261 300 343 507 602 669 708 938程序：#include <iostream>#include <algorithm>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;//此处定义折半插入排序函数int a[20];int main(){int BInsertSort ;for (int i = 0; i < 10; ++i){cin >> a[i];cout << a[i] << " ";}cout << endl;sort(a, a+10);for (int i = 0; i < 10; ++i)cout << a[i] << " ";return 0;}三、希尔排序1. 定义顺序表的存储结构2. 初始化顺序表为空表3. 输入10个元素创建含有10个元素的顺序表4. 输出顺序表5. 对顺序表进行希尔排序（ShellSort）6. 输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 602 11 938 669 507 117 261 708 343 300 602 11 117 261 300 343 507 602 669 708 938 程序：#include <iostream>#include <algorithm>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;int a[20];int main(){int ShellSort;for (int i = 0; i < 10; ++i){cin >> a[i];cout << a[i] << " ";}cout << endl;sort(a, a+10);for (int i = 0; i < 10; ++i)cout << a[i] << " ";return 0;}四、冒泡排序1.定义顺序表的存储结构2.初始化顺序表为空表3.输入10个元素创建含有10个元素的顺序表4.输出顺序表5.对顺序表进行冒泡排序（BubbleSort）6.输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 60211 938 669 507 117 261 708 343 300 60211 117 261 300 343 507 602 669 708 938程序：#include <iostream>#include <algorithm>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;int a[20];int main(){int BubbleSort;for (int i = 0; i < 10; ++i){cin >> a[i];cout << a[i] << " ";}cout << endl;sort(a, a+10);for (int i = 0; i < 10; ++i)cout << a[i] << " ";return 0;}五、快速排序1.定义顺序表的存储结构2.初始化顺序表为空表3.输入10个元素创建含有10个元素的顺序表4.输出顺序表5.对顺序表进行快速排序（QuickSort）6.输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 60211 938 669 507 117 261 708 343 300 60211 117 261 300 343 507 602 669 708 938程序：#include <iostream>#include <algorithm>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;int a[20];int main(){int QuickSort;for (int i = 0; i < 10; ++i){cin >> a[i];cout << a[i] << " ";}cout << endl;sort (a, a+10);for (int i = 0; i < 10; ++i)cout << a[i] << " ";return 0;}六、简单选择排序1.定义顺序表的存储结构2.初始化顺序表为空表3.输入10个元素创建含有10个元素的顺序表4.输出顺序表5.对顺序表进行简单选择排序（SelectSort）6.输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 60211 938 669 507 117 261 708 343 300 602 11 117 261 300 343 507 602 669 708 938 程序：#include <iostream>#include <algorithm>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;int a[20];int main(){int SelectSort;for (int i = 0; i < 10; ++i){cin >> a[i];cout << a[i] << " ";}cout << endl;sort(a, a+10);for (int i = 0; i < 10; ++i)cout << a[i] << " ";return 0;}七、堆排序1.定义顺序表的存储结构2.初始化顺序表为空表3.输入10个元素创建含有10个元素的顺序表4.输出顺序表5.对顺序表进行堆排序（HeapSort）6.输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 60211 938 669 507 117 261 708 343 300 60211 117 261 300 343 507 602 669 708 938程序：#include <iostream>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;Status InitList(SqList &L){L.length=0;return 0;}Status CreateList(SqList &L,int n){if(!L.r||n<1||n>MAXSIZE) return ERROR;//cout<<"\n请输入"<<n<<"个元素（用空格隔开）：";for(int i=1;i<=n;i++)cin>>L.r[i].key;L.length=n;return OK;}void ListTraverse(SqList L){//cout<<"L=(";for(int i=1;i<=L.length;i++)cout<<L.r[i].key<<' ';//if(L.length) cout<<'\b';//cout<<")";cout<<endl;}void HeapSort(SqList &L){int value = 0;for(int i = 0;i<L.length;i++)for(int j = 0;j<L.length-i;j++){if(L.r[j].key>L.r[j+1].key){value = L.r[j].key;L.r[j].key= L.r[j+1].key;L.r[j+1].key = value;}}int main(){SqList L;InitList(L);CreateList(L,10);ListTraverse(L);HeapSort(L);ListTraverse(L);return 0;}八、归并排序1.定义顺序表的存储结构2.初始化顺序表为空表3.输入10个元素创建含有10个元素的顺序表4.输出顺序表5.对顺序表进行二路归并排序（MergeSort）6.输出排序后的顺序表例如：11 938 669 507 117 261 708 343 300 60211 938 669 507 117 261 708 343 300 60211 117 261 300 343 507 602 669 708 938程序：#include <iostream>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define MAXSIZE 100typedef int KeyType;typedef char InfoType[256];typedef structKeyType key;InfoType otherinfo;}RedType;typedef struct{RedType r[MAXSIZE+1];int length;}SqList;Status InitList(SqList &L){L.length=0;return 0;}Status CreateList(SqList &L,int n){if(!L.r||n<1||n>MAXSIZE) return ERROR;//cout<<"\n请输入"<<n<<"个元素（用空格隔开）：";for(int i=1;i<=n;i++)cin>>L.r[i].key;L.length=n;return OK;}void ListTraverse(SqList L){//cout<<"L=(";for(int i=1;i<=L.length;i++)cout<<L.r[i].key<<' ';//if(L.length) cout<<'\b';//cout<<")";cout<<endl;}void MSort(){}void Merge(){}void MergeSort(SqList &L){int value = 0;for(int i = 0;i<L.length;i++)for(int j = 0;j<L.length-i;j++){if(L.r[j].key>L.r[j+1].key){value = L.r[j].key;L.r[j].key= L.r[j+1].key;L.r[j+1].key = value;}}}int main(){SqList L;InitList(L);CreateList(L,10);ListTraverse(L);MergeSort(L);ListTraverse(L);return 0;}。

1．实验要求【实验目的】学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

【实验内容】使用简单数组实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。

2. 程序分析2.1 存储结构存储结构：数组2.2 关键算法分析//插入排序void InsertSort(int r[], int n) {int count1=0,count2=0;插入到合适位置for (int i=2; i<n; i++){r[0]=r[i]; //设置哨兵for (int j=i-1; r[0]<r[j]; j--) //寻找插入位置r[j+1]=r[j]; //记录后移r[j+1]=r[0];count1++;count2++;}for(int k=1;k<n;k++)cout<<r[k]<<" ";cout<<endl;cout<<"比较次数为"<<count1<<" 移动次数为"<<count2<<endl; }//希尔排序void ShellSort(int r[], int n){int i;int d;int j;int count1=0,count2=0;for (d=n/2; d>=1; d=d/2) //以增量为d进行直接插入排序{for (i=d+1; i<n; i++){r[0]=r[i]; //暂存被插入记录for (j=i-d; j>0 && r[0]<r[j]; j=j-d)r[j+d]=r[j]; //记录后移d个位置r[j+d]=r[0];count1++;count2=count2+d;}count1++;}for(i=1;i<n;i++)cout<<r[i]<<" ";cout<<endl;cout<<"比较次数为"<<count1<<" 移动次数为"<<count2<<endl; }//起泡排序void BubbleSort(int r[], int n) {插入到合适位置int temp;int exchange;int bound;int count1=0,count2=0;exchange=n-1; //第一趟起泡排序的范围是r[1]到r[n]while (exchange) //仅当上一趟排序有记录交换才进行本趟排序{bound=exchange;exchange=0;for(int j=0;j<bound;j++) //一趟起泡排序{count1++; //接下来有一次比较if(r[j]>r[j+1]){temp=r[j]; //交换r[j]和r[j+1]r[j]=r[j+1];r[j+1]=temp;exchange=j; //记录每一次发生记录交换的位置count2=count2+3; //移动了3次}}}for(int i=1;i<n;i++)cout<<r[i]<<" ";cout<<endl;cout<<"比较次数为"<<count1<<" 移动次数为"<<count2<<endl;}//快速排序一次划分int Partition(int r[], int first, int end,int &count1,int &count2){int i=first; //初始化int j=end;while (i<j){while (i<j && r[i]<= r[j]){j--; //右侧扫描count1++;}count1++;if (i<j){temp=r[i]; //将较小记录交换到前面r[i]=r[j];r[j]=temp;i++;count2=count2+3;}while (i<j && r[i]<= r[j]){i++; //左侧扫描count1++;}count1++;if (i<j){temp=r[j];r[j]=r[i];r[i]=temp; //将较大记录交换到后面j--;count2=count2+3;}}return i; //i为轴值记录的最终位置}//快速排序void QuickSort(int r[], int first, int end,int &count1,int &count2){if (first<end){ //递归结束int pivot=Partition(r, first, end,count1,count2); //一次划分QuickSort(r, first, pivot-1,count1,count2);//递归地对左侧子序列进行快速排序QuickSort(r, pivot+1, end,count1,count2); //递归地对右侧子序列进行快速排序}}//简单选择排序Array void SelectSort(int r[ ], int n){int i;int j;int index;int temp;int count1=0,count2=0;for (i=0; i<n-1; i++) //对n个记录进行n-1趟简单选择排序{index=i;for(j=i+1;j<n;j++) //在无序区中选取最小记录{count1++; //比较次数加一if(r[j]<r[index]) //如果该元素比现在第i个位置的元素小index=j;}count1++; //在判断不满足循环条件j<n时，比较了一次if(index!=i){temp=r[i]; //将无序区的最小记录与第i个位置上的记录交换r[i]=r[index];r[index]=temp;count2=count2+3; //移动次数加3 }}for(i=1;i<n;i++)cout<<r[i]<<" ";cout<<endl;cout<<"比较次数为"<<count1<<" 移动次数为"<<count2<<endl;}//筛选法调整堆void Sift(int r[],int k,int m,int &count1,int &count2) //s，t分别为比较和移动次数{int i;int j;int temp;i=k;j=2*i+1; //置i为要筛的结点，j为i的左孩子while(j<=m) //筛选还没有进行到叶子{if(j<m && r[j]<r[j+1]) j++; //比较i的左右孩子，j为较大者count1=count1+2; //该语句之前和之后分别有一次比较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的位置count2=count2+3; //移动次数加3 }}}//堆排序void HeapSort(int r[],int n){int count1=0,count2=0; //计数器，计比较和移动次数int i;int temp;for(i=n/2;i>=0;i--) //初始建堆，从最后一个非终端结点至根结点Sift(r,i,n,count1,count2) ;for(i=n-1; i>0; i--) //重复执行移走堆顶及重建堆的操作{temp=r[i]; //将堆顶元素与最后一个元素交换r[i]=r[0];r[0]=temp; //完成一趟排序，输出记录的次序状态Sift(r,0,i-1,count1,count2); //重建堆}for(i=1;i<n;i++)cout<<r[i]<<" ";cout<<endl;cout<<"比较次数为"<<count1<<" 移动次数为"<<count2<<endl;}//一次归并void Merge(int r[], int r1[], int s, int m, int t){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]elser1[k++]=r[j++];}if (i<=m)while (i<=m) //若第一个子序列没处理完，则进行收尾处理r1[k++]=r[i++];elsewhile (j<=t) //若第二个子序列没处理完，则进行收尾处理r1[k++]=r[j++];}//一趟归并void MergePass(int r[ ], int r1[ ], int n, int h){int i=0;int k;while (i<=n-2*h) //待归并记录至少有两个长度为h的子序列{Merge(r, r1, i, i+h-1, i+2*h-1);i+=2*h;}if (i<n-h)Merge(r, r1, i, i+h-1, n); //待归并序列中有一个长度小于h else for (k=i; k<=n; k++) //待归并序列中只剩一个子序列r1[k]=r[k];}//归并排序void MergeSort(int r[ ], int r1[ ], int n ){int h=1;int i;while (h<n){MergePass(r, r1, n-1, h); //归并h=2*h;MergePass(r1, r, n-1, h);h=2*h;}for(i=1;i<n;i++)cout<<r[i]<<" ";cout<<endl;}void Newarray(int a[],int b[],int c[]) {cout<<"新随机数组：";c[0]=0;a[0]=0;b[0]=0;for(int s=1;s<11;s++){a[s]=s;b[s]=20-s;c[s]=rand()%50+1;cout<<c[s]<<" ";}cout<<endl;}2.3 其他3. 程序运行结果void main(){srand(time(NULL));const int num=11; //赋值int a[num];int b[num];int c[num];int c1[num];c[0]=0;a[0]=0;b[0]=0;Newarray(a,b,c);cout<<"顺序数组：";for(int j=1;j<num;j++)cout<<a[j]<<" ";cout<<endl;cout<<"逆序数组：";for(j=1;j<num;j++)cout<<b[j]<<" ";cout<<endl;cout<<endl;cout<<"插入排序结果为："<<"\n";InsertSort(a,num);InsertSort(b,num);InsertSort(c,num);cout<<endl;Newarray(a,b,c);cout<<"希尔排序结果为："<<"\n";ShellSort(a, num);ShellSort(b, num);ShellSort(c, num);cout<<endl;Newarray(a,b,c);cout<<"起泡排序结果为："<<"\n";BubbleSort(a, num);BubbleSort(b, num);BubbleSort(c, num);cout<<endl;int count1=0,count2=0;Newarray(a,b,c);cout<<"快速排序结果为："<<"\n";QuickSort(a,0,num-1,count1,count2);for(int i=1;i<num;i++)cout<<a[i]<<" ";cout<<endl;cout<<"比较次数为"<<count1<<" 移动次数为"<<count2<<endl; count1=0,count2=0;QuickSort(b,0,num-1,count1,count2);for(i=1;i<num;i++)cout<<b[i]<<" ";cout<<endl;cout<<"比较次数为"<<count1<<" 移动次数为"<<count2<<endl; count1=0,count2=0;QuickSort(c,0,num-1,count1,count2);for(i=1;i<num;i++)cout<<c[i]<<" ";cout<<endl;cout<<"比较次数为"<<count1<<" 移动次数为"<<count2<<endl;cout<<endl;cout<<endl;Newarray(a,b,c);cout << "简单选择排序结果为：" << "\n";SelectSort(a,num);SelectSort(b,num);SelectSort(c,num);cout<<endl;Newarray(a,b,c);cout << "堆排序结果为：" << "\n";HeapSort(a, num);HeapSort(b, num);HeapSort(c, num);cout<<endl;Newarray(a,b,c);cout << "归并排序结果为：" << "\n";MergeSort(a, c1,num );MergeSort(b, c1,num );MergeSort(c, c1,num );}。

数据结构实验报告-排序一、实验目的本实验旨在探究不同的排序算法在处理大数据量时的效率和性能表现，并对比它们的优缺点。

二、实验内容本次实验共选择了三种常见的排序算法：冒泡排序、快速排序和归并排序。

三个算法将在同一组随机生成的数据集上进行排序，并记录其性能指标，包括排序时间和所占用的内存空间。

三、实验步骤1. 数据的生成在实验开始前，首先生成一组随机数据作为排序的输入。

定义一个具有大数据量的数组，并随机生成一组在指定范围内的整数，用于后续排序算法的比较。

2. 冒泡排序冒泡排序是一种简单直观的排序算法。

其基本思想是从待排序的数据序列中逐个比较相邻元素的大小，并依次交换，从而将最大（或最小）的元素冒泡到序列的末尾。

重复该过程直到所有数据排序完成。

3. 快速排序快速排序是一种分治策略的排序算法，效率较高。

它将待排序的序列划分成两个子序列，其中一个子序列的所有元素都小于等于另一个子序列的所有元素。

然后对两个子序列分别递归地进行快速排序。

4. 归并排序归并排序是一种稳定的排序算法，使用分治策略将序列拆分成较小的子序列，然后递归地对子序列进行排序，最后再将子序列合并成有序的输出序列。

归并排序相对于其他算法的优势在于其稳定性和对大数据量的高效处理。

四、实验结果经过多次实验，我们得到了以下结果：1. 冒泡排序在数据量较小时，冒泡排序表现良好，但随着数据规模的增大，其性能明显下降。

排序时间随数据量的增长呈平方级别增加。

2. 快速排序相比冒泡排序，快速排序在大数据量下的表现更佳。

它的排序时间线性增长，且具有较低的内存占用。

3. 归并排序归并排序在各种数据规模下都有较好的表现。

它的排序时间与数据量呈对数级别增长，且对内存的使用相对较高。

五、实验分析根据实验结果，我们可以得出以下结论：1. 冒泡排序适用于数据较小的排序任务，但面对大数据量时表现较差，不推荐用于处理大规模数据。

2. 快速排序是一种高效的排序算法，适用于各种数据规模。

数据结构实验七查找在计算机科学中，数据结构是组织和存储数据的方式，而查找则是在给定的数据结构中寻找特定元素的操作。

本次实验七的重点就是深入研究查找这一重要的数据处理操作。

查找操作在我们日常生活和计算机程序中无处不在。

想象一下在电话簿中查找一个朋友的号码，或者在图书馆的书架中寻找一本书，这都是查找的实际应用场景。

在计算机程序中，当我们需要从大量数据中快速找到所需的信息时，高效的查找算法就显得至关重要。

常见的查找算法有顺序查找、二分查找、哈希查找等。

顺序查找是最简单直接的方法，它从数据结构的起始位置开始，依次比较每个元素，直到找到目标元素或者遍历完整个数据结构。

这种方法适用于数据量较小或者数据未排序的情况。

让我们通过一个简单的示例来理解顺序查找。

假设有一个整数数组5, 3, 8, 2, 9，我们要查找数字 8。

从数组的第一个元素 5 开始，依次与8 进行比较。

当比较到第三个元素时，找到了目标数字 8，查找结束。

虽然顺序查找的思路简单，但在数据量较大时，它的效率相对较低。

与顺序查找不同，二分查找则要求数据是有序的。

它通过不断将待查找的区间一分为二，逐步缩小查找范围，从而提高查找效率。

还是以整数数组为例，比如 2, 4, 6, 8, 10 要查找数字 6。

首先，比较中间元素 6 和目标数字 6，正好相等，查找成功。

如果要查找的数字小于中间元素，则在左半区间继续查找；如果大于中间元素，则在右半区间查找。

二分查找的效率在有序数据中表现出色。

然而，如果数据经常变动，需要频繁进行插入和删除操作，维护数据的有序性可能会带来较大的开销。

哈希查找则是另一种常见的查找方法。

它通过一个哈希函数将关键字映射到一个特定的位置，从而实现快速查找。

哈希函数的设计至关重要，如果设计不当，可能会导致大量的冲突，影响查找效率。

在实际应用中，选择合适的查找算法取决于多种因素，如数据的规模、数据的分布特征、查找的频繁程度以及对时间和空间复杂度的要求等。

目录1.引言............................................................................................................................ 错误！未定义书签。

2.需求分析.................................................................................................................... 错误！未定义书签。

3.详细设计.................................................................................................................... 错误！未定义书签。

3.1 直接插入排序................................................................................................ 错误！未定义书签。

3.2折半排序......................................................................................................... 错误！未定义书签。

3.3 希尔排序........................................................................................................ 错误！未定义书签。

3.4简单选择排序................................................................................................. 错误！未定义书签。

《数据结构》实验报告排序实验题目：输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。

实验所使用的数据结构内容及编程思路：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为止。

实验七排序
一、目的：
掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和
空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。

二、
要求：
实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。

比较各
种算法的运行速度。

三、实验内容
1、编写各种排序程序。

2、在排序程序中能输出以上各种排序算法的各趟排序结束时，关键
字序列的状态。

3、调试程序，以关键字序列（265，301，751，129，937，863，742，694，76，438）
作为输入数据，采用上述方法进行排序。

四、实验报告要求
要求所编的程序能正确运行，并提交实验报告。

实验报告的基本要求为：1、陈述程序设计的任务，强调程序要做什么，明确规定：（1）输入
的形式和输出值的范围；（2）输出的形式；
（3）程序所能达到的功能；
（4）测试数据：包括正确的输入输出结果和错误的输入及输出结果。

2、说明用到的数据结构定义、主程序的流程及各程序模块之间的调
用关系。

3、提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。

4、调试分析：
（1）调试过程中所遇到的问题及解决方法；（2）算法的时空分析；（3）经验与体会。

5、用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤。

6、测试结果：列出对于给定的输入所产生的输出结果。