数据结构实验报告（四）——查找和排序算法

实验目的

1. 掌握顺序查找技术和拆半查找技术以及部分排序算法的设计思想；

2. 掌握查找、部分排序算法的实现与执行过程。

实验原理

查找算法

1.顺序查找：从数组第一个元素开始逐个比较，找到后返回相应下标。

2.折半查找：从数组中间开始比较，如果需查找值比中间值大，则在中间值右边继续找，重复上述步骤，直至找到该元素；如果需查找值比中间值小，则在中间值左边继续找，重复上述步骤。

3. 二叉查找树：先利用递归方式构建一棵二叉查找树，使得左子树所有结点都比根节点小，右子树所有结点都比根节点大。查找时，通过与根节点比较大小即可分别对应进入左右子树，依次递归，直至找到该元素。

排序算法

1. 直接插入排序：假设把数组分为两部分，一部分是初始时是R1[1]，另一部分是R2[2……n-1],每次将R2的第一个元素抽出来与R1中的数进行比较，找到合适的位置插入，然后把这个元素加入R1，依次循环直到R2的数组为空。

2. 折半插入排序：与直接插入类似，只不过在寻找插入位置时采用了折半方法。

3. 希尔排序：设置初始增量为n/2（n为数组长度），将数组划分为n/2个小数组,然后对每个小数组进行直接插入排序，一轮结束后，再将增量/2，重复上述步骤，直至增量=0，即排序完成。

4. 冒泡排序：设置双重循环，相邻元素之间比较大小根据大小进行移动。并添加标志，如果剩下的序列中没有元素发生移动，则表明数组元素已排序完成，可以提前退出。

5. 快速排序：初始时，将数组的第一个元素作为标记，然后扫描数组，将比标记小的数移到标记左边，比数组大的数移到标记右边，最后返回标记的位置；所以以标记为中心，数组被划分为了两部分，假设为左右子表，接着对左右子表用递归方式重复上述步骤即可完成排序。

6. 选择排序：设置双重循环，初始时假设第一个元素是最小值，向后扫描找是否有比第一个更小的元素，如果有则记录它的下标，直到找到真正的最小值，然后把最小值和第一个元素交换位置；第二趟排序则设第二个元素是最小值，重复上述步骤，即可完成排序。

7. 堆排序：将数组看作是一棵完全二叉树的顺序存储结构。初始时，需要构建大根堆。由完全二叉树性质可得，序号大于n/2的结点都是叶子结点，叶子结点满足堆，所以只需要对序号小于n/2的这部分结点进行筛选调整。之后再反复重建堆即可完成排序。

8. 归并排序：初始时，设数组分为n个 部分，所以每个部分都是有序的；每一趟排序将两两小数组合并（合并时要比较大小进行排序）；最后合并得到一个数组即为有序数组，完成排序。

实验源码

查找

顺序表查找

int SeqSearch(int arr[], int n, int x){//顺序表查找
    cout