各种算法的性能分析

《各种算法的性能分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验项目一各种排序算法的性能测试第一章：简介（Introduction）排序就是将一个记录的无序序列调整成为一个有序序列的过程。在对记录进行排序的时候，需要选定一个信息作为排序的依据，例如，可以按学生姓名对学生记录进行排序，这个特别选定的信息称为关键码。排序的主要目的是为了进行快速查找，这就是为什么字典、电话薄和班级名册都是排好序的。在数据结构课程中，我们已经学过了几种内部排序算法，没有一种排序算法在任何情况下都是最好的解决方案，有些排序算法比较简单，但速度相对比较慢；有些排序算法速度比较快，但却很复

2、杂。1.冒泡排序：设想被排序的数组R[1..N]垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"（交换位置），如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行n(n-1）/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。2.快

3、速排序：快速排序（quicksort）是对冒泡排序的一种改进。由C.A.R.Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。3.选择排序：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。通俗的解释：对比数组中前一个

4、元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。第二章：算法定义（Algori

5、thmSpecification）1.冒泡排序通过对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元），就象水底下的气泡一样逐渐向上冒。冒泡排序算法如下：voidbubblesort(inta[],intn)//冒泡排序C语言描述，待排序的元素放在数组a中{inti,j;inttemp;for(i=0;ii;j--){if(a[j-1]>a[j])

6、{temp=a[j-1];a[j-1]=a[j];a[j]=temp;}}}}2.快速排序任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。voidquicksort(inta[],intstart,intend)//快速排序{inti,j,mid;i=start;j=end;mid=a[i];while(sta

7、rt>=end)return;while(imid)j--;if(i

8、次从n个数据元素中找出最小的元素与a[0]交换，第二次从剩下的n-1个元素中找出最小的元素与a[1]交换，……直到第n-1次在剩下的两个元素中找出最小的元素与a[n-1]交换，剩下的最后一个元素的位置就在a[n].选择排序算法如下：voidselectsort(inta[],intn)//选择排序{inti,j;intmin,temp;for(i=0;i