下载文档原格式
实验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、轴值寻找算法：//为了保证轴值的“随机性”，采用时间初始化种子。
安徽工程大学高级语言程序设计实验报告班级姓名同组者/ 成绩日期2019.09.30 指导教师实验名称顺序结构程序设计一、实验目的1.掌握数据的输入/输出方法，能正确使用有关格式转换符。
2.掌握顺序结构程序中语句的执行过程。
3.掌握顺序结构程序的设计方法。
二、实验内容1.P47页第一个程序的作用是依次输入2个整数，计算并输出这2个整数之差。
（1）分析程序，若运行时输出：200,160<回车>，预期结果是多少？（2）上机运行该程序，查看程序运行结果是否符合题目要求。
如果不符合，请分析原因并修改程序，直至符合要求为止。
2.P47页第二个程序用于实现按下列公式计算并输出s1和s2的值：s1=3/(a+b)2,s2=ab/(a+b)3,其中a,b为整型数据。
（1）根据题意修改上述程序，并进行调试，直到正确为止。
（2）在（1）的基础上，将“scanf("%d,%d",&a,&b);”改为“scanf("%d%d",&a,&b);”后再编译、连接、运行。
3.分析P47页第三个程序，写出预期结果，然后输入调试，查看运行结果与预期结果是否一致，并分析其原因。
4.编程实现下列功能并上机调试运行。
（1）设圆半径为r，求圆周长和面积。
要求用scanf函数输入数据，输出时取小数点后两位。
（2）输入一个3位十进制整数，分别输出百位、十位以及个位上的数。
（3）从键盘输入一个带两位小数的实数，将其整数部分和小数部分分离后输出。
（4）用getchar函数读入两个字符，然后分别用putchar和printf函数输出这两个字符。
*思考题：5. 若实验内容1的程序改为P48页第一个程序段，运行该程序，输入5,3，查看程序运行结果是否与自己预测的结果一致，并分析原因。
6.若实验内容1的程序改为P48页第二个程序段，运行该程序，输入5,3，查看程序运行结果是否与自己预测的结果一致，并分析原因。
一、实验目的1. 理解起泡排序算法的基本原理和操作步骤。
2. 掌握C语言中实现起泡排序算法的方法。
3. 通过实验，比较起泡排序算法的优缺点，分析其在不同场景下的适用性。
二、实验环境1. 操作系统：Windows 102. 编程语言：C语言3. 编译器：Visual Studio 2019三、实验原理起泡排序是一种简单的排序算法，它通过重复遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
遍历数列的工作是重复进行的，直到没有再需要交换，也就是说该数列已经排序完成。
起泡排序的步骤如下：1. 比较相邻的元素。
如果第一个比第二个大（升序排序），就交换它们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。
这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 重复步骤1~3，直到排序完成。
四、实验内容1. 设计一个函数，使用起泡排序算法对输入的10个字符按由小到大顺序排列。
2. 编写主函数，从用户那里获取10个字符，调用排序函数，并输出排序后的结果。
五、实验步骤1. 创建一个新的C语言项目，并添加一个名为`BubbleSort.c`的源文件。
2. 在`BubbleSort.c`文件中，定义一个名为`bubbleSort`的函数，该函数接受一个字符数组和数组的长度作为参数。
3. 在`bubbleSort`函数中，使用两层嵌套循环实现起泡排序算法。
4. 在主函数中，定义一个长度为10的字符数组，并从用户那里获取10个字符。
5. 调用`bubbleSort`函数，对字符数组进行排序。
6. 输出排序后的字符数组。
六、实验代码```c#include <stdio.h>void bubbleSort(char arr[], int n) {int i, j;char temp;for (i = 0; i < n - 1; i++) {for (j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}int main() {char arr[10];printf("请输入10个字符：\n");for (int i = 0; i < 10; i++) {scanf("%c", &arr[i]);}bubbleSort(arr, 10);printf("排序后的字符为：\n");for (int i = 0; i < 10; i++) {printf("%c ", arr[i]);}printf("\n");return 0;}```七、实验结果与分析1. 运行程序，按照提示输入10个字符，程序将输出排序后的字符数组。
《数据结构与算法》综合实验报告系别：专业：学生姓名：指导教师：2011年 11月 25日实验目的掌握线性表的建立、插入、删除算法；掌握查找算法；掌握排序算法；实验要求使用C语言（环境任意）开发程序，能够对用户输入的任意一组数据，建立一个线性表，可以输出此线性表。
并且能够对此线性表进行插入、删除、查找、排序等操作。
程序流程建表如下：定义一个整型的数据类型data和next指针：定义头指针和当前结点指针，申请连续空间将单个字节大小复制给头指针，把头指针赋值给当前节点指针：若输入的数是0，则若输入不为0，把输入的数赋值给已申请的新结点，把新结点赋给当前节点的next域，再把新结点赋值给当前结点，以此方法重复执行得到如下链表：输出函数：把头指针赋值给当前结点指针，当当前节点的next域不为空时输出当前节点所指向的数据，把当前结点的next域赋值给当前节点，否则输出链表为空对此线性表进行插入、删除、查询、排序操作把已申请的结点数据域指向所输入的数再把插入w结点赋值头结点，是插入的位置，如果w=0则插入结点的next域赋值给头结点否则如果w>表长，则输出超出范围代码及运行结果（主要语句要求有注释）#include"stdafx.h"#include<stdio.h>#include<malloc.h>#define NULL 0typedef struct linknode{int data;struct linknode *next;}node;node *head;node *creat(){node *currnode,*newnode;int x;head=(node*)malloc(sizeof(node));currnode=head;do{scanf("%d",&x);newnode=(node*)malloc(sizeof(node));newnode->data=x;currnode->next=newnode;currnode=newnode;}while(x!=NULL);head=head->next;currnode->next=NULL;return head;};int length(){node *currnode;int i=0;currnode=head;while(currnode->data!=NULL){currnode=currnode->next;i++;};return i;};void print(){node *currnode;currnode=head;printf("链表如下....linklist");while(currnode->data!=NULL){printf("%d-->",currnode->data);currnode=currnode->next;};printf("NULL\n");printf("链表长度为........linklist length%d\n",length());};void delete1(){int x;node *delnode,*currnode;printf("输入要删除的数据......input delete data：");scanf("%d",&x);if(head->data==NULL) printf("此链表为空无法删除.....this linklist empty！\n"); if(head->data==x){delnode=head;head=head->next;free(delnode);if(head==NULL) printf("此链表为空.......this linklist enpty！");}else{currnode=head;delnode=currnode->next;while(delnode->data!=x&&delnode!=NULL){currnode=currnode->next;delnode=currnode->next;};if(delnode==NULL)printf("无此数据......no this data！\n");else{currnode->next=delnode->next;free(delnode);};};};void find(){node *currnode;int count=1,x;currnode=head;printf("输入要查找的数据.......input search data:");scanf("%d",&x);while(currnode->data!=NULL&&currnode->data!=x) {currnode=currnode->next;count++;};if(currnode->data!=NULL){printf("\n%d为第........is no.",currnode->data);printf("%d个数据........data。
C语⾔⼋⼤排序算法C语⾔⼋⼤排序算法，附动图和详细代码解释！来源：C语⾔与程序设计、⽵⾬听闲等⼀前⾔如果说各种编程语⾔是程序员的招式，那么数据结构和算法就相当于程序员的内功。
想写出精炼、优秀的代码，不通过不断的锤炼，是很难做到的。
⼆⼋⼤排序算法排序算法作为数据结构的重要部分，系统地学习⼀下是很有必要的。
1、排序的概念排序是计算机内经常进⾏的⼀种操作，其⽬的是将⼀组“⽆序”的记录序列调整为“有序”的记录序列。
排序分为内部排序和外部排序。
若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。
反之，若参加排序的记录数量很⼤，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。
2、排序分类⼋⼤排序算法均属于内部排序。
如果按照策略来分类，⼤致可分为：交换排序、插⼊排序、选择排序、归并排序和基数排序。
如下图所⽰：3、算法分析1.插⼊排序*直接插⼊排序*希尔排序2.选择排序*简单选择排序*堆排序3.交换排序*冒泡排序*快速排序4.归并排序5.基数排序不稳定排序：简单选择排序，快速排序，希尔排序，堆排序稳定排序：冒泡排序，直接插⼊排序，归并排序，奇数排序1、插⼊排序将第⼀个和第⼆个元素排好序，然后将第3个元素插⼊到已经排好序的元素中，依次类推（插⼊排序最好的情况就是数组已经有序了）因为插⼊排序每次只能操作⼀个元素，效率低。
元素个数N，取奇数k=N/2，将下标差值为k的数分为⼀组（⼀组元素个数看总元素个数决定），在组内构成有序序列，再取k=k/2，将下标差值为k的数分为⼀组，构成有序序列，直到k=1，然后再进⾏直接插⼊排序。
3、简单选择排序选出最⼩的数和第⼀个数交换，再在剩余的数中⼜选择最⼩的和第⼆个数交换，依次类推4、堆排序以升序排序为例，利⽤⼩根堆的性质（堆顶元素最⼩）不断输出最⼩元素，直到堆中没有元素1.构建⼩根堆2.输出堆顶元素3.将堆低元素放⼀个到堆顶，再重新构造成⼩根堆，再输出堆顶元素，以此类推5、冒泡排序改进1：如果某次冒泡不存在数据交换，则说明已经排序好了，可以直接退出排序改进2：头尾进⾏冒泡，每次把最⼤的沉底，最⼩的浮上去，两边往中间靠16、快速排序选择⼀个基准元素，⽐基准元素⼩的放基准元素的前⾯，⽐基准元素⼤的放基准元素的后⾯，这种动作叫分区，每次分区都把⼀个数列分成了两部分，每次分区都使得⼀个数字有序，然后将基准元素前⾯部分和后⾯部分继续分区，⼀直分区直到分区的区间中只有⼀个元素的时候，⼀个元素的序列肯定是有序的嘛，所以最后⼀个升序的序列就完成啦。
c语言数组数据比较算法概述在C语言中，数组是一种常见的数据结构，用于存储一系列相同数据类型的元素。
在实际编程中，经常需要对数组进行比较操作，以找到数组中的最大值、最小值、排序等。
本文将详细介绍C语言中常用的数组数据比较算法。
一、数组元素比较1.1 逐个元素比较法逐个元素比较法是最简单的数组比较方法，其基本思想是将两个数组中的对应元素逐个进行比较，找出差异或相同之处。
具体步骤如下：1.声明两个数组a和b；2.逐个比较数组a和数组b的对应元素；3.如果找到不同的元素，输出差异；4.如果所有对应元素都相同，则输出相同。
1.2 利用循环遍历比较法逐个元素比较法虽然简单，但需要逐个比较所有元素，效率较低。
利用循环遍历比较法可以通过循环结构实现更高效的数组比较。
具体步骤如下： 1. 声明两个数组a和b； 2. 使用循环结构遍历数组a和数组b的对应元素； 3. 逐个比较数组a 和数组b的对应元素； 4. 如果找到不同的元素，输出差异； 5. 如果所有对应元素都相同，则输出相同。
二、数组排序算法2.1 冒泡排序法冒泡排序是一种简单的排序算法，其基本思想是多次遍历数组，每次遍历都将相邻的两个元素进行比较并交换位置，从而实现将最大（或最小）元素逐渐移到数组的末尾（或开头）。
具体步骤如下： 1. 声明一个数组a； 2. 外层循环遍历数组元素，从第一个元素到倒数第二个元素； 3. 内层循环遍历数组元素，从第一个元素到当前外层循环变量所指示的位置； 4. 逐个比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置； 5. 继续下一轮的遍历，直到所有元素排序完成。
2.2 插入排序法插入排序是一种简单直观的排序算法，其基本思想是将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的适当位置。
具体步骤如下： 1. 声明一个数组a； 2. 外层循环遍历数组元素，从第二个元素到最后一个元素； 3. 内层循环从外层循环变量所指示的位置开始，向前逐个比较并移动已排序部分的元素； 4. 当找到合适位置时，插入当前未排序元素； 5. 继续下一轮的遍历，直到所有元素排序完成。
c语言数组排序由大到小C语言数组排序由大到小在C语言中，数组是一种非常常见且重要的数据结构，用于存储一系列相同类型的数据。
而对数组进行排序操作是程序设计中的常见需求之一。
本篇文章将介绍如何使用C语言对数组进行排序，具体而言是由大到小的排序。
排序是将一组数据按照一定的规则重新排列的过程，可以按照升序或降序的方式进行。
而本文将以降序排序为例，即将数组中的元素从大到小进行排列。
我们需要了解一下C语言中的排序算法。
常见的排序算法有冒泡排序、选择排序、插入排序、快速排序等。
在这里，我们将使用冒泡排序算法对数组进行降序排序。
冒泡排序是一种简单直观的比较交换排序算法。
其基本思想是通过相邻元素的比较和交换，将较大的元素逐渐“冒泡”到数组的末尾。
具体实现如下：```cvoid bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - 1 - i; j++) {if (arr[j] < arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}```以上是冒泡排序算法的C语言实现。
其中，arr为待排序的数组，n 为数组的长度。
通过嵌套的for循环，依次比较相邻的两个元素，如果前者大于后者，则进行交换。
通过多次遍历，将最大的元素逐渐交换到数组的末尾，从而实现降序排序。
接下来，我们可以编写一个简单的程序来测试这个排序算法。
```c#include <stdio.h>void bubbleSort(int arr[], int n);int main() {int arr[] = {9, 5, 7, 3, 1};int n = sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, n);printf("排序后的数组：");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;}```在这个程序中，我们首先定义了一个包含5个整数的数组arr，并计算了数组的长度n。
数据结构实验八快速排序实验报告一、实验目的1.掌握快速排序算法的原理。
2. 掌握在不同情况下快速排序的时间复杂度。
二、实验原理快速排序是一种基于交换的排序方式。
它是由图灵奖得主 Tony Hoare 发明的。
快速排序的原理是：对一个未排序的数组，先找一个轴点，将比轴点小的数放到它的左边，比轴点大的数放到它的右边，再对左右两部分递归地进行快速排序，完成整个数组的排序。
优缺点：快速排序是一种分治思想的算法，因此，在分治思想比较适合的场景中，它具有较高的效率。
它是一个“不稳定”的排序算法，它的工作原理是在大数组中选取一个基准值，然后将数组分成两部分。
具体过程如下：首先，选择一个基准值（pivot），一般是选取数组的中间位置。
然后把数组的所有值，按照大小关系，分成两部分，小于基准值的放左边，大于等于基准值的放右边。
继续对左右两个数组递归进行上述步骤，直到数组只剩一个元素为止。
三、实验步骤1.编写快速排序代码：void quicksort(int *a,int left,int right) {int i,j,t,temp;if(left>right)return;temp=a[left];i=left;j=right;while(i!=j) {// 顺序要先从右往左移while(a[j]>=temp&&i<j)j--;while(a[i]<=temp&&i<j)i++;if(i<j) {t=a[i];a[i]=a[j];a[j]=t;}}a[left]=a[i];a[i]=temp;quicksort(a,left,i-1);quicksort(a,i+1,right);}2.使用 rand() 函数产生整型随机数并量化生成的随机数序列，运用快速排序算法对序列进行排序。
四、实验结果实验结果显示，快速排序能够有效地快速地排序整型序列。
在随机产生的数值序列中，快速排序迅速地将数值排序，明显快于冒泡排序等其他排序算法。
本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！== 本文为word格式，下载后可方便编辑和修改！ ==快速排序算法实验报告篇一：快速排序( 实验报告附C++源码)快速排序一、问题描述在操作系统中，我们总是希望以最短的时间处理完所有的任务。
但事情总是要一件件地做，任务也要操作系统一件件地处理。
当操作系统处理一件任务时，其他待处理的任务就需要等待。
虽然所有任务的处理时间不能降低，但我们可以安排它们的处理顺序，将耗时少的任务先处理，耗时多的任务后处理，这样就可以使所有任务等待的时间和最小。
只需要将n 件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。
当有 n 件任务同时来临时，每件任务需要用时ni，求让所有任务等待的时间和最小的任务处理顺序。
二、需求分析1. 输入事件件数n，分别随机产生做完n件事所需要的时间；2. 对n件事所需的时间使用快速排序法，进行排序输出。
排序时，要求轴值随机产生。
3. 输入输出格式：输入：第一行是一个整数n，代表任务的件数。
接下来一行，有n个正整数，代表每件任务所用的时间。
输出：输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要处理的任务所用的时间。
按此顺序进行，则使得所有任务等待时间最小。
4. 测试数据：输入95 3 4 26 1 57 3 输出1 2 3 3 4 5 5 6 7三、概要设计抽象数据类型因为此题不需要存储复杂的信息，故只需一个整型数组就可以了。
算法的基本思想对一个给定的进行快速排序，首先需要选择一个轴值，假设输入的数组中有k 个小于轴值的数，于是这些数被放在数组最左边的k个位置上，而大于周知的结点被放在数组右边的n-k个位置上。
k也是轴值的下标。
这样k把数组分成了两个子数组。
分别对两个子数组，进行类似的操作，便能得到正确的排序结果。
程序的流程输入事件件数n-->随机产生做完没个事件所需时间-->对n个时间进行排序-->输出结果快速排序方法（因图难画，举一个实例）：初始状态 72 6 57 88 85 42 l r 第一趟循环 72 6 57 88 85 42 l r 第一次交换 6 72 57 88 85 42 l r 第二趟循环 6 72 57 88 85 42 r l 第二次交换 72 6 57 88 85 42 r l反转交换 6 72 57 88 85 42 r l这就是依靠轴值，将数组分成两部分的实例（特殊情况下，可能为一部分，其中42是轴值）。
《数据结构与算法》实验报告一、需求分析问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。
试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
基本要求：（l）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。
（2）待排序表的表长不小于100000；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
（3）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。
数据测试：二．概要设计1.程序所需的抽象数据类型的定义：typedef int BOOL; //说明BOOL是int的别名typedef struct StudentData { int num; //存放关键字}Data; typedef struct LinkList { int Length; //数组长度Data Record[MAXSIZE]; //用数组存放所有的随机数} LinkList int RandArray[MAXSIZE]; //定义长度为MAXSIZE的随机数组void RandomNum() //随机生成函数void InitLinkList(LinkList* L) //初始化链表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, int* CmpNum, int* ChgNum) //快速排序void HeapSort (LinkList* L, int* CmpNum, int* ChgNum) //堆排序void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum) //冒泡排序void SelSort(LinkList* L, int* CmpNum, int* ChgNum) //选择排序void Compare(LinkList* L,int* CmpNum, int* ChgNum) //比较所有排序2 .各程序模块之间的层次（调用）关系：二、详细设计typedef int BOOL; //定义标识符关键字BOOL别名为int typedef struct StudentData //记录数据类型{int num; //定义关键字类型}Data; //排序的记录数据类型定义typedef struct LinkList //记录线性表{int Length; //定义表长Data Record[MAXSIZE]; //表长记录最大值}LinkList; //排序的记录线性表类型定义int RandArray[MAXSIZE]; //定义随机数组类型及最大值/******************随机生成函数********************/void RandomNum(){int i; srand((int)time(NULL)); //用伪随机数程序产生伪随机数for(i=0; i小于MAXSIZE; i++) RandArray[i]<=(int)rand(); 返回;}/*****************初始化链表**********************/void InitLinkList(LinkList* L) //初始化链表{int i;memset(L,0,sizeof(LinkList));RandomNum();for(i=0; i小于<MAXSIZE; i++)L->Record[i].num<=RandArray[i]; L->Length<=i;}BOOL LT(int i, int j,int* CmpNum){(*CmpNum)++; 若i<j) 则返回TRUE; 否则返回FALSE;}void Display(LinkList* L){FILE* f; //定义一个文件指针f int i;若打开文件的指令不为空则//通过文件指针f打开文件为条件判断{ //是否应该打开文件输出“can't open file”;exit(0); }for (i=0; i小于L->Length; i++)fprintf(f,"%d\n",L->Record[i].num);通过文件指针f关闭文件;三、调试分析1.调试过程中遇到的问题及经验体会:在本次程序的编写和调试过程中，我曾多次修改代码，并根据调试显示的界面一次次调整代码。
在调试成功之前，我的程序因为3个错误而无法运行，在经过完整并且仔细的检查后，发现3处错误分别是没有定义变量就直接套用、忘记加指针符号、忘记在嵌套语句后加大括号，这些看似不显眼的小问题却导致整个程序无法运行，所以我认为在编程过程中要及其严谨，尽量少犯或避免犯语法错误，保证代码的完整性。
2.算法的时空分析：1.稳定性比较：插入排序、冒泡排序、简单选择排序及其他线形排序是稳定的；希尔排序、快速排序、堆排序是不稳定的。
2.时间复杂性比较：插入排序、冒泡排序、选择排序的时间复杂性为O(n2)；其它非线形排序的时间复杂性为O(nlog2n)；线形排序的时间复杂性为O(n)。
3.辅助空间的比较：线形排序的辅助空间为O(n)，其它排序的辅助空间为O(1)。
4.其它比较：插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。
反而在这种情况下，快速排序反而慢了：当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序；当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。
四、用户守则1.可执行文件为：a.exe2.为了界面更加友好特将背景颜色设计为黑色，字体为白色。
3.进入演示程序后即显示文本形式的用户界面，再按提示一步步完成：五、测试结果测试结果及其分析：通过本次程序的运行，得到数据：插入排序：比较的次数为25114496，交换的次数为25094525，花费的时间为1203ms；希尔排序：比较的次数为3834939，交换的次数为3782098，花费的时间为187ms；快速排序：比较的次数为153398，交换的次数为62804，花费的时间为0ms；堆排序：比较的次数为235273，交换的次数为124235，花费的时间为16ms；冒泡排序：比较的次数为49995000，交换的次数为27537172，花费的时间为2969ms；选择排序：比较的次数为50005000，交换的次数为9988，花费的时间为1656ms。
算法效率是依据算法执行的时间来看的，从上面的数据来看，虽然插入排序的算法简洁，容易实现，但是从它执行的时间1203ms 来看它的效率并不是很高，而且比较次数和交换次数都比较多，在这六种排序中效率是很底的；希尔排序的时间复杂度较直接排序低，在六种内部排序中效率居中；分析冒泡排序的效率，容易看出，若初始序列为“正序”序列，则只进行一趟排序，在排序过程中进行n-1次关键字的比较，反之，则需进行n-1趟排序，总的时间复杂度为O(n2)，在该程序中，冒泡排序所花费的时间为4360，是所有排序中花费最多的，可见效率是很底的。
快速排序是对冒泡排序的一种改进，它所用的时间几乎为0，交换的比较的次数都比较少；堆排序仅次于快速排序，花费的时间只有16ms。
由以上讨论可知，从时间上看，快速排序的平均性能都优于其他5种排序。
算法时间复杂度分析如下：1、直接插入排序：当文件的初始状态不同时，直接插入排序所耗费的时间是有很大差异的。
最好情况是文件初态为正序，此时算法的时间复杂度为O(n)，最坏情况是文件初态为反序，相应的时间复杂度为O(n2)，算法的平均时间复杂度是O(n2)；2、选择排序是不稳定的，算法复杂度为O(n2)；3、快速排序是不稳定的主体算法时间运算量约O(log2n)，划分子区函数运算量约O(n)，所以总的时间复杂度为O(nlog2n)，它显然优于冒泡排序O(n2)；4、希尔排序是不稳定的，算法复杂度是n1.25~1.6*n1.25；5、冒泡排序是稳定的，时间复杂度为O(n2)；6、堆排序是不稳定的。
对各种表长和测试组数进行了测试，程序运行正常。
分析实测得到的数值，6种排序算法的特点小结如下：(1)若n较小（如n≤50），可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜；(2)若文件初始状态基本有序（指正序），则应选用直接插人、冒泡或随机的快速排序为宜；(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序；快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。
这两种排序都是不稳定的。
六、附录（源代码）#include<stdio.h># include <stdlib.h># include <string.h># include <time.h># include <windows.h># include <winbase.h># define MAXSIZE 10000 //线性表中最多元素个数#define TRUE 1# define FALSE 0typedef int BOOL; //定义标识符关键字BOOL别名为int typedef struct StudentData //记录数据类型{int num; //定义关键字类型}Data; //排序的记录数据类型定义typedef struct LinkList //记录线性表{int Length; //定义表长Data Record[MAXSIZE]; //表长记录最大值}LinkList; //排序的记录线性表类型定义int RandArray[MAXSIZE]; //定义随机数组类型及最大值/******************随机生成函数********************/ void RandomNum() //随机生成函数{int i;srand((int)time(NULL)); //用伪随机数程序产生伪随机数for(i=0; i<MAXSIZE; i++)RandArray[i]=(int)rand(); return; }/*****************初始化链表**********************/void InitLinkList(LinkList* L) //初始化链表{int i;memset(L,0,sizeof(LinkList));RandomNum(); //调用随机函数for(i=0; i<MAXSIZE; i++)L->Record[i].num=RandArray[i]; L->Length=i;}BOOL LT(int i, int j, int* CmpNum) {(*CmpNum)++;if (i<j) return TRUE;return FALSE;}void Display(LinkList* L){FILE* f; //定义一个文件指针f int i;if((f=fopen("SortRes.txt","w"))==NULL) //通过文件指针f 打开文件为条件判断{ //是否应该打开文件printf("can't open file\n"); exit(0);}for (i=0; i<L->Length; i++)fprintf(f,"%d\n",L->Record[i].num);fclose(f); //通过文件指针f关闭文件}/***********冒泡排序*******************************/void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum){ int i,j;Data temp;for (i=0; i<MAXSIZE-1;i++){for(j=0;j<MAXSIZE-i-1;j++) {if(!LT(L->Record[j].num,L->Record[j+1].num,CmpNum)){(*ChgNum)++;memcpy(&temp,&L->Record[j],sizeof(Data));memcpy(&L->Record[j],&L->Record[j+1],sizeof(Data));memcpy(&L->Record[j+1],&temp,sizeof(Data));}}}}/*******选择排序*******************************/int SelectMinKey(LinkList* L,int k,int* CmpNum){int Min=k;for ( k<L->Length; k++) {if(!LT(L->Record[Min].num,L->Record[k].num,CmpNum)) Min=k;}return Min;}void SelSort(LinkList* L, int* CmpNum, int* ChgNum){int i, j; Data temp;for(i=0; i<L->Length; i++) {j=SelectMinKey(L,i,CmpNum);if(i!=j){(*ChgNum)++;memcpy(&temp,&L->Record[i],sizeof(Data));memcpy(&L->Record[i],&L->Record[j],sizeof(Data));memcpy(&L->Record[j],&temp,sizeof(Data));}}}/*************快速排序******************************/int Partition (LinkList* L, int low, int high, int* CmpNum, int* ChgNum) {Data Temp;int PivotKey;memcpy(&Temp,&L->Record[low],sizeof(Data));PivotKey=L->Record[low].num;while (low < high){while (low<high && L->Record[high].num >= PivotKey) {high--;(*CmpNum)++;}(*ChgNum)++;memcpy(&L->Record[low],&L->Record[high],sizeof(Data)); while (low<high && L->Record[low].num <= PivotKey){low++;(*CmpNum)++;}(*ChgNum)++;memcpy(&L->Record[high],&L->Record[low],sizeof(Data)); }memcpy(&L->Record[low],&Temp,sizeof(Data));return low;}void QSort (LinkList* L, int low, int high, int* CmpNum, int*ChgNum) {int PivotLoc=0;if (low < high){PivotLoc=Partition(L,low,high,CmpNum,ChgNum);QSort(L,low,PivotLoc-1,CmpNum,ChgNum);QSort(L,PivotLoc+1,high,CmpNum,ChgNum); }}void QuickSort (LinkList* L, int* CmpNum, int* ChgNum) { QSort(L,0,L->Length-1,CmpNum,ChgNum);}/*********************希尔排序*************************/ void ShellInsert(LinkList* L,int dk, int* CmpNum, int* ChgNum) {int i, j; Data Temp; for(i=dk; i<L->Length;i++) {if( LT(L->Record[i].num, L->Record[i-dk].num, CmpNum) ) {memcpy(&Temp,&L->Record[i],sizeof(Data));for(j=i-dk; j>=0 && LT(Temp.num, L->Record[j].num, CmpNum) j-=dk){(*ChgNum)++;memcpy(&L->Record[j+dk],&L->Record[j],sizeof(Data));}memcpy(&L->Record[j+dk],&Temp,sizeof(Data));}}}void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum){int k; for (k=0; k<t; k++) ShellInsert(L,dlta[k],CmpNum,ChgNum); } /************堆排序******************************/void HeapAdjust (LinkList* L,int s, int m, int* CmpNum, int* ChgNum){Data Temp;int j=0; s++;memcpy(&Temp,&L->Record[s-1],sizeof(Data));for (j=2*s; j<=m j*=2){if(j<m && LT(L->Record[j-1].num,L->Record[j].num,CmpNum))++j;if(!LT(Temp.num,L->Record[j-1].num,CmpNum))break;(*ChgNum)++;memcpy(&L->Record[s-1],&L->Record[j-1],sizeof(Data));s=j;}memcpy(&L->Record[s-1],&Temp,sizeof(Data)); }void HeapSort (LinkList* L, int* CmpNum, int* ChgNum) {int i=0;Data Temp;for (i=L->Length/2-1; i>=0; i--)HeapAdjust(L,i,L->Length,CmpNum,ChgNum);for (i=L->Length; i>1; i--){memcpy(&Temp,&L->Record[0],sizeof(Data));(*ChgNum)++;memcpy(&L->Record[0],&L->Record[i-1],sizeof(Data)); memcpy(&L->Record[i-1],&Temp,sizeof(Data)); HeapAdjust(L,0,i-1,CmpNum,ChgNum);}}/****************比较所有排序******************************/ void Compare(LinkList* L,int* CmpNum, int* ChgNum) { int TempTime,i;int SpendTime;int dlta[3]={7,3,1};int Indata[1]={1};TempTime=(int)GetTickCount();ShellSort(L,Indata,1,&CmpNum[0],&ChgNum[0]); SpendTime=(int)GetTickCount()-TempTime;printf("\n\t================================== ==================="); printf("\n\n\t插入排序:");printf("\n\t比较的次数=%d\t交换的次数=%d\t所用的时间=%dms",CmpNum[0],ChgNum[0],SpendTime);for(i=0; i<MAXSIZE; i++)L->Record[i].num=RandArray[i]; //随机数列复位TempTime=(int)GetTickCount();ShellSort(L, dlta, 3,&CmpNum[1],&ChgNum[1]);SpendTime=(int)GetTickCount()-TempTime;printf("\n\n\t希尔排序:");printf("\n\t比较的次数=%d\t交换的次数=%d\t所用的时间=%dms",CmpNum[1],ChgNum[1],SpendTime);for(i=0; i<MAXSIZE; i++)L->Record[i].num=RandArray[i]; //随机数列复位TempTime=(int)GetTickCount();QuickSort(L,&CmpNum[2],&ChgNum[2]);SpendTime=(int)GetTickCount()-TempTime;printf("\n\n\t快速排序:");printf("\n\t比较的次数=%d\t交换的次数=%d\t所用的时间=%dms",CmpNum[2],ChgNum[2],SpendTime);for(i=0; i<MAXSIZE; i++)L->Record[i].num=RandArray[i]; //随机数列复位TempTime=(int)GetTickCount();HeapSort(L,&CmpNum[3],&ChgNum[3]);SpendTime=(int)GetTickCount()-TempTime;printf("\n\n\t堆排序:");printf("\n\t比较的次数=%d\t交换的次数=%d\t所用的时间=%dms",CmpNum[3],ChgNum[3],SpendTime);for(i=0; i<MAXSIZE; i++) L->Record[i].num=RandArray[i]; //随机数列复位TempTime=(int)GetTickCount();BubbleSort(L,&CmpNum[4],&ChgNum[4]);SpendTime=(int)GetTickCount()-TempTime;printf("\n\n\t冒泡排序:");printf("\n\t比较的次数=%d\t交换的次数=%d\t所用的时间=%dms",CmpNum[4],ChgNum[4],SpendTime);for(i=0; i<MAXSIZE; i++) L->Record[i].num=RandArray[i];//随机数列复位TempTime=(int)GetTickCount();SelSort(L,&CmpNum[5],&ChgNum[5]);SpendTime=(int)GetTickCount()-TempTime;printf("\n\n\t选择排序:");printf("\n\t比较的次数=%d\t交换的次数=%d\t所用的时间=%dms",CmpNum[5],ChgNum[5],SpendTime);printf("\n\t================================== ==================="); }/***************主函数*******************************/void main() { int select=0;int dlta[3]={7,3,1}; int Indata[1]={1};int CmpNum[6],ChgNum[6]; //CnpNum数组时比较次数，ChgNum是交换次数int SpendTime=0;LinkList L; InitLinkList(&L);memset(CmpNum,0,sizeof(CmpNum));memset(ChgNum,0,sizeof(ChgNum));printf("\n\n\t\t******************************************\n"); printf("\t\t 数据结构课程设计\n\n");printf("\t\t ——内部排序算法的比较\n\n");printf("\t\tPlese press enter to continue...\n"); printf("\t\t******************************************");getchar(); system("cls.exe");printf("\n\t正在计算，请稍等....."); Compare(&L,CmpNum,ChgNum);//比较所有排序Display(&L); printf("\n\n\t比较结束, 请按回车键!\n");getchar();getchar();}THANKS致力为企业和个人提供合同协议，策划案计划书，学习课件等等打造全网一站式需求欢迎您的下载，资料仅供参考。
