当前位置：首页 > news >正文

算法分析与设计实验1：实现两路合并排序和折半插入排序

news 2025/7/7 10:58:14

实验原理

（一）两路合并排序：

一种基于分治法的排序算法，其基本思想是将待排序的数组分成两个子数组，分别进行排序，然后将两个已排序的子数组合并成一个完整的排序数组。

基本环节

（1）分解：

将待排序的数组从中间分成两个子数组，如果数组长度为奇数，则尽量平均分配。

对这两个子数组递归地执行分解操作，直到每个子数组只包含一个元素（自然排序）。

（2）递归求解：

递归地对每个子数组进行排序。

（3）合并：

将两个已排序的子数组合并成一个完整的排序数组。在合并过程中，通过比较两个子数组的元素，依次将较小的元素放入新的数组中，直到所有元素都被合并。

算法步骤

（1）如果数组长度为1，返回数组（已排序）。

（2）将数组从中间分成两个子数组。

（3）递归地对两个子数组进行排序。

（4）合并两个已排序的子数组，得到排序后的数组。

时间复杂度

最好、最坏、平均情况下都是 O(nlogn)。

（二）折半插入排序：

一种改进的插入排序算法，利用折半查找（二分查找）来确定插入位置，从而减少了比较次数，提高了效率。

A.基本环节

（1）初始：

假设数组的第一个元素已排序。

迭代：
1. 从数组的第二个元素开始，依次取出每个元素，记为key。
2. 使用二分查找在已排序部分找到key应该插入的位置。
3. 将已排序部分的元素依次向后移动，为key腾出位置。
4. 将key插入到正确的位置。

B.二分查找步骤：

初始化 low 和 high 指针，分别指向已排序部分的开始和结束。
计算中间位置 mid。
如果 key 小于 mid 位置的元素，则 high 指针移动到 mid - 1。
如果 key 大于等于 mid 位置的元素，则 low 指针移动到 mid + 1。
重复步骤2-4，直到找到 key 的插入位置（即 low 的位置）。

C.插入步骤：

从 low 位置开始，将已排序部分的元素依次向后移动一位。
将 key 插入到 low 位置。

D.算法步骤：

从数组的第二个元素开始，依次取出每个元素 key。
使用二分查找确定 key 在已排序部分的插入位置。
将已排序部分的元素依次向后移动，为 key 腾出位置。
将 key 插入到正确的位置。
重复步骤1-4，直到所有元素都被排序。

E.时间复杂度：

（1）最好情况下是 O(nlogn)（数组已排序）。

（2）最坏情况下是 O(n2)（数组逆序）。

（3）平均情况下接近 O(n2)。

流程分析

（一）两路合并排序：

输入：一个无序的数组。

流程：

1.分解阶段：

（1）检查数组长度。如果长度为1，则数组已排序，无需进一步操作。

（2）找到数组的中间位置，将数组分成两个子数组。

（3）递归地对两个子数组执行分解操作，直到每个子数组只包含一个元素。

2.递归求解阶段：

（1）这一步实际上在分解阶段已经隐含完成，因为分解过程本身就是递归地进行的。

（2）每个子数组在分解到只包含一个元素时，自然成为已排序的子数组。

3.合并阶段：

（1）从最底层的递归开始，逐层向上合并已排序的子数组。

（2）合并时，使用两个指针分别指向两个子数组的起始位置，比较两个指针所指的元素，将较小的元素放入新的数组中，并移动相应的指针。

（3）重复上述步骤，直到两个子数组中的所有元素都被合并到新的数组中。

（4）最终，合并后的数组就是排序后的数组。

输出：一个有序的数组。

（二）折半插入排序

输入：一个无序的数组。

流程：

1.初始化：

假设数组的第一个元素已排序，作为已排序部分的起点。

2.迭代阶段：

（1）从数组的第二个元素开始，依次取出每个元素作为 key。

（2）使用二分查找在已排序部分找到 key 的插入位置。二分查找时，通过比较 key 和已排序部分中间位置的元素，不断调整搜索范围，直到找到插入位置。

（3）将已排序部分的元素从插入位置开始依次向后移动一位，为 key 腾出位置。

（4）将 key 插入到正确的位置，此时已排序部分增加一个元素。

3.重复迭代：

对数组的剩余元素重复步骤2，直到所有元素都被排序。

输出：一个有序的数组。

程序实现

（1）两路合并排序：

#include<stdio.h>
#define Max_ 10void Show(int  arr[], int n)
{int i;for (i = 0; i < n; i++)printf("%d  ", arr[i]);printf("\n");
}void Merge(int array[], int left, int m, int right)
{int aux[Max_] = { 0 }; int i; int j; int k; for (i = left, j = m + 1, k = 0; k <= right - left; k++) {if (i == m + 1){aux[k] = array[j++];continue;}if (j == right + 1){aux[k] = array[i++];continue;}if (array[i] < array[j]){aux[k] = array[i++];}else{aux[k] = array[j++];}}for (i = left, j = 0; i <= right; i++, j++){array[i] = aux[j];}
}void MergeSort(int array[], int start, int end)
{if (start < end){int i;i = (end + start) / 2;MergeSort(array, start, i);MergeSort(array, i + 1, end);Merge(array, start, i, end);}
}int main()
{int arr_test[Max_] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 };printf("初始的数组为：");Show(arr_test, Max_);MergeSort(arr_test, 0, Max_ - 1);printf("排序后数组为：");Show(arr_test, Max_);return 0;
}

（2）折半插入排序：

#include"stdio.h"
void BinInsertSort(int arr[], int n);int main()
{int arr[] = { 4, 1, 3, 5, 4, 2 };int n = 6;printf("初始数组为：");for (int j = 0; j < n; j++){printf("%5d", arr[j]);}printf("\n");BinInsertSort(arr, n);return 0;
} 
void BinInsertSort(int arr[], int n)
{int i, j, lo, mid, hi, t;if (arr[1] < arr[0]){t = arr[0];arr[0] = arr[1];arr[1] = t;}printf("第1次排序 ：");for (j = 0; j < n; j++){printf("%5d", arr[j]);}printf("\n");for (i = 2; i < n; i++){t = arr[i];lo = 0;hi = i - 1;while (lo <= hi){mid = int((lo + hi) / 2);if (t < arr[mid]){hi = mid - 1;}else if (t > arr[mid]){lo = mid + 1;}else{hi = mid;break;}}for (j = i - 1; j >= hi + 1; j--){arr[j + 1] = arr[j];}arr[hi + 1] = t;printf("第%d次排序 : ", i);for (j = 0; j < n; j++){printf("%5d", arr[j]);}printf("\n");}
}