数据结构课程设计排序实验报告

实验8 快速排序1．需求分析（1）输入的形式和输入值的范围：第一行是一个整数n，代表任务的件数。

接下来一行，有n个正整数，代表每件任务所用的时间。

中间用空格或者回车隔开。

不对非法输入做处理，及假设用户输入都是合法的。

（2）输出的形式：输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要处理的任务所用的时间。

按此顺序进行，则使得所有任务等待时间最小。

（3）程序所能达到的功能：在操作系统中，当有n 件任务同时来临时，每件任务需要用时ni，输出所有任务等待的时间和最小的任务处理顺序。

（4）测试数据：输入请输入任务个数：9请输入任务用时：5 3 4 2 6 1 5 7 3输出任务执行的顺序：1 2 3 3 4 5 5 6 72．概要设计（1）抽象数据类型的定义：为实现上述程序的功能，应以整数存储用户的第一个输入。

并将随后输入的一组数据储存在整数数组中。

（2）算法的基本思想：如果将任务按完成时间从小到大排序，则在完成前一项任务时后面任务等待的时间总和最小，即得到最小的任务处理顺序。

采取对输入的任务时间进行快速排序的方法可以在相对较小的时间复杂度下得到从小到大的顺序序列。

3．详细设计（1）实现概要设计中定义的所有数据类型：第一次输入的正整数要求大于零，为了能够存储，采用int型定义变量。

接下来输入的一组整数，数据范围大于零，为了排序需要，采用线性结构存储，即int类型的数组。

（2）实现程序的具体步骤：一.程序主要采取快速排序的方法处理无序数列：1．在序列中根据随机数确定轴值，根据轴值将序列划分为比轴值小和比轴值大的两个子序列。

2．对每个子序列采取从左右两边向中间搜索的方式，不断将值与轴值比较，如果左边的值大于轴值而右边的小于轴值则将二者交换，直到左右交叉。

3．分别对处理完毕的两个子序列递归地采取1，2步的操作，直到子序列中只有一个元素。

二.程序各模块的伪代码：1、主函数int main(){int n;cout<<"请输入任务个数：";cin>>n;int a[n];cout<<"请输入任务用时：";for(int i=0;i<n;i++) cin>>a[i];qsort(a,0,n-1); //调用“快排函数”cout<<"任务执行的顺序：";for(int i=0;i<n;i++) cout<<a[i]<<" "; //输出排序结果}2、快速排序算法：void qsort(int a[],int i,int j){if(j<=i)return; //只有一个元素int pivotindex=findpivot(a,i,j); //调用“轴值寻找函数”确定轴值swap(a,pivotindex,j); //调用“交换函数”将轴值置末int k=partition(a,i-1,j,a[j]); //调用“分割函数”根据轴值分割序列swap(a,k,j);qsort(a,i,k-1); //递归调用，实现子序列的调序qsort(a,k+1,j);}3、轴值寻找算法：//为了保证轴值的“随机性”，采用时间初始化种子。

数据结构拓扑排序实验报告数据结构拓扑排序实验报告一、引言本实验报告旨在介绍拓扑排序算法在数据结构中的应用。

拓扑排序是一种用于有向无环图（DAG）的排序算法，它可以将DAG中的节点按照拓扑顺序进行排列，即节点的排列满足所有的有向边都是从排在前面的节点指向排在后面的节点。

拓扑排序在实际生活中有广泛应用，比如任务调度、课程安排等。

二、算法原理拓扑排序的基本原理是通过在DAG中不断删除入度为0的节点，并将这些节点输出，直到所有节点都被输出。

具体步骤如下： 1-统计每个节点的入度。

2-将入度为0的节点加入输出结果中。

3-删除所有以该节点为起点的边，即将它指向的节点的入度减1。

4-重复步骤2和步骤3，直到没有节点的入度为0。

三、实验步骤及结果本实验通过实现拓扑排序算法，对给定的有向图进行拓扑排序，并输出排序结果。

具体步骤如下：1-构建有向图，并初始化每个节点的入度为0。

2-输入有向边的信息，并根据有向边更新每个节点的入度。

3-使用拓扑排序算法对有向图进行排序，并输出排序结果。

4-验证排序结果是否符合要求。

实验结果如下：给定的有向图为：A -> CB -> CB -> DC -> ED -> FE -> F经过拓扑排序算法排序后的结果为：A ->B ->C ->D ->E -> F四、实验分析通过对实验结果的观察和分析发现，拓扑排序算法能够正确地对有向图进行排序。

在本实验中，所有的节点都能够按照拓扑顺序进行排列，说明该有向图是一个有向无环图（DAG）。

五、实验总结通过本次实验，我们深入了解了拓扑排序算法在数据结构中的应用。

拓扑排序算法能够有效地对有向无环图进行排序，广泛应用于任务调度、课程安排等实际问题中。

在实验过程中，我们成功实现了拓扑排序算法，并验证了其正确性和可靠性。

附件：本文档未涉及附件。

法律名词及注释：本文档未涉及法律名词及注释。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本章共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. 快速排序是一种高效的排序算法，适用于各种数据规模。

数据结构排序实验报告1. 引言数据结构是计算机科学中的重要概念，它涉及组织和管理数据的方式。

排序算法是数据结构中的重要部分，它可以将一组无序的数据按照一定的规则进行重新排列，以便更容易进行搜索和查找。

在本实验中，我们将对不同的排序算法进行研究和实验，并对其性能进行评估。

2. 实验目的本实验旨在通过比较不同排序算法的性能，深入了解各算法的特点，从而选择最适合特定场景的排序算法。

3. 实验方法本实验使用C++编程语言实现了以下排序算法：冒泡排序、选择排序、插入排序、快速排序和归并排序。

为了评估这些算法的性能，我们设计了一组实验来测试它们在不同数据规模下的排序时间。

4. 实验过程4.1 数据生成首先，我们生成了一组随机的整数数据作为排序的输入。

数据规模从小到大递增，以便观察不同算法在不同规模下的性能差异。

4.2 排序算法实现接下来，我们根据实验要求，使用C++编程语言实现了冒泡排序、选择排序、插入排序、快速排序和归并排序。

每个算法被实现为一个独立的函数，并按照实验顺序被调用。

4.3 性能评估我们使用计时器函数来测量每个排序算法的执行时间。

在测试过程中，我们多次运行每个算法，取平均值以减小误差。

5. 实验结果我们将在不同数据规模下运行每个排序算法，并记录它们的执行时间。

下表展示了我们的实验结果：数据规模（n）冒泡排序选择排序插入排序快速排序归并排序1000 2ms 3ms 1ms 1ms 1ms5000 20ms 15ms 10ms 3ms 5ms10000 85ms 60ms 30ms 5ms 10ms50000 2150ms 1500ms 700ms 10ms 15ms从上表我们可以观察到，随着数据规模的增加，冒泡排序和选择排序的执行时间呈指数级增长，而插入排序、快速排序和归并排序的执行时间则相对较稳定。

此外，当数据规模较大时，快速排序和归并排序的性能远优于其他排序算法。

6. 实验结论根据实验结果，我们可以得出以下结论：- 冒泡排序和选择排序是简单但效率较低的排序算法，仅适用于较小规模的数据排序。

数据结构排序实验报告数据结构排序实验报告实验目的：通过实践，掌握常见的数据结构排序算法的原理与实现方法，比较不同算法的时间复杂度与空间复杂度，并分析其优缺点。

实验环境：编程语言：Python运行平台：Windows 10实验内容：1. 插入排序 (Insertion Sort)2. 冒泡排序 (Bubble Sort)3. 快速排序 (Quick Sort)4. 选择排序 (Selection Sort)5. 归并排序 (Merge Sort)6. 堆排序 (Heap Sort)实验步骤：1. 实现各种排序算法的函数，并验证其正确性。

2. 构建不同规模的随机数数组作为输入数据。

3. 使用time库测量每种算法在不同规模数据下的运行时间。

4. 绘制时间复杂度与输入规模的关系图。

5. 对比分析各种算法的时间复杂度和空间复杂度。

实验结果：1. 插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

2. 冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

3. 快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)。

4. 选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

5. 归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。

6. 堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。

实验结论：1. 在小规模数据排序时，插入排序和冒泡排序由于其简单性和稳定性可以采用。

2. 在大规模数据排序时，快速排序、归并排序和堆排序由于其较低的时间复杂度可以采用。

3. 选择排序由于其时间复杂度较高，不适合用于大规模数据排序。

4. 归并排序由于其需要额外的空间存储中间结果，空间复杂度较高。

5. 快速排序由于其递归调用栈的使用，时间复杂度虽然较低，但空间复杂度较高。

综上所述，选择排序、插入排序和冒泡排序适用于小规模数据排序，而归并排序、快速排序和堆排序适用于大规模数据排序。

数据结构实验报告排序姓名：13-计算机-舞学号：0000000000专业：计算机科学与技术班级：计算机13-2班日期：2014年6月6日星期五一、实验目的和要求通过编程实现直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序。

要求输入一些无序数，执行程序后使他们变成有序数并在窗口输出。

二、实验环境1、windows 72、c-free 5.0三、实验内容用五种排序算法对输入的数进行排序，并在屏幕中输出。

四、实验过程1、直接插入排序：即将所需要排序的数据分成两部分，其中一部分为已排好序部分，另一部分为未排序部分。

然后从未排序部分中选出一元素插入到一排序部分中，要求插入后已排序部分任然有序。

在编写该程序时，我将要排序的数据储存在一个数组中，并将第一个数划分为已经排序部分然后从下一个数开始不断和前边的最后一个数比较，知道找到插入位置。

2、希尔排序：希尔排序是建立在直接插入排序的基础之上的，他是通过将数据分成几组，在组内实现插入排序，使整个数据基本有序，最后再对整个数据实现插入排序。

这里同样将数据储存在数组中，分组的步长每次取之前步长的一半。

需要注意的是，移动元素时，下标不再是减1，而是减去步长。

3、冒泡排序：通过不断比较相邻的两个元素，发现倒序即交换，最终实现排序。

在这个程序中，我从后面开始向前比较。

每依次循环可以最终确定一个元素在其最终位置上，所以每次循环之后，元素间的两两比较次数减1.4、快速排序：选定一个元素作为中间元素，将整个数据分为比中间元素小的一组和比中间元素大的一组，并且小的在中间元素前，大的在中间元素后。

再分好的两组内再次重复上诉过程使所有元素排好序。

5、直接选择排序：将待排序数据存入数组中，扫描一遍数组，将其中最小的元素找出并放在第一位，再扫描一遍剩下的元素，找到最小的放在第二位。

如此不断重复知道扫描了n-1次。

由于不要再开新空间，所以找到最小元素时用交换的方式使其放在第一位。

比如第一遍扫描，假设第一个为最小元素，再扫描过程中，如果发现比它小的数，则把第一个元素和该位置的元素交换。

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

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

数据结构实验课程最终报告题目：实验八快速排序专业班级：计算机科学与技术姓名：XXＸ学号：指导老师: 李晓鸿完成日期:20１5、01、06一、需求分析背景排序就是计算机内经常进行得一种操作,其目得就是将一组“无序”得记录序列调整为“有序"得记录序列。

假设含n个记录得序列为{R1，R2, …，Rｎ｝其相应得关键字序列为{K１，K2, …,K n｝这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Ｋp1≤K p2≤…≤K pｎ按此固有关系将上式记录序列重新排列为{ R p1，R p2,…，R pn｝得操作称作排序。

排序算法就是计算机科学中最重要得研究问题之一.对于排序得研究既有理论上得重要意义，又有实际应用价值.它在计算机图形、计算机辅助设计、机器人、模式识别、及统计学等领域具有广泛应用。

常见得排序算法有起泡排序、直接插入排序、简单选择排序、快速排序、堆排序等。

例１:有时候应用程序本身就需要对信息进行排序。

为了准备客户账目，银行需要根据支票得号码对支票排序；例2：在一个绘制互相重叠得图形对象得程序中，可能需要根据一个“在上方”关系将各对象排序,以便自下而上地绘出对象。

例3：在一个由n个数构成得集合上,求集合中第i小/大得数。

例4：对一个含有ｎ个元数得集合,求解中位数、k分位数.1.问题描述在操作系统中，我们总就是希望以最短得时间处理完所有得任务。

但事情总就是要一件件地做,任务也要操作系统一件件地处理。

当操作系统处理一件任务时，其她待处理得任务就需要等待。

虽然所有任务得处理时间不能降低,但我们可以安排它们得处理顺序,将耗时少得任务先处理,耗时多得任务后处理，这样就可以使所有任务等待得时间与最小。

只需要将n 件任务按用时去从小到大排序，就可以得到任务依次得处理顺序.当有n 件任务同时来临时，每件任务需要用时nｉ，求让所有任务等待得时间与最小得任务处理顺序.2.程序要求实现得功能当有 n 件任务同时来临时,每件任务需要用时ｎi,求出让所有任务等待得时间与最小得任务处理顺序。

《数据结构》课程设计报告实验五排序一、需求分析：本演示程序用C++6.0编写，完成各种排序的实现，对输入的一组数字实现不同的排序方法，对其由小到大顺序输出。

（1）分别对直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序算法进行编写。

（2）、对存储的函数即输入的数字进行遍历。

（3）、初始化函数对输入的数字进行保存。

（4）、主函数实现使用者操作界面的编写，对输入、选择、保存、输出的各种实现。

这当中还包括了各个函数的调用的实现。

（5）、程序所能达到的功能：完成对输入的数字的生成，并通过对各排序的选择实现数字从小到大的输出。

二、程序主要功能以及基本要求：（1）、设计一个菜单，格式如下：1、直接插入排序2、希尔排序3、冒泡排序4、快速排序5、选择排序6、堆排序7、退出（2）、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。

三、系统框架图：本程序包含了9个函数，它们分别是：（1）、直接插入排序的算法函数InsertSort （）。

（2）、希尔排序的算法函数（3）、冒泡排序算法函数（4）、快速排序的算法函数（5）、选择排序算法函数（6）、堆排序算法函数（7）、对存储数字的遍历函数（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;while ((j >= dk) &&(L.r[j-dk].key > L.r[0].key)){L.r[j].key = L.r[j-dk].key;j -= dk;}L.r[j].key = L.r[0].key;}}}三、冒泡排序void BubbleSort(SqList &L){int i,j;for(i=0;i<L.length-2;i++){int flag = 1;for(j=0;j<L.length-i-2;j++)if(L.r[j].key > L.r[j+1].key){flag = 0;int temp;temp = L.r[j].key;L.r[j].key = L.r[j+1].key;L.r[j+1].key = temp;}//若无交换说明已经有序if(flag==1)break;}}四、快速排序int Partition(SqList &L,int low,int high){//分割区域函数L.r[0] = L.r[low];int pivotkey = L.r[low].key;//一般将顺序表第一个元素作为支点while(low < high){while(low<high &&L.r[high].key>=pivotkey)high--;L.r[low] = L.r[high];while(low<high &&L.r[low].key<=pivotkey)low++;L.r[high] = L.r[low];}L.r[low] = L.r[0];//返回枢轴位置return low;}void QSort(SqList &L,int low,int high){//每张子表的快速排序if(low<high){int pivotloc =Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}}void QuickSort(SqList &L){QSort(L,1,L.length);}五、简单选择排序void SelectSort(SqList &L){int min;int j;for (int i = 0; i <L.length; i++){ // 选择第i小的记录，并交换j = i;min = L.r[i].key;for (int k = i; k < L.length; k++){ // 在R[i..n-1]中选择最小的记if (L.r[k].key < min){min = L.r[k].key ;j = k;}}if (i != j){ // 与第i个记录交换int temp = L.r[i].key;L.r[i].key = L.r[j].key;L.r[j].key = temp;}}}六、堆排序void HeapAdjust(HeapType &H,int s,int m){//堆调整，将记录调整为小顶堆int j;RedType rc = H.r[s];//暂时存储根结for(j=2*s; j<=m; j*=2){//沿着结点记录较小的向下筛选if(j<m &&H.r[j].key<H.r[j+1].key)++j;if(rc.key>= H.r[j].key)break;H.r[s] = H.r[j];s = j;}H.r[s] = rc;}void HeapSort(HeapType &H){int i;RedType temp;for(i = H.length; i>0; --i)HeapAdjust(H,i,H.length);for(i=H.length; i>1; --i){temp = H.r[1];H.r[1] = H.r[i];H.r[i] = temp;HeapAdjust(H,1,i-1);}}（2）遍历函数与初始化void Visit(SqList L){for(int i=1; i<=L.length; i++)cout<<L.r[i].key<<" ";cout<<endl;}void InitSqList(SqList &L,int a[]){for(int i=1;i<=L.length;i++)L.r[i].key = a[i];}五、测试结果以下是各种界面的测试结果：（1）输入的界面:（2）排序操作界面：（3）各种排序的结果：六、设计不足以及存在问题本程序是基于C++6.0的实现，其实在设计上的改进可以利用类进行操作，这种类的改进了存储上的不足还可以实现了，对各种的函数基于类的实现，这就是对本程序的改进，这是十分重要的与是改进的基础。

数据结构实验报告实验名称：排序学号：姓名：实验日期：2016.07.01一、实验目的至少掌握一种排序算法二、实验内容随机生成10个从1－100之间的随机数，编程实现至少一种排序算法，对该数据进行排序。

要求1、要排序的数据随机生成2、先升序排序一次，再用同样的算法降序排序一次（2）分析（3）实验代码#include <stdio.h>#include <stdlib.h>#include <time.h>typedef struct{int key;}keytype;typedef struct{ keytype r[1000];int length;}sqlist;/*产生随机数*/void creat(sqlist *l){int i;printf("请输入要产生的随机数个数:");scanf("%d",&l->length);srand((unsigned)time(NULL));for(i=1;i<=l->length;i++){l->r[i].key = rand() %900+100;printf("%d ",l->r[i].key);}printf("\n");}/*交换顺序表中子表r[low...high]的记录，使枢轴记录到位，并返回其所在的位置*/int partion(sqlist *l,int low,int high){ int pivotkey;l->r[0]=l->r[low];pivotkey=l->r[low].key;while(low<high){ while(low<high&&l->r[high].key>=pivotkey) --high;l->r[low]=l->r[high];while(low<high&&l->r[low].key<=pivotkey) ++low;l->r[high]=l->r[low];}l->r[low]=l->r[0];return low;}/*快速排序*/void Qsort(sqlist *l,int low,int high){ int pivotloc;if(low<high){ pivotloc=partion(l,low,high);Qsort(l,low,pivotloc-1);Qsort(l,pivotloc+1,high);}}/*显示顺序表*/void display(sqlist *l){ int i;for(i=1;i<=l->length;i++)printf("%-4.2d",i);printf("\n");for(i=1;i<=2*l->length;i++)printf("--");printf("\n");for(i=1;i<=l->length;i++)printf("%-4.2d",l->r[i].key);}/*主函数*/void main(){sqlist t;creat(&t);Qsort(&t,1,t.length);printf("\n\n");printf("快速排序:\n");display(&t);}三、实验小结。

数据结构实验报告排序数据结构实验报告：排序引言：排序是计算机科学中常见的算法问题之一，它的目标是将一组无序的数据按照特定的规则进行排列，以便于后续的查找、统计和分析。

在本次实验中，我们将学习和实现几种常见的排序算法，并对它们的性能进行比较和分析。

一、冒泡排序冒泡排序是最简单的排序算法之一，它通过不断交换相邻的元素，将较大（或较小）的元素逐渐“冒泡”到数组的一端。

具体实现时，我们可以使用两层循环来比较和交换元素，直到整个数组有序。

二、插入排序插入排序的思想是将数组分为两个部分：已排序部分和未排序部分。

每次从未排序部分中取出一个元素，插入到已排序部分的适当位置，以保持已排序部分的有序性。

插入排序的实现可以使用一层循环和适当的元素交换。

三、选择排序选择排序每次从未排序部分中选择最小（或最大）的元素，与未排序部分的第一个元素进行交换。

通过不断选择最小（或最大）的元素，将其放置到已排序部分的末尾，从而逐渐形成有序序列。

四、快速排序快速排序是一种分治的排序算法，它通过选择一个基准元素，将数组划分为两个子数组，其中一个子数组的所有元素都小于等于基准元素，另一个子数组的所有元素都大于基准元素。

然后对两个子数组分别递归地进行快速排序，最终将整个数组排序。

五、归并排序归并排序也是一种分治的排序算法，它将数组划分为多个子数组，对每个子数组进行排序，然后再将排好序的子数组合并成一个有序的数组。

归并排序的实现可以使用递归或迭代的方式。

六、性能比较与分析在本次实验中，我们对以上几种排序算法进行了实现，并通过对不同规模的随机数组进行排序，比较了它们的性能。

我们使用了计算排序时间的方式，并记录了每种算法在不同规模下的运行时间。

通过对比实验结果，我们可以得出以下结论：1. 冒泡排序和插入排序在处理小规模数据时表现较好，但在处理大规模数据时性能较差，因为它们的时间复杂度为O(n^2)。

2. 选择排序的时间复杂度也为O(n^2)，与冒泡排序和插入排序相似，但相对而言，选择排序的性能稍好一些。

《数据结构》课程设计报告专业班级姓名学号指导教师起止时间课程设计：排序综合一、任务描述利用随机函数产生n个随机整数（20000以上），对这些数进行多种方法进行排序。

（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。

并把排序后的结果保存在不同的文件中。

（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

要求：根据以上任务说明，设计程序完成功能。

二、问题分析1、功能分析分析设计课题的要求，要求编程实现以下功能：（1）随机生成N个整数，存放到线性表中；（2）起泡排序并计算所需时间；（3）简单选择排序并计算时间；（4）希尔排序并计算时间；（5）直接插入排序并计算所需时间；（6）时间效率比较。

2、数据对象分析存储数据的线性表应为顺序存储。

三、数据结构设计使用顺序表实现，有关定义如下：typedef int Status;typedef int KeyType ; //设排序码为整型量typedef int InfoType;typedef struct { //定义被排序记录结构类型KeyType key ; //排序码I nfoType otherinfo; //其它数据项} RedType ;typedef struct {RedType * r; //存储带排序记录的顺序表//r[0]作哨兵或缓冲区int length ; //顺序表的长度} SqList ; //定义顺序表类型四、功能设计（一）主控菜单设计为实现通各种排序的功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。

程序运行后，给出5个菜单项的容和输入提示，如下：1.起泡排序2.简单选择排序3.希尔排序4. 直接插入排序0. 退出系统（二）程序模块结构由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）：●主控菜单项选择函数menu()●创建排序表函数InitList_Sq()●起泡排序函数Bubble_sort()●简单选择排序函数SelectSort()●希尔排序函数ShellSort();●对顺序表L进行直接插入排序函数Insertsort()（三）函数调用关系程序的主要结构（函数调用关系）如下图所示。

《数据结构》课程设计报告专业班级姓名学号指导教师起止时间课程设计：排序综合一、任务描述利用随机函数产生n个随机整数（20000以上），对这些数进行多种方法进行排序。

（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。

并把排序后的结果保存在不同的文件中。

（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

要求：根据以上任务说明，设计程序完成功能。

二、问题分析1、功能分析分析设计课题的要求，要求编程实现以下功能：（1）随机生成N个整数，存放到线性表中；（2）起泡排序并计算所需时间；（3）简单选择排序并计算时间；（4）希尔排序并计算时间；（5）直接插入排序并计算所需时间；（6）时间效率比较。

2、数据对象分析存储数据的线性表应为顺序存储。

三、数据结构设计使用顺序表实现，有关定义如下：typedef int Status;typedef int KeyType ; 直接插入排序0. 退出系统（二）程序模块结构由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）：主控菜单项选择函数menu()创建排序表函数InitList_Sq()起泡排序函数Bubble_sort()简单选择排序函数SelectSort()希尔排序函数ShellSort();对顺序表L进行直接插入排序函数Insertsort()（三）函数调用关系程序的主要结构（函数调用关系）如下图所示。

其中main()是主函数，它负责调用各函数。

进行调用菜单函数menu()，根据选择项0~4调用相应的函数。

main()函数使for循环实现重复选择。

其循环结构如下：for (;;){long start,end;switch(menu()){case 1:printf("* 起泡排序*\n");start=clock();Bubble_sort(L);end=clock();printf("%d ms\n",end-start);fp=fopen("D: 起泡排序.txt","w");if(fp==NULL)xt","w");if(fp==NULL)xt","w");if(fp==NULL)Ney,[j].key)){flag=1; 共通过n－1趟,得到一个按排序码从小到大排列的有序序列流程图：NN代码描述：void SelectSort(SqList &L){ ] 中选择key最小的记录int k=i;for(int j=i+1;j<= ; j++)if ( LT[j].key,[k].key)) k=j;if(k!=i){x=[i];[i]=[j];[j]=x;}}} ey , [i-dk].key )){[0]= [i];int j;for(j=i-dk;(j>0)&&(LT [0].key , [j].key ));j-=dk)[j+dk]= [j];[j+dk]= [0];}}}void ShellSort(SqList &L,int dlta[],int t)NNey,[i-1].key)) ey,[j].key);j--){[j+1]=[j];ey的元素[j+1]=[0]; //将暂存在r[0]中的记录插入到正确位置}// printf("%d ",[i]);}算法的时间复杂度分析：O（n2）五、测试数据和结果1、测试数据随机产生30000个数2、测试结果本程序在VC++环境下实现，下面是对以上测试数据的运行结果。

引言概述：数据结构排序实验是计算机科学与技术专业中一项重要的实践课程。

通过实验，可以深入理解和掌握不同排序算法的原理、特点和性能表现。

本文将针对数据结构排序实验进行详细的阐述和总结，包括实验目的、实验内容、实验结果分析和总结。

一、实验目的1. 加深对数据结构排序算法的理解：通过实验，掌握不同排序算法的工作原理和实现方式。

2. 分析和比较不同排序算法的性能：对比不同排序算法在不同数据规模下的时间复杂度和空间复杂度，理解它们的优劣势。

3. 提高编程和算法设计能力：通过实验的编写，提升对排序算法的实现能力和代码质量。

二、实验内容1. 选择排序算法：选择排序是一种简单直观的排序算法，将序列分为有序和无序两部分，每次从无序部分选择最小（最大）元素，放到有序部分的末尾（开头）。

- 算法原理及步骤- 实现过程中的注意事项- 时间复杂度和空间复杂度的分析2. 插入排序算法：插入排序逐步构建有序序列，对于未排序的元素，在已排序序列中从后向前扫描，找到对应位置插入。

- 算法原理及步骤- 实现过程中的注意事项- 时间复杂度和空间复杂度的分析3. 快速排序算法：快速排序利用分治的思想，将序列分为左右两部分，选取基准元素，将小于基准的放在左边，大于基准的放在右边，递归地对左右部分进行排序。

- 算法原理及步骤- 实现过程中的注意事项- 时间复杂度和空间复杂度的分析4. 归并排序算法：归并排序是一种稳定的排序算法，通过将序列分为若干子序列，分别进行排序，然后再将排好序的子序列合并成整体有序序列。

- 算法原理及步骤- 实现过程中的注意事项- 时间复杂度和空间复杂度的分析5. 堆排序算法：堆是一种特殊的树状数据结构，堆排序利用堆的性质进行排序，通过构建大顶堆或小顶堆，并逐个将堆顶元素移出形成有序序列。

- 算法原理及步骤- 实现过程中的注意事项- 时间复杂度和空间复杂度的分析三、实验结果分析1. 比较不同排序算法的执行时间：根据实验数据和分析，对比不同排序算法在不同数据规模下的执行时间，并针对其时间复杂度进行验证和分析。

数据结构课程设计实验报告1、需求分析(1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；(2)待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字进行一次交换操作记为3次移动）；(3)输出比较结果。

2、主要函数及数据类型typedef int KeyType; //定义关键字类型为整数类型typedef int InfoType; //定义关键字类型为整数类型typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等*/typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */typedef struct{KeyType key; //关键字项InfoType otherinfo; //其它数据项}RedType; //记录类型typedef struct {RedType r[MAXSIZE+1]; //r[0]闲置或用作哨兵单元int length; //顺序表长度}SqList; //顺序表类型3、源代码/*头文件和宏定义部分*/#include"string.h"#include"ctype.h"#include"time.h"#include"malloc.h" /* malloc()等*/#include"limits.h" /* INT_MAX等*/#include"stdio.h" /* EOF(=^Z或F6),NULL */#include"stdlib.h" /* atoi() */#include"io.h" /* eof() */#include"math.h" /* floor(),ceil(),abs() */#include"process.h" /* exit() *//* 函数结果状态代码*/#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define MAXSIZE 100 //示例数据类型的最大长度typedef int KeyType; //定义关键字类型为整数类型typedef int InfoType; //定义关键字类型为整数类型typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等*/ typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */typedef struct{KeyType key; //关键字项InfoType otherinfo; //其它数据项}RedType; //记录类型typedef struct {RedType r[MAXSIZE+1]; //r[0]闲置或用作哨兵单元int length; //顺序表长度}SqList; //顺序表类型void InitData(SqList *L,int dataCopy[]){int i;L->length=MAXSIZE;srand((unsigned)time(NULL));for(i=0;i<=MAXSIZE;i++){L->r[i].otherinfo=0;dataCopy[i]=L->r[i].key=rand();}}void PrintData(SqList L){int i;for(i=1;i<=L.length;i++){printf("%d\t",L.r[i].key);}}void ResumeData(SqList *L,int dataCopy[]){int i;for(i=0;i<=MAXSIZE;i++){L->r[i].key=dataCopy[i];}}void PrintStatistic(int *compareCounts,int *moveCounts){printf("\n\t\t各种排序方法比较结果:\n\n");printf("\t\t起泡排序: 比较次数%d,移动次数%d\n",compareCounts[0],moveCounts[0]);printf("\t\t直接插入排序:比较次数%d,移动次数%d\n",compareCounts[1],moveCounts[1]);printf("\t\t简单选择排序:比较次数%d,移动次数%d\n",compareCounts[2],moveCounts[2]);printf("\t\t快速排序: 比较次数%d,移动次数%d\n",compareCounts[3],moveCounts[3]);printf("\t\t希尔排序: 比较次数%d,移动次数%d\n",compareCounts[4],moveCounts[4]);printf("\t\t堆排序: 比较次数%d,移动次数%d\n",compareCounts[5],moveCounts[5]);}/*******************************直接插入排序*******************************/void InsertSort(SqList *L,int *compareCounts,int *moveCounts ) //直接插入排序{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];(*moveCounts)+=2; //关键字移动了2次j=i-2; //从要比较的关键字的前第二个记录开始进行比较,然后后移while(L->r[0].key<L->r[j].key){L->r[j+1]=L->r[j]; //记录后移(*moveCounts)++; //每作一次后移,移动次数加1j--;(*compareCounts)++; //每作一次比较，比较次数加1}L->r[j+1]=L->r[0]; //插入到正确位置}(*compareCounts)++;}}/*******************************希尔排序*******************************/void ShellInsert(SqList *L,int increment,int *compareCounts,int *moveCounts){ //对顺序表作一趟希尔插入排序int j,n;for(j=1+increment;j<=L->length;j++){if(L->r[j].key<L->r[j-increment].key) //将L->[i]插入到有序增量子表{L->r[0]=L->r[j]; //暂存在L->r[0]L->r[j]=L->r[j-increment];(*moveCounts)+=2;for(n=j-2*increment;n>0&&L->r[0].key<L->r[n].key;n-=increment){L->r[n+increment]=L->r[n]; //记录后移，查找插入位置(*moveCounts)++;(*compareCounts)++;}L->r[n+increment]=L->r[0]; //插入(*moveCounts)++;}(*compareCounts)++;}}void ShellSort(SqList *L,int IncreList[],int times,int *compareCounts,int *moveCounts) //希尔排序{ //按增量序列Increlist［0.....times-1］对顺序表Ｌ作希尔排序int k; //for(k=0;k<times;k++){ShellInsert(L,IncreList[k],compareCounts,moveCounts); //一趟增量为IncreList[k]的插入排序}}/*******************************起泡排序*******************************/void BubbleSort(SqList *L,int *compareCounts,int *moveCounts) //起泡排序{int i,j;for(i=1;i<=L->length;i++){for(j=L->length;j>i;j--){ //从后往前两两进行比较，将元素关键字小的交换到前面if(L->r[j].key<L->r[j-1].key){L->r[0]=L->r[j];L->r[j]=L->r[j-1];L->r[j-1]=L->r[0];(*moveCounts)+=3;}(*compareCounts)++;}}}/*******************************快速排序*******************************/int Partition(SqList *L,int low,int high,int *compareCounts,int *moveCounts) //快速排序中的分{int pivotkey;L->r[0]=L->r[low];(*moveCounts)++;pivotkey=L->r[low].key;while(low<high){while(low<high&&L->r[high].key>=pivotkey){high--;(*compareCounts)++;}L->r[low]=L->r[high];(*moveCounts)++;while(low<high&&L->r[low].key<=pivotkey){low++;(*compareCounts)++;}L->r[high]=L->r[low];(*moveCounts)++;(*compareCounts)++;}L->r[low]=L->r[0];(*moveCounts)++;return low;}void QSort(SqList *L,int low,int high,int *compareCounts,int *moveCounts){int pivotloc;if(low<high){pivotloc=Partition(L,low,high,compareCounts,moveCounts);QSort(L,low,pivotloc-1,compareCounts,moveCounts);QSort(L,pivotloc+1,high,compareCounts,moveCounts);}}void QuickSort(SqList *L,int *compareCounts,int *moveCounts){QSort(L,1,L->length,compareCounts,moveCounts);}/*******************************简单选择排序*******************************/void SelectSort(SqList *L,int *compareCounts,int *moveCounts){int i,j,minPoint;for(i=1;i<=L->length;i++){L->r[0]=L->r[i];(*moveCounts)++;minPoint=i;for(j=i+1;j<=L->length;j++){if(L->r[j].key<L->r[0].key){L->r[0]=L->r[j];(*moveCounts)++;minPoint=j;}(*compareCounts)++;}L->r[minPoint]=L->r[i];L->r[i]=L->r[0];(*moveCounts)++;}}/*******************************堆排序*******************************/void HeapAdjust(SqList *L,int s,int m,int *compareCounts,int *moveCounts){RedType cmpKey; //待比较的值int j;cmpKey=L->r[s];(*moveCounts)++;for(j=s*2;j<=m;j*=2){(*compareCounts)+=2;if(j<m&&L->r[j].key<L->r[j+1].key) j++;if(!(cmpKey.key<L->r[j].key)) break;L->r[s]=L->r[j];(*moveCounts)++;s=j;}L->r[s]=cmpKey;(*moveCounts)++;}void HeapSort(SqList *L,int *compareCounts,int *moveCounts){int i;RedType temp;for(i=L->length/2;i>0;i--) HeapAdjust(L,i,L->length,compareCounts,moveCounts);for(i=L->length;i>1;i--){temp=L->r[1];L->r[1]=L->r[i];L->r[i]=temp;(*moveCounts)+=3;HeapAdjust(L,1,i-1,compareCounts,moveCounts);}}void SortCompare(){SqList L; //用顺序表存放待排序的元素int dataCopy[MAXSIZE+1],i;int compareCounts[7],moveCounts[7];int increList[6];for(i=0;i<5;i++){increList[i]=(int)pow(2,7-i)-1;}increList[5]=1;for(i=0;i<7;i++){compareCounts[i]=0;moveCounts[i]=0;}InitData(&L,dataCopy); //初始化数据，随机产生100个正整数的数列printf("\t\t\t初始化数据后产生的数列:\n");PrintData(L); //显示出未排序的数列printf("\n\n\t\t\t经过起泡排序后产生的数列:\n");BubbleSort(&L,&compareCounts[0],&moveCounts[0]); //对数列使用起泡排序PrintData(L); //显示出排序好的数列ResumeData(&L,dataCopy);printf("\n\n\t\t\t经过直接插入排序后产生的数列:\n");InsertSort(&L,&compareCounts[1],&moveCounts[1]); //对数列使用插入排序PrintData(L); //显示出排序好的数列ResumeData(&L,dataCopy);printf("\n\n\t\t\t经过简单选择排序后产生的数列:\n");SelectSort(&L,&compareCounts[2],&moveCounts[2]); //对数列使用简单选择排序PrintData(L); //显示出排序好的数列ResumeData(&L,dataCopy);printf("\n\n\t\t\t经过快速排序后产生的数列:\n");QuickSort(&L,&compareCounts[3],&moveCounts[3]); //对数列使用快速排序PrintData(L); //显示出排序好的数列ResumeData(&L,dataCopy);printf("\n\n\t\t\t经过希尔排序后产生的数列:\n");ShellSort(&L,increList,6,&compareCounts[4],&moveCounts[4]); //对数列使用希尔排序PrintData(L); //显示出排序好的数列ResumeData(&L,dataCopy);printf("\n\n\t\t\t经过堆排序后产生的数列:\n");HeapSort(&L,&compareCounts[5],&moveCounts[5]); //对数列使用堆排序PrintData(L); //显示出排序好的数列PrintStatistic(compareCounts,moveCounts);}main(){int i,temp;for(i=0;i<5;i++){SortCompare();printf("\n\t\t请按任意键进行下一组数据的排序对比\n\n");temp=getchar();}}4、调试分析成功运行，如图所示：。

数据结构排序实验报告一、实验目的本次数据结构排序实验的主要目的是深入理解和掌握常见的排序算法，包括冒泡排序、插入排序、选择排序、快速排序和归并排序，并通过实际编程和实验分析，比较它们在不同规模数据下的性能表现，从而为实际应用中选择合适的排序算法提供依据。

二、实验环境本次实验使用的编程语言为 Python 3x，开发环境为 PyCharm。

实验中使用的操作系统为 Windows 10。

三、实验原理1、冒泡排序（Bubble Sort）冒泡排序是一种简单的排序算法。

它重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。

2、插入排序（Insertion Sort）插入排序是一种简单直观的排序算法。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到整个数组有序。

3、选择排序（Selection Sort）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

以此类推，直到所有元素均排序完毕。

4、快速排序（Quick Sort）通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

5、归并排序（Merge Sort）归并排序是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法(Divide and Conquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

四、实验步骤1、算法实现使用 Python 语言分别实现上述五种排序算法。

为每个算法编写独立的函数，函数输入为待排序的列表，输出为排序后的列表。

2、生成测试数据生成不同规模（例如 100、500、1000、5000、10000 个元素）的随机整数列表作为测试数据。