数据结构实验报告八种排序算法实验报告一、 实验容编写关于八种排序算法的 C 语言程序，要求包含直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序和基数排序。二、 实验步骤 各种部排序算法的比较：1. 八种排序算法的复杂度分析（时间与空间）。2. 八种排序算法的 C 语言编程实现。3. 八种排序算法的比较，包括比较次数、移动次数。三、 稳定性，时间复杂度和空间复杂度分析 比较时间复杂度函数的情况：时间复杂度函数 O(n)的增长情况所以对 n 较大的排序记录。一般的选择都是时间复杂度为 O(nlog2n)的排序方法。时间复杂度来说：(1)平方阶(O(n2))排序 各类简单排序:直接插入、直接选择和冒泡排序； (2)线性对数阶(O(nlog2n))排序 快速排序、堆排序和归并排序； (3)O(n1+§))排序,§是介于 0 和 1 之间的常数。 希尔排序(4)线性阶(O(n))排序 基数排序，此外还有桶、箱排序。说明：当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至 O（n）；而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为 O（n2）；原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。 稳定性：排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。 稳定性的好处：排序算法假如是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，假如排序算法稳定，可以避开多余的比较；稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序四、 设计细节排序有部排序和外部排序，部排序是数据记录在存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。我们这里说说八大排序就是部排序。1. 插入排序---直接插入排序（Straight lnsertion Sort）基本思想： 将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增 1 的有序表。即：先将序列的第 1 个记录看成是一个有序的子序列，...
