数据结构内排序实验报告.doc

1. 实验目的 1. 了解内排序都是在内存中进行的。 2. 为了提高数据的查找速度，需要对数据进行排序。 3. 掌握内排序的方法。 2. 实验内容 1. 设计一个程序exp10—1.cpp实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1 ,0}的排序过程。 1. 源程序如下所示： //文件名:exp10-1.cpp #include <stdio.h> #define MAXE 20 //线性表中最多元素个数 typedef int KeyType; typedef char InfoType[10]; typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType; void InsertSort(RecType R[],int n) //对R[0..n- 1]按递增有序进行直接插入排序 { int i,j,k; RecType temp; for (i=1;i<n;i++) { temp=R[i]; j=i-1; //从右向左在有序区R[0..i- 1] 数据结构中的内排序，是指在计算机的主存储器（内存）中完成的排序过程，它与外排序相对，后者涉及到磁盘等外部存储设备。内排序对于提高数据的查找速度至关重要，因为内存中的数据访问速度远高于外部存储，排序后的数据可以更高效地被检索。 直接插入排序是一种简单的内排序算法，它的核心思想是将未排序的元素逐个插入到已排序的部分，保持已排序部分的有序性。在给定的实验中，`exp10-1.cpp` 实现了直接插入排序。程序定义了一个结构体 `RecType`，包含一个整型的关键字 `key` 和一个字符数组 `data`。`InsertSort` 函数接受一个 `RecType` 类型的数组和其大小 `n`，通过循环遍历数组，将每个元素与已排序的部分比较并插入合适的位置。在每次插入操作后，程序还会输出当前的排序状态，以便观察排序过程。 希尔排序是改进版的插入排序，由希尔（Shell）提出，通过设置间隔（增量）将待排序序列划分为若干子序列，然后对子序列进行插入排序，逐步减少间隔直至为1，这样可以减少元素移动的次数，提高排序效率。在 `exp10-2.cpp` 文件中，`ShellSort` 函数实现了希尔排序，初始增量为 `n/2`，然后每次减半，直到增量为0，完成整个排序过程。 在实验中，两种排序算法都被应用于排序数组 `{9,8,7,6,5,4,3,2,1,0}`。通过运行程序，可以看到每一步的排序状态以及最终的排序结果，直观展示了两种排序算法的工作原理。 总结来说，这个实验报告涵盖了数据结构中的两个基础排序算法：直接插入排序和希尔排序。直接插入排序适用于小规模或部分有序的数据，而希尔排序则适合于处理中到大规模数据，通过间隔排序策略提高了效率。这些排序算法的理解和实践对于学习数据结构和算法，提升编程能力具有重要意义。