c语言程序设计.docx

2014-2015 学年 第 2 学期
学号
《高级语言程序设计
课程设计报告
排序算法
指导教师:
计算机与信息工程系
2015 年 3 月 26 日
需求分析 第一章程序内容及要求
冒泡排序 选择排序 插入数和第 3 个数，将小数放前，大数放后，如此继 续，直至比较 最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的 数放到了最后。在第二趟： 仍从第一对数开始比较（因为可能由于第 2 个数和第
3 个数的交换，使得第 1 个数不再小于第 2 个数），将小数放前，大数放后, 直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒 数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数） 下去，重复 。如此 以上过程，直至最终完成排序。用二重循环实现，外循环变量设为 i， 内循环变量设
为j。假如有10个数需要进行排序，则外循环重复9次，内循环 依次重复9, 8, ...，1次。每 次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1 ]标识，i的值依次 为 1,2,...,9 ，对于每一个 i,j 的值依次为 1,2,...10-i 。冒泡排序算法的性能
选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放
在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳 定
的排序方法。
基本思想:
n 个记录的文件的直接选择排序可经过 n-1 趟直接选择排序得到有序结果:
初始状态：无序区为R[1..n]，有序区为空。
第1趟排序 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1] 交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序 区。……③
第i趟排序 第i趟排序开始时，当前有序区和无序区分别为 R[1..i-1]和R（1
该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个
记录 R 交换，
使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新
无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
选择排序法的第一层循环从起始元素开始选到倒数第二个元素，主要是在每次进 入的第二层循 环之前， 将外层循环的下标赋值给临时变量，接下来的第二层循环中，如果发现有比这个 最小
位置处的元素更小的 元素,则将那个更小的元素的下标赋给临时变量，最后,在二层循环退出 后，如果 临时变量改变，则说明, 有比当前外层循环位置更小的元素，需要将这两个元素交换
插入排序
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一
个数，但要求插入后此数据序列仍然有序， 这个时候就要用到一种新的排序方法
--插入排序法，插入排序的基本操作就是将一个数据插入到已经排好序的有序数
据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序,
时间复杂度为0（门八 2）。是稳定的排序方法。插入算法把要排序的 数组分成两部 分:
第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个 空间才有插入的
位置），而第二部分就只