实验项目一各种排序算法的性能测试
第一章:简介(Introduction)
排序就是将一个记录的无序序列调整成为一个有序序列的过程。在对记录进行排序的时候,需要选定一个信息作为排序的依据,例如,可以按学生姓名对学生记录进行排序,这个特别选定的信息称为关键码。
排序的主要目的是为了进行快速查找,这就是为什么字典、电话薄和班级名册都是排好序的。
在数据结构课程中,我们已经学过了几种内部排序算法,没有一种排序算法在任何情况下都是最好的解决方案,有些排序算法比较简单,但速度相对比较慢;有些排序算法速度比较快,但却很复杂。
1.冒泡排序:
设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"漂浮"(交换位置),如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。若记录序列的初始状态为"正序",则冒泡排序过程只需进行一趟排序,在排序过程中只需进行n-1次比较,且不移动记录;反之,若记录序列的初始状态为"
逆序",则需进行n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。
2.快速排序:
快速排序(quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
3.选择排序:
每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。通俗的解释:对比数组中前一个元素跟后一个元素的大小,如果后面的元素比前面的元素小则用一个变量k来记住他的位置,接着第二次比较,前面“后一个元素”现变成了“前一个元素”,继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标),等到循环结束的时候,我们应该找到了最小的那个数的下标了,然后进行判断,如果这个元素的下标不是第一个元素的下标,就让第一个元素跟他交换一下值,这样就找到整个数组中最小的数了。然后找到数组中第二小的数,让他跟数组中第二个元素交换一下值,以此类推。
第二章:算法定义(Algorithm Specification)
1.冒泡排序
通过对待排序序列从后向前(从下标较大的元素开始),依次比较相邻元素的排序码,若发现逆序则交换,使排序码较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单元),就象水底下的气泡一样逐渐向上冒。
冒泡排序算法如下:
void bubblesort(int a[],int n)//冒泡排序C语言描述,待排序的元素放在数组a中
{
int i,j;
int temp;