排序算法比较分析 专业班级：08 软件工程2 班 姓 名： 汪伟 学 号： 08010xxxxx 设计时间： 2010-9-15— -2010-9-27 指导教师： 杨薇薇 数据结构课程设计 课程设计报告的内容 一、题目：排序算法比较 1、 设计目的 1． 掌握各种排序的基本思想。 2． 掌握各种排序方法的算法实现。 3． 掌握各种排序方法的优劣分析及花费的时间的计算。 4． 掌握各种排序方法所适应的不同场合。 2、 设计内容和要求 利用随机函数产生30000 个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间 二、 运行环境（软、硬件环境） 软件环境：Vc6.0 编程软件 运行平台： Win32 硬 件： 普通个人pc 机 三、 算法设计的思想 1 、冒泡排序：bubbleSort() 基本思想: 设待排序的文件为r[1..n] 第 1 趟 (遍 )：从r[1]开始,依次比较两个相邻记录的关键字 r[i].key 和 r[i+1].key ,若 r[i].key >r[i+1].key，则交换记录 r[i]和 r[i+1]的位置；否则,不交换。 (i=1,2,...n-1) 第 1 趟之后,n 个关键字中最大的记录移到了r[n]的位置上。 第 2 趟：从r[1]开始,依次比较两个相邻记录的关键字 r[i].key 和 r[i+1].key ,若 r[i].key >r[i+1].key，则交换记录 r[i]和 r[i+1]的位置；否则,不交换。 (i=1,2,...n-2) 第 2 趟之后,前 n-1 个关键字中最大的记录移到了r[n-1]的位 置上，作完n-1 趟 ,或者不需再交换记录时为止。 2、选择排序：selSort() 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序不像冒泡排序算法那样先并不急于调换位置，第一轮（ k=1） 先从array [k]开始逐个检查，看哪个数最小就记下该数所在的位置于minlIndex 中，等一轮扫描完毕，如果找到比array [k-1]更小的元素，则把array [minlIndex ]和 a[k-1]对调，这时array [k]到最后一个元素中最小的元素就换到了array [k-1]的位置。 如此反复进行第二轮、第三轮…直到循环至最后一元素 3、直接插入排序 ： insSort() 在已经排好序的序列中查找待插入的元素的插入位置，并将待插入元素插入到有序列表中的过程。 将数组分成两部分，初始化时，前部分数组为只有第一个元素，用来存储已排序元素，我们这里叫 arr1 ； 后部分数组的元素为除第一个...
