分治法与递归算法实践：全排列、二分查找、合并排序

一、实验目的

了解分治法思想；
掌握递归算法的思想与程序编写；
熟练使用二分查找法实现代码编写；
熟练使用全排序实现代码编写；
熟练使用合并排序实现代码编写；

二、实验内容

n个数的全排列问题。
在一个给定的n个元素的有序序列中查找出与给定关键字x相同的元素的具体位置。即输入一个n个元素的序列，其中n个元素从小到大的顺序排列，查找是否存在给定的值x.(用二分查找法）。
改写二分搜索算法：设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。
消除合并排序算法中的递归：给定数组a，将数组a中相邻元素两两配对，用合并算法将他们排序，构成n/2组长度为2的排好序的子数组段，然后再将它们排序成长度为4的排好序的子数组段，如此继续下去，直至整个数组排好序。

三、实验步骤

n个数的全排列问题
- 定义一个函数permute，用于实现全排列的递归调用
- 在permute函数中，使用一个循环遍历数组，将每个元素与当前位置进行交换，并递归调用permute函数
- 在递归调用之后，将交换回来的元素再次交换回去，以保持原数组的顺序
- 在主函数中调用permute函数，传入数组和数组长度
二分查找法
- 定义一个函数binarySearch，用于实现二分查找
- 在函数中，使用两个指针分别指向数组的起始位置和结束位置
- 使用一个循环，不断将指针移到中间位置，并比较中间位置的元素与给定关键字x的大小
- 如果中间位置的元素等于x，则返回该位置
- 如果中间位置的元素大于x，则将结束指针移到中间位置的前一个位置
- 如果中间位置的元素小于x，则将起始指针移到中间位置的后一个位置
- 循环结束后，如果找到了与x相同的元素，则返回该位置，否则返回-1
改写二分搜索算法
- 定义一个函数binarySearch2，用于实现改写后的二分搜索算法
- 在函数中，使用两个指针分别指向数组的起始位置和结束位置
- 使用一个循环，不断将指针移到中间位置，并比较中间位置的元素与给定关键字x的大小
- 如果中间位置的元素等于x，则返回该位置
- 如果中间位置的元素大于x，则将结束指针移到中间位置的前一个位置
- 如果中间位置的元素小于x，则将起始指针移到中间位置的后一个位置
- 循环结束后，如果找到了与x相同的元素，则返回该位置，否则返回起始指针和结束指针的位置
消除合并排序算法中的递归
- 定义一个函数mergeSort，用于实现消除递归的合并排序算法
- 在函数中，使用一个循环，控制每次合并的子数组段的长度
- 在循环中，使用两个指针分别指向当前子数组段的起始位置和结束位置
- 使用一个循环，将两个子数组段进行合并排序，并将排序结果放入一个新的数组中
- 循环结束后，将新数组中的元素复制回原数组

四、实验结果

n个数的全排列问题
- 输入：[1, 2, 3]
- 输出：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
二分查找法
- 输入：[1, 2, 3, 4, 5], x = 3
- 输出：2
改写二分搜索算法
- 输入：[1, 2, 3, 4, 5], x = 3
- 输出：2, 2
消除合并排序算法中的递归
- 输入：[5, 4, 3, 2, 1]
- 输出：[1, 2, 3, 4, 5]