数据结构课程设计-排序

《数据结构课程设计-排序》由会员分享，可在线阅读，更多相关《数据结构课程设计-排序（9页珍藏版）》请在毕设资料网上搜索。

1、五五. .综合排序综合排序 1、设计目的 对于数据处理工作，排序是其最基本的运算之一。在当今的计算机系统中， 花费在排序上的时间占系统 CPU 运行时间的很大比重（约 20%60%）。为了提高 计算机的工作效率，人们提出了各种各样的排序算法，这些算法充分地展示了算 法设计的某些重要原则和高超技巧。 本设计旨在对一些常用的内部排序算法作深 入地探讨和理解，通过比较，评价各算法的优劣。 2、问题描述 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶， 或大 概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次 数，以取得直观感受。 3、设计要求 (1) 实现基本排序方法

2、：直接插入排序、希尔排序、冒泡、快速排序、直接选 择、堆排序； （我们要求至少实现三种算法）(2) 对每种基本排序方法尽量给出 改进算法； (3) 利用随机函数产生不少于 100 个随机整数，利用直接插入排序、 希尔排序、冒泡、快速排序、直接选择、堆排序等排序方法进行递增排序，统计 各算法的关键字比较次数和关键字移动次数； (4) 以菜单的形式组织程序各功 能； (5) 至少要用 5 组不同的输入数据作比较，比较的指标为有关键字参加的 比较次数和关键字移动次数（关键字交换计为 3 次移动）； (6) 观察所有实验 结果并汇集成表格加以总结。 4、相关知识介绍 将一个数据元素（或记录）的任意序列

3、，重新排列成一个按关键字有序的序 列叫排序。排序的目的是为了便于查找和处理，提高数据检索的效率。排序问题 是要把若干无序数据元素序列排成一个有序序列。 因此排序问题的数据元素集合 是线性结构。在这个数据元素集合上也允许存取任意位置的数据元素，所以排序 问题的数据结构是线性表。 任何算法的实现方法都和算法所处理数据元素的存储 结构有关。 线性表的存储结构有顺序表和链表两种， 因为数组具有随机存取特性， 而链表不具备，所以排序算法基本上是基于顺序表设计的。排序的方法很多，若 按待排序记录所在位置可分为外部排序（排序过程中需对外存进行访问的排序） 和内部排序（待排序记录存放在内存）；按排序依据的不同

4、原则来看，内部排序 又可分为插入排序 （直接插入排序、 折半插入排序、 希尔排序等）、 交换排序 （冒 泡排序、快速排序等）、选择排序（简单选择排序、堆排序）、归并排序（2- 路归并排序）和基数排序。因为排序过程常包括两个基本操作：比较两个关键字 大小；将记录从一个位置移动到另一个位置，所以我们通过统计各算法的关键字 比较次数和关键字移动次数的方法，直观地感受不同算法的时间复杂度。 5、课程设计分析 插入排序的基本思想是， 每次将一个待排序的记录按其关键字的大小插入到前面 已经排好序的有序序列中的适当位置，直到全部记录插入完成为止。（1）直接 插入排序是一种简单的排序方法，它的基本思想是将待插入记录 Ri与有序区 的记录 Rj从右向左(j=i-1,i-21)比较，若 Rj Ri则 Rj右移一个位置 到 Rj+1；否则，将 Ri插入到 j+1 处。在改进算法中引进附加记录 R0称为 监视哨，其作用有两个：在进入查找（插入位置）循环之前，它保存了 Ri 的副本，保证不至于因记录后移而丢失 Ri的内容；在查找循环中，避免检 测下标变量