快速排序算法实验报告,数据结构排序实验报告代码怎么写
快速排序算法实验报告,数据结构排序实验报告代码怎么写详细介绍
本文目录一览： 快速排序算法的实验验证 [ 实验目的] 验证快速排序算法。(C++)
今天介绍快速排序，这也是在实际中最常用的一种排序算法，速度快，效率高。就像名字一样，快速排序是最优秀的一种排序算法。
思想
快速排序采用的思想是分治思想。
快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
举例说明一下吧，这个可能不是太好理解。假设要排序的序列为
2 2 4 9 3 6 7 1 5 首先用2当作基准，使用i j两个指针分别从两边进行扫描，把比2小的元素和比2大的元素分开。首先比较2和5，5比2大，j左移
2 2 4 9 3 6 7 1 5 比较2和1，1小于2，所以把1放在2的位置
2 1 4 9 3 6 7 1 5 比较2和4，4大于2，因此将4移动到后面
2 1 4 9 3 6 7 4 5 比较2和7，2和6，2和3，2和9，全部大于2，满足条件，因此不变
经过第一轮的快速排序，元素变为下面的样子
[1] 2 [4 9 3 6 7 5]
之后，在把2左边的元素进行快排，由于只有一个元素，因此快排结束。右边进行快排，递归进行，最终生成最后的结果。
代码
int quicksort(vector
&v, int left, int right){if(left < right){int key = v[left];int low = left;int high = right;while(low < high){while(low < high && v[high] > key){high--;}v[low] = v[high];while(low < high && v[low] < key){low++;}v[high] = v[low];}v[low] = key;quicksort(v,left,low-1);quicksort(v,low+1,right);}}
分析
快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。
最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n*n)
在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)
尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。
快速排序
基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
下面通过一个例子介绍快速排序算法的思想，假设要对数组a[10]={6，1，2，7，9，3，4，5，10，8}进行排序，首先要在数组中选择一个数作为基准值，这个数可以随意选择，在这里，我们选择数组的第一个元素a[0]=6作为基准值，接下来，我们需要把数组中小于6的数放在左边，大于6的数放在右边，怎么实现呢？
我们设置两个“哨兵”，记为“哨兵i”和“哨兵j”，他们分别指向数组的第一个元素和最后一个元素，即i=0，j=9。首先哨兵j开始出动，哨兵j一步一步地向左挪动（即j–），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。
最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。此时就需要交换i和j指向的元素的值。
交换之后的数组变为a[10]={6，1，2，5，9，3，4，7，10，8}：
第一次交换至此结束。接下来，由于哨兵i和哨兵j还没有相遇，于是哨兵j继续向前，发现比6小的4之后停下；哨兵i继续向前，发现比6大的9之后停下，两者再进行交换。交换之后的数组变为a[10]={6，1，2，5，4，3，9，7，10，8}。
第二次交换至此结束。接下来，哨兵j继续向前，发小比6小的3停下来；哨兵i继续向前，发现i==j了！！！于是，这一轮的探测就要结束了，此时交换a[i]与基准的值，数组a就以6为分界线，分成了小于6和大于6的左右两部分：a[10]={3，1，2，5，4，6，9，7，10，8}。
至此，第一轮快速排序完全结束，接下来，对于6左边的半部分3，1，2，5，4，执行以上过程；对于6右边的半部分9，7，10，8，执行以上过程，直到不可拆分出新的子序列为止。最终将会得到这样的序列：1 2 3 4 5 6 7 8 9 10，到此，排序完全结束。
快速排序的一次划分算法从两头交替搜索，直到low和hight重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。
理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log 2 n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog 2 n)。
最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n 2 )。
为改善最坏情况下的时间性能，可采用其他方法选取中间数。通常采用“三者值取中”方法，即比较H->r[low].key、H->r[high].key与H->r[(low+high)/2].key，取三者中关键字为中值的元素为中间数。
可以证明，快速排序的平均时间复杂度也是O(nlog 2 n)。因此，该排序方法被认为是目前最好的一种内部排序方法
快速排序法
快速排序法一般指快速排序算法。
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
排序流程
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：?
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。?
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。?
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
快速排序（Quicksort）是对冒泡排序的一种改进。[1]
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。[1]
中文名
快速排序算法
外文名
quick sort
别名
快速排序
提出者
C. A. R. Hoare
提出时间
1960年
快速
导航
排序步骤
程序调用举例
示例代码
性能分析
排序流程
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：[2]
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。[2]
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。[2]
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。[2]
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。[2]
排序步骤
原理
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选
快排图
用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。[1]
一趟快速排序的算法是：[1]
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；[1]
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；[1]
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；[1]
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；[1]
5）重复第3、4步，直到i==j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。[1]
排序演示
假设一开始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。
此时，ref=5，i=1，j=11，从后往前找，第一个比5小的数是x8=2，因此序列为：2，3，7，6，4，1，0，5，9，10，8。
此时i=1，j=8，从前往后找，第一个比5大的数是x3=7，因此序列为：2，3，5，6，4，1，0，7，9，10，8。
此时，i=3，j=8，从第8位往前找，第一个比5小的数是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。
数据结构排序实验报告代码怎么写
引入必要的库和模块，定义排序算法、测试数据生成、性能评估函数，实现实验逻辑、输出实验结果。1、根据实验要求，引入排序算法的实现代码或者用于生成测试数据的库。2、实现不同的排序算法，例如冒泡排序、插入排序、选择排序、快速排序等，确保每个排序算法都有明确的输入和输出，根据实验要求，编写函数来生成测试数据。
实验题【实验四题目1】
数据结构实验报告
实验名称： 实验四——题目一
学生姓名： 唐文旭
班 级：2013211118
班内序号： 09
学 号： 2013210524
日 期： 2015年1月5日
1．实验要求
使用简单数组实现下面各种排序算法，并进行比较。
排序算法：
1、插入排序
2、希尔排序
3、冒泡排序
4、快速排序
5、简单选择排序
6、堆排序（选作）
7、归并排序（选作）
8、基数排序（选作）
9、其他
要求：
1、测试数据分成三类：正序、逆序、随机数据
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度
编写测试main()函数测试线性表的正确性。
2. 程序分析
2.1 存储结构
2.2 关键算法分析
北京邮电大学信息与通信工程学院
第2页
希尔排序又称“缩小增量排序”，是对直接插入排序的一种改进，它利用了直接插入的两个特点：1. 基本有序的序列，直接插入最快；2. 记录个数很少的无序序列，直接插入也很快。希尔排序的基本思想为：将待排序的元素集分成多个子集，分别对这些子集进行直接插入排序，待整个序列基本有序时，再对元素进行一次直接插入排序。
冒泡排序的基本思想是：两两比较相邻的元素，如果反序，则交换位置，直到没有反序的元素为止。具体的排序过程是：将整个待排序元素划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的元素；对无序区从前向后依次将相邻元素的关键码进行比较，若反序则交换，从而使得关键码小的元素向前移，关键码大的元素向后移；重复执行前一个步骤，直到无序区中没有反序的元素。
快速排序元素的比较和移动是从两端向中间进行的。快速排序的基本思想是：在分区中选择一个元素作为轴值，将待排序元素划分成两个分区，使得左侧元素的关键码均小于或等于轴值，右侧元素的关键码均大于或等于轴值，然后分别对这两个分区重复上述过程，直到整个序列有序。
简单选择排序的基本思想是：第1趟，在待排序记录r[1?n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2?n]中选出最小的记录，将它与r[2]交换；以此类推，第i 趟，在待排序记录r[i?n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。
r[0]留空，初始时赋为0
2.2 关键算法分析
1、直接插入排序
自然语言描述：
（1） 将整个待排序的记录划分成有序区和无序区。有序区为待排序记录的第一个记录， 无序区为所有剩余带待排序记录。
（2） 从第二个数据开始依次插入到有序区中，直到所有记录插入完毕。 （3） 在r[0]处设置“哨兵”，记为要插入的记录r[i]，在自i-1起往前查找的过程中，同时
后移记录。
（4） 找到插入位置后，将待插入记录插入到有序表中。
（5） 重复执行（3）、（4），直到无序区中没有记录。
伪代码描述：
初始化比较次数compare =0，移动次数move =0 2. for(int i=2;i
for(j=i-1;r[0]
r[j+1]=r[j] 比较次数++；移动次数++；
r[j+1]=r[0]，移动次数++
时间复杂度：最好情况下，待排序序列为正序，每趟秩序与有序序列的最后一个纪录的关键码比较一次，移动两次记录。总的比较次数为n-1，记录移动的次数为2（n-1）。因此，时间复杂度为O （n ）。
最坏情况下，待排序序列为逆序，比较次数为(n+2)(n+1)/2，移动次数为(n+4)(n-1)/2因此，时间复杂度为O （n2）.
平均情况下，总的比较次数为n （n-1）/4，移动次数为（n+4）（n-1）/4，因此，时间复杂度
为O （n2）
2、希尔排序
自然语言描述：
（1） 假设待排序记录为n 个，先取整数d
中的前一个记录比较，在插入记录r[i]时，自r[i-d]往前查找待插入位置，在查找过程中，记录后移也是移动d 个位置。
（3） 当搜索位置j=r[j]，表示插入位置已经找到。在整个序列中，前d 个记 录分别是d 个子序列的第一个记录，所以从第d+1个记录开始插入。 （4） 再缩小d ，重复以上步骤，再对每个子序列进行直接插入排序，直到d=1，即将所有
记录放在一组进行一次直接插入排序，最终将所有记录重新排序得到有序序列。
伪代码描述：
1. 初始化比较次数compare =0，移动次数move =0
for(int d=n/2;d>=1;d=d/2)
for(int i=d+1;i
if(r[i]
r[0]=r[i]，移动次数++
for(j=i-d;i>0&&r[0]
r[j+d]=r[j] 比较次数++，移动次数++
r[j+d]=r[0]，移动次数++
时间复杂度：
希尔排序的时间性能分析是一个复杂的问题，因为它是所取增量的函数。有人在大量实验的基础上指出，希尔排序的时间性能在O （n2）和O （nlog2n ）之间
3、冒泡排序
自然语言描述：
（1） 将整个待排序的记录划分成有序区和无序区，初始有序区为空，无序区包括所有待排序记录。设置变量pos ，此位置之后的所有记录均已经有序。
（2） 对无序区从前向后一次将相邻记录的关键码进行比较，若反序则交换，从而使得关 键码小的记录前移，关键码大的记录后移。
（3） 每趟冒泡排序开始之前，设pos 初值为0，在该趟排序过程中，只要有记录的交换，pos 就大于0。通过pos 是否为0判断是否有记录的交换，从而判断冒泡排序是否结束。 伪代码描述：
初始化比较次数compare =0，移动次数move =0
int pos=0 2. while(pos!=0)
int bound=pos，pos=n
for(int j=1;j
if(r[j]>r[j+1])
r[0]=r[j]，r[j]=r[j+1],r[j+1]=r[0]
pos=j，move+=3
时间复杂度：
最好情况下，待排序记录序列为正序，算法只执行了一趟，进行了n-1次关键妈的比较，不需要移动记录，时间复杂度为O （n ） 最坏情况下，待排序记录序列为反序，每趟排序在无序序列中只有一个最大的纪录被交换到最终位置，故算法执行n-1趟，第i 趟排序执行了n-1
次关键码的比较和n-i 次记录的交换，这样，关键码的比较次数为n （n-1）/2，记录的移动次数为3n （n-1）/2平均情况下，起泡排序的时间复杂度与最坏情况同数量级。
4、快速排序
自然语言描述：
（1） 取第一个记录作为基准，设置两个参数i ，j 分别用来指示将要与基准记录进行比较 的左侧记录位置和右侧记录位置，也就是本次划分的区间。 （2） 右侧扫描过程：将基准记录与j 指向的记录进行比较，如果j 指向记录的关键码大，
则j--，重复右侧扫描过程，直到右侧的记录小，即反序，执行r[i]=r[j] （3） 左侧扫描过程：将基准记录与i 指向的记录进行比较，如果i 指向记录的关键码大，
则i--，重复右侧扫描过程，直到右侧的记录小，即反序，执行r[j]=r[i]
（4） 重复执行（2）、（3），直到i 、j 指向同一位置。 （5） r[i]=pivot （6） 返回i 的位置 伪代码描述：
int i=first; int j=end; int pivot=r[i] 2. while(i
while((i=pivot))
j--; 比较次数++
r[i]=r[j] 2.3 if(i
while((i
r[j]=r[i] 2.6 if(i
r[i]=pivot; return i ;
时间复杂度：
最好情况下，每次划分对一个记录定位后，该记录的左侧子序列和右侧子序列的长度相同。在具有n 个记录的序列中，对一个记录定位要对整个待划分序列扫描一遍，则所需时间为O
（n ）。时间复杂度为O （nlog2n ）。 最坏情况下，待排序记录序列正序或逆序，每次划分只得到一个比上一次划分少一个纪录的子序列（另一个子序列为空）。此时，必须经过n-1次递归调用才能把所有记录定位，而且第i 趟划分需要经过n-i 次关键码的比较才能找到第i 个记录的基准记录，因此总的比较次数为n （n-1）/2，记录的移动次数小于等于比较次数。因此时间复杂度为O （n2）. 平均情况下，可以用归纳法证明，其数量级也为O （nlog2n ）。
5、简单选择排序
自然语言描述：
（1） 将整个记录划分为有序区和无序区，初始有序区为空，无序区包括所有待排序记录。设置变量index ，记录一次比较中关键码最小的位置。
（2） 第i 趟简单选择排序的待排序区间是r[i]-r[n]，首先将index 设定为当前无序区的第一个位置，然后用r[index]与无序区中其他记录进行比较，若有比r[index]小的记录，就将index 改为这个新的最小的记录的位置。
（3） 如果index 不等于i ，则将它与无序区中第一个记录交换，有序区增加一个记录，无 序区减少一个记录。 （4） 重复（2）（3），直到无序区只剩下一个记录为止。此时所有记录已经按照从小到大
的顺序排好。 伪代码描述：
初始化比较次数compare=0，移动次数move=0
for(int i=1;i
int index=i
for(int j=i+1;j
if(r[j]
if(index!=i)
r[0]=r[i];r[i]=r[index];r[index]=r[0]
move+=3
时间复杂度：待排序序列为正序时，记录的移动次数最少，为0次。在待排序序列为逆序时，记录的移动次数最多为3（n-1）次。
无论记录的初始排列如何，关键码的比较次数相同，第i 趟排序需进行n-1次关键码的比较，而简单选择排序需进行n-1趟排序，则总的比较次数为n （n-1）/2=O（n2）。所以， 总的时间复杂度为O(n2)，这是简单选择排序最好、最坏、和平均的时间性能。
3. 程序运行结果
测试条件：
问题规模的数量级是4，正序逆序由键盘输入，随机数由随机数生成函数生成。
测试结论：
程序对不同序列的数组运用各种不同方法进行排序时均能得到正确的排序结果，同时能够给出正确的比较次数和移动次数。
4. 总结
插入排序：n*n的时间复杂度，稳定排序，原地排序。在数据大部分都排好了，用插入排序会给你带来很大的方便。数据的移动和交换都很少。
希尔排序：n*log(n)的时间复杂度， 非稳定排序，原地排序。主要思想是分治，不过他的分治和合并排序的分治不一样，他是按步长来分组的，而不是想合并那样左一半右一半。 开始
输出测试数组
进行简单插入排序 进行希尔排序
进行起泡排序 进行快速排序
进行简单选择排序 结束
开始步长为整个的长度的一半，然后每组排序。接个步长减为原来的一半在分组排序，直到步长为1，排序之后希尔排序就完成了。这个思路很好，是插入排序的升级版，我觉得他是一个特别好的排序方法了。他的缺点就是两个数可能比较多次，但效率也是很高的。
冒泡排序，n*n的时间复杂度，稳定排序，原地排序。冒泡排序的思想很不错，一个一个比较，把小的上移，依次确定当前最小元素。因为他简单，稳定排序，而且好实现，所以用处也是比较多的。
选择排序，n*n的时间复杂度， 稳定排序，原地排序。选择排序就是冒泡的基本思想，从小的定位，一个一个选择，直到选择结束。和插入排序是一个相反的过程，插入是确定一个元素的位置，而选择是确定这个位置的元素。它的好处就是每次只选择确定的元素，不会对很多数据进行交换。所以在数据交换量上应该比冒泡小。
数据结构课程设计综合排序代码及实验报告书。
需要对条目进行自动排序，当增加或减少条目时，下面的会自动进行再排序，你回答中的格式--样式和格式的操作，我不是很明白，要怎么操作才能实现自动排序。
重新
#include
#include
#include
#include
#define N 200
double maopao(int B[],int M)//冒泡排序
{
clock_t start, finish;
double time; // 测量一个事件持续的时间
start = clock();
FILE *fp1;
int i,j,t;
for(i=0;i
<m-1;i++) 排序
for(j=0;j
<m-i-1;j++)
if(B[j]>B[j+1])
{
t=B[j];B[j]=B[j+1];B[j+1]=t;
}
finish = clock();
time = (double)(finish - start) / CLOCKS_PER_SEC;
fp1=fopen("a","wb");
printf("经排序后序列为:\n");
for(i=0;i
<m;i++) 输出排序后结果
{
if(i%10==0)printf("\n");
printf("%d ",B[i]);
fwrite(&B[i],sizeof(int),1,fp1);//把数据以二进制形式存入磁盘文件
}fclose(fp1);
printf("\n");
printf( "冒泡排序法运行时间：" );
printf( "%f seconds\n", time );
return time;
}
double charru(int A[], int len)//插入排序
{
clock_t start, finish;
double time; // 测量一个事件持续的时间
start = clock();
FILE *fp2;
int i,j,high,low,mid,temp;
for(i=1;i
<len;i++)
{
temp=A[i];
low=0;high=i-1;
while(low<=high)
{
mid=(low+high)/2;
if(A[0]>temp)
high=mid-1;
else low=mid+1;
}
for(j=i-1;j>high;j--)
A[j+1]=A[j];
A[high+1]=temp;
}
finish = clock();
time = (double)(finish - start) / CLOCKS_PER_SEC;
fp2=fopen("b","wb");
printf("经排序后序列为:\n");
for(i=0;i
<len;i++)
{
if(i%10==0)printf("\n");
printf("%d ",A[i]);
fwrite(&A[i],sizeof(int),1,fp2);
}fclose(fp2);
printf("\n");
printf( "插入排序法运行时间：" );
printf( "%f seconds\n", time );
return time;
}
double xuanze(int arry[],int n)//选择排序
{
clock_t start, finish;
double time; //测量一个事件持续的时间
start = clock();
FILE *fp3;
int i,j,k,t;
for(i=0;i
<n;i++)
{
k=i;
for(j=i+1;j
<n;j++)
if(arry[j]
<arry[k])
k=j;
t=arry[k];
arry[k]=arry[i];
arry[i]=t;
}
finish = clock();
time = (double)(finish - start) / CLOCKS_PER_SEC;
fp3=fopen("c","wb");
printf("经排序后序列为:\n");
for(i=0;i
<n;i++)
{
if(i%10==0)printf("\n");
printf("%d ",arry[i]);
fwrite(&arry[i],sizeof(int),1,fp3);
} fclose(fp3);
printf("\n");
printf( "选择排序法运行时间：" );
printf( "%f seconds\n", time );
return time;
}
int kuaisu(int*c,int low,int high)//快速排序确定枢轴位置
{
int temp,t;
temp=c[low];
while(low
<high)
{
while(low
=temp)high--;
{
t=c[low];c[low]=c[high];c[high]=t;
}
while(low
<high&&c[low]<=temp)low++;
{
t=c[low];c[low]=c[high];c[high]=t;
}
}
return low;
}
void kuaisu1(int *b,int low,int high)//快速排序
{
int t;
if(low
<high)
{
t=kuaisu(b,low,high);
kuaisu1(b,low,t-1);
kuaisu1(b,t+1,high);
}
}
double xier(int *x, int n)//希尔排序
{
clock_t start, finish;
double time; /* 测量一个事件持续的时间*/
start = clock();
FILE *fp5;
int h, j, k, t,i;
for(h=n/2; h>0; h=h/2)
{
for (j=h; j
<n; j++)
{
t = *(x+j);
for(k=j-h; (k>=0 && t<*(x+k)); k-=h)
{
*(x+k+h) = *(x+k);
}
*(x+k+h) = t;
}
}
finish = clock();
time = (double)(finish - start) / CLOCKS_PER_SEC;
fp5=fopen("e","wb");
printf("经排序后序列为:\n");
for(i=0;i
<n;i++)
{
if(i%10==0)
printf("\n");
printf("%d ",x[i]);
fwrite(&x[i],sizeof(int),1,fp5);
}fclose(fp5);
printf("\n");
printf( "希尔排序法运行时间：" );
printf( "%f seconds\n", time );
return time;
}
void main(void)
{
FILE *fp4;
int i,a[N];
double min,b[5];
char ch,ch1;
for(i=0;i<30;i++)
printf("*");
printf("欢迎进入综合排序系统");
for(i=0;i<30;i++)
printf("*");
printf("\n");
srand((unsigned)time(NULL));//获取随机数
printf("获得%d个随机数:\n",N);
for(i=0;i
<n;i++)
a[i]=(rand()%12767+20000)%32767;
for(i=0;i
<n;i++) 输出随机数
{
if(i%10==0)printf("\n");
printf("%d ",a[i]);
}
printf("\n");
do
{
for(i=0;i<80;i++)
printf("=");
printf("\t1.冒泡排序\n");
printf("\t2.选择排序\n");
printf("\t3.插入排序\n");
printf("\t4.快速排序\n");
printf("\t5.希尔排序\n");
printf("\t6.方法比较\n");
printf("\t7.退出\n");
printf("\t请选择排序方法:\n");
do
{
ch=getchar();
}while(ch!='1'&&ch!='2'&&ch!='3'&&ch!='4'&&ch!='5'&&ch!='6'&&ch!='7');
switch(ch)
{
case'1': b[0]=maopao(a,N);break;
case'2': b[1]=xuanze(a,N);break;
case'3': b[2]=charru(a,N);break;
case'4':
clock_t start, finish; //测量一个事件持续的时间
double time;
start = clock();
kuaisu1(a,0,N-1);
finish = clock();
time = (double)(finish - start) / CLOCKS_PER_SEC;
fp4=fopen("d","wb");
printf("经排序后序列为:\n");
for(i=0;i
<n;i++)
{
if(i%10==0)printf("\n");
printf("%d ",a[i]);
fwrite(&a[i],sizeof(int),1,fp4);
}fclose(fp4);
printf("\n");
finish = clock();
time = (double)(finish - start) / CLOCKS_PER_SEC;
b[3]=time;
printf( "快速排序法运行时间：" );
printf( "%f seconds\n", time ); break;
case'5': b[4]=xier(a,N);break;
case'6': min=b[0];
for(i=0;i<5;i++)
{
if(min>b[i])
min=b[i];
}
ch1='a';
i=0;
while(i<5)
{
if(min>=b[i])
switch(ch1)
{
case 'a':printf("较好的算法是冒泡排序\n");break;
case 'b':printf("较好的算法是选择排序\n");break;
case 'c':printf("较好的算法是插入排序\n");break;
case 'd':printf("较好的算法是快速排序\n");break;
case 'e':printf("较好的算法是希尔排序\n");break;
}
ch1++;i++;
}break;
case'7': {
printf("\n");
for(i=0;i<37;i++)
printf("*");
printf("谢谢 !");
for(i=0;i<37;i++)
printf("*");
exit(0);
}
default:exit(1);
}
}while(1);
}
</n;i++)
</n;i++)
</n;i++)
</high)
</high&&c[low]<=temp)low++;
</high)
</n;i++)
</arry[k])
</n;i++)
</len;i++)
</len;i++)
</m-i-1;j++)
快速排序和冒泡排序算法
此前由于自己对快速排序算法的认识不够，现在重新学习一遍，加深自己的认识。
快速排序算法是对冒泡算法的一种改进，大家都知道，冒泡排序是比较相邻元素的大小，而快速排序则在冒泡排序的基础上将数组分为两部分，在分别对他们进行排序，通过递归实现。
冒泡排序的实现过程：
快速排序的思想是在一个需要排序的数组A中首先选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的树都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法。
一般快速排序的算法是：
快速排序实现过程:
总结：快速排序和冒泡排序各有优缺点，不过快排时间复杂度是o(nlogn)，而冒牌排序在最坏的情况下的时间复杂度是o(n2)，所以快速排序在提升效率上快了不少。
快速排序的算法复杂度分析
原文地址：
快速排序的算法复杂度分析
以下是快排的java算法：
大家都知道快排的时间复杂度是O(n*ln[n])，那么这个复杂度是如何计算出来的呢？
最好的情况下，每次划分对一个记录定位后，要记录的左侧子序列与右侧子序列的长度相同。在具有n个记录的序列中，一次划分需要对整个待划分序列扫描一遍，所需的时间为O(n)。
设 是对n个记录的序列进行排序的时间，每次划分后，正好把划分区域分为长度相等的连个子序列，显然T(0)=T(1) =1,则有：
最坏的情况下，待排序的记录序列正序或逆序，每次划分只能得到一个比上一次划分少一个记录的子序列，（另一个子序列为空）。此时，必须经过n-1次递归调用才能把所有记录定位，而且第i趟划分需要经过n-i次比较才能找个才能找到第i个记录的位置，因此时间复杂度为
平均情况下，设轴值记录的关键码第k小（1≤k≤n）,则有：
由上式可推出如下两式：
两式相减,然后两边同除以n(n+1)得
又因为f(n)单调递减，单调有界数列极限定理，所以f(n)有界
此数称为欧拉常数，
约为 0.57721380086060651209
所以
所以
**如果有何处不当，请不吝赐教，一定多加完善。谢谢 **
参考资料：
【1】《算法设计与分析》第二版 王红梅
写一个数据结构的实验报告。要求研究数据结构的一个典型算法，有实验内容，实验步骤(代码)，分析，总结
课程设计任务书及成绩评定
课题名称
宿舍管理查询软件
Ⅰ、题目的目的和要求：
巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。
（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。
（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。
第四章详细设计
#include "fstream"
#include "iostream"
#include "cstring"
using namespace std;
/************************学生信息定义**********************************/
typedef struct Stu
{ char name[8];
char num[6];
char room[5];
}Stu;
typedef struct{
Stu *elem;
int length;
}Snode;
/*****************************学生信息处理及用户交互****************/
int Init_Stu(Snode &st); //创建学生信息
int Sort_Stu(Snode &st,intlow,int high); //快速排序算法
int Search_Stu(Snode st, char sn[]); //学生姓名二分查找并输出
void scopy(Stu &s1,Stu s2); //结构体s2赋给s1
int display(Snode st); //学生数据输出
void SavePass(); //密码问题
int quanxian(); //管理员登陆
/*******************************主函数程序****************************/
int main()
{ int suc=0;
charch1,choice,look[10];
Snode stu;
while(suc==0)
{ suc=quanxian();
if(suc==0)
{ cerr<<"您输入的用户信息不存在，请重新输入:"<
<endl<<"退出输入'y'或 'y',否则'n'或'n'："<<endl<<endl;
cin>>ch1;
if(ch1=='y'||ch1=='Y')
return0;
}
cout<
<endl<<endl<<endl<<endl;
}
cout<<"\t\t****\n\n\t\t\t欢迎进入学生宿舍管理查询系统 \n\n\t\t****\n\n";
cout<<"\t\t\t***************主菜单***************\n\n";
</endl<<endl<<endl<<endl;
</endl<