专业班级：姓 名：学 号：设计时间：指导教师：
计数据结构课程设
排序算法比较分析
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 ；后部分数组的元素为除第一个元素的所有元素，为待排序或待插入元素，我们这里叫 arr2 。
排序时使用二层循环：第一层对 arr2 进行循环，每次取后部分数组（待排序数组）里的第一个元素（我们称为待排序元素或称待插入元素） e1 ，然后在第二层循环中对 arr1 （已排好序的数组）从第一个元素往后进行循环，查到第一个大于待插入元素（如果是升序排列）或第一个小于待插入元素（如果是降序排列） e2 ，然后对 arr1 从 e2 元素开始往后的所有元素向后移，最后把 e1 插入到原来 e2 所在的位置。这样反复地对 arr2 进行循环，直到 arr2 中所有的待插入的元素都插入到 arr1 中。
4、快序排序：QuickSort()
基本思想：首先在r[1..n]中，确定一个r[i]，经过比较和 移动，将r[i]放到\中间\某个位置上，使得r[i]左边所有记录 的关键字小于等于r[i].key，r[i]右边所有记录的关键字大于等 于r[i].key。以r[i]为界,将文件划分为左、右两个子文件。
用同样的方法分别对这两个子文件进行划分, 得到4个更小 的子文件。继续进行下去,使得每个子文件只有一个记录为止, 便得到原文件的有序文件。
例. 给定文件(20,05,37,08,63,12,59,15,44,08)，选 用第1个元素20进行划分:
5、归并排序：MegeSort()
假定文件(r[1],r[2],...,r[n])中记录是随机排列的,进行
2-路归并排序，首先把它划分为长度均为1的n个有序子文件， 然后对它们逐步进行2－路归并排序。其步骤如下：
第1趟：从r[1..n]中的第1个和第2个有序子文件开始,调用 算法merge,每次归并两个相邻子文件,归并结果放到y[1..n]中。 在y中形成 ?n/2? 个长度为2的有序子文件。若n为奇数,则y中最 后一个子文件的长度为1。
第2趟：把y[1..n]看作输入文件,将 ?n/2? 个有序子文件两 两归并,归并结果回送到r[1..n]中,在r中形成 ??n/2?/2?个长度为4的有序子文件。若y中有奇数个子文件，则r中最后一个子文 件的长度为2。
共计经过 ?log2n? 趟归并,最后得到n个记录的有序文件。
6、堆排序：HeapSort()
堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
1、N（N>1）个节点的的完全二叉树从层次从左自右编号，最后一个分枝节点（非叶子节点）的编号为 N/2 取整。2、且对于编号 i（1<=i<=N）有：父节点为 i/2 向下取整；若2i>N，则节点i没有左孩子，否则其左孩子为2i；若2i+1>N，则没有右孩子，否则其右孩子为2i+1。3、这里使用完全二叉树只是为了好描述算法，它只是一种逻辑结构，真真在实现时我们还是使用数组来存储这棵二叉树的，因为完全二叉树完全可以使用数组来存储。
堆排序其实最主要的两个过程：第一步，创建初始堆；第二步，交换根节点与最后一个非叶子节
从最后一个非叶子节点为开始向前循环每个会支节点，比较每个分支节点与他左右子节点，如果其中某个子节点比父节点大，则与父节点交换，交换后原父节点可能还小于原子节点的子节点，所以还需
对原父节点进行调整，使用原父节点继续下沉，直到没有子节点或比左右子节点都大为止，调用过程可通过递归完成。当某个非叶子节点调整完毕后，再处理下一个非叶子节点，直到根节点也调整完成，这里初始堆就创建好了，这里我们创建的是大顶堆，即大的元素向树的根浮，这样排序最后得到的结果为升序，因为最大的
将树中的最后一个元素与堆顶元素进行交换，并从树中去掉最后叶子节点。交换后再按创建初始堆的算法调整根节点，如此下去直到树中只有一个节点为止。
数据结构课程设计 实验报告 心得体会 C++
