用自己电脑做主机做网站/百度安装免费下载

百度文库-

百度文库-让每个人平等地提升自我

PAGE

PAGE #

实验项目一各种排序算法的性能测试

第一章：简介(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)速排序

任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排

百度文库-

百度文库-让每个人平等地提升自我

PAGE

PAGE #

序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准 元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子

序列继续进行排序，直至整个序列有序。

void quicksort^ nt a[],i nt start,i nt end) 择排序

假设待排序的列表的n个数据元素放在数组a中，第一次从n个数据元素中 找出最小的元素与a[0]交换，第二次从剩下的n-1个元素中找出最小的元素与a[1] 交换，……直到第n-1次在剩下的两个元素中找出最小的元素与 a[n-1]交换，剩 下的最后一个元素的位置就在 a[n].

选择排序算法如下：

void selectsort(i nt a[],i nt n)

百度文库-

百度文库-让每个人平等地提升自我

PAGE

PAGE #

泡排序

如果有n个数，则要进行n-1趟比较。在第1趟比较中要进行n-1次相邻元素的 两两比较，在第j趟比较中要进行n-j次两两比较。比较的顺序从前往后，经过 一趟比较后，将最值沉底(换到最后一个元素位置)，最大值沉底为升序，最小 值沉底为降序。

(1)算法的最好时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较 次数J和记录移动次数I均达到最小值：

Jmin =n-1

Imin =0 o

冒泡排序最好的时间复杂度为 0( n) o

(2 )算法的最坏时间复杂度

/

若初始文件是反序的，需要进行

n-1趟排序。每趟排序要进行n-i次关键字的比较

(1 ￡窃-1)，且每次比较