王帅-E11314150-排序算法.docx

课程设计报告课程名称: 《数据结构》课程设计课程设计题目: 排序算法姓名: ** 院系: 计算机学院专业: 计算机科学与技术年级:2013 级学号:** 指导教师:** 2015 年*月**日(1) 熟练使用 C 语言编写程序,解决实际问题; (2) 了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力; (3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; (4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 2 需求分析随机产生 1000000 数值在 0~29999 个数,并用四种不同的方法进行排序,将结果在文件中显示出来,并比较四种排序的区别,分析各自的特点。 3 课程设计报告内容 概要设计此次题目分为 4 部分,要用 4 中不同的排序方法进行排序,并对这 4 中排序进行比较。(1) 插入排序: 插入排序的基本思想就是对于新输入的数,与前面已存在的数组中的数进行比较, 选择合适的位置将其插入其中。设计关键字 key 用来存放每次读取的数,在数组的范围内,从后往前依次与数组中的值进行比较,直到找到不比 key 大的数,那些比 key 大的数则依次往后进行移位。如此就可以完成一个数的插入,对于每一个数执行上述操作就可得到排序好的数组。(2) 堆排序: 堆排序的基本思想就是对于要进行排序的数,建立最大堆,根据最大堆的特性(根结点的值不小于左右子结点的值)由此从上到下使得整个要进行排序的数组基本有序,然后在此基础上将最大的依次提取出来,从数组末尾开始,依次往前排。最终就得到完全有序的的数组,即完成排序。(3) 快速排序: 运用分治法来具体地实现快速排序,对于程序中的待排序的元素,将最后一个元素设为 key 与所有元素进行比较, 若发现比 key 大则继续往后进行比较, 若发现比 ke y 小,则将较小元素和第一个不比 key 小的元素交换位置,这样依次执行,到最后交换 key 和第一个不比 key 小的元素的位置,此时, key 左边的元素全部小于 key , 右边的全部不小于 key ,这就相当于已经将 key 的位置找到了,然后对 key 左右两侧的子数组重复上述操作,直到排好所有的元素。则排序就完成。(4) 计数排序: 计数排序的思想很简单,即就是开辟很大的数组,在以元素的值为数组下标的位置进行计数,看原来的数组中此元素值的数有几个,然后用数组前一个元素的值与当前位置元素相加,处理元素在将要排好序的新数组中的位置,然后从后往前,将原数组的值放到相应的新的数组对应的位置上。 详细设计为了可以进行对比,在以下 4 种排序算法的设计过程中,都要输出两次,一次是随机产生的未进行排序的数, 将其输出到” ”中, 然后将排序之后的有序数组中的元素按顺序输出到” ”中。此处的输出到 txt 文档均采用 fprint f 函数, 随机产生的 100000 0 个数均采用 rand() 函数,算法的计时均采用 clock() 函数。(1 )插入排序: 插入排序算法的主要步骤就是进行比较并插入,从数组中的第二个元素开始,首先将此元素值付给关键字 key , 然后用 key 与数组前面的元素进行比较, 若是前面的元素大于关键字, 就将前面的元素后移一位, 在数组范围内, 直到找到某个元素不大于关键字, 就将关键字插入到此元素后面,如此反复进行操作,就可以将原数组中的元素全部排序(2 )堆排序: 由于堆排序中要用到根节点的左右子树来进行比较排序, 由于 L=2*i,R=2*i+1 因此要从数组的第 1 号单元开始进行比较,所以开始时开辟 N+1 个空间进行排序。用函数 MAX_PEAPIFY(int *A,int i) 来判断 A 数组中的 i 结点是否满足 i 结点不小于它的左右结点, 若不满足, 则进行替换, 将三个数中最大的一个替换到根节点上, 如此对所有结点执行此操作, 可得基本有序的数组。此时最大值在数组的开头, 然后将最大的与数组最末尾的值进行替换,此时最大数排到了数组的末尾,在调用 MAX_PEAPIFY(int *A,int i) 函数对前面的结点依次进行检查整理。这时除了最后结点之外的最大结点就到了数组开始位置, 在于数组中倒数第二位置的元素进行替换, 就这样依次执行, 最终可得到从后往前依次递减的有序数组, 即完成排序。(3 )快速排序: 首先要设置两个位置的标记 i和j,i 数组第一个元素之前,每次比较,发现比 key 小的值, 就将 i+1 ,用j 定位目前比较的位置, 从左往右依次进行比较, 若发现比 key 小的值, 用i和j 的标记将此值与第一个不比 key 小的值进行位置互换, 就这样一直比较, 最终将