目录
前言：
一、实验内容
二、实验目的
三、实验步骤
四、实验过程
1、算法分析
2、写出伪代码
3、代码实现
4、代码详解
5、用例测试
6、复杂度分析
总结
前言：
分治法是一种将复杂问题分解为若干个相同或相似的子问题，然后递归地求解子问题，最后将子问题的解合并为原问题的解的算法设计思想。减治法是一种将复杂问题简化为规模较小的同类问题，然后递归地求解简化后的问题，最后得到原问题的解的算法设计思想。分治法和减治法都是利用递归技术实现的算法。
排序是计算机科学中最基本也最重要的问题之一，它的目的是将一组无序的数据按照某种规则排列成有序的数据。排序中有许多经典的分治法和减治法的应用，例如快速排序、归并排序、堆排序等。这些排序算法都有各自的优缺点，需要根据不同的场景和需求选择合适的算法。
本实验旨在通过排序中分治法的程序设计，掌握分治法和减治法在排序问题上的应用，了解不同排序算法的原理、步骤、性能和特点，能够使用高级语言实现和测试这些排序算法，并能够分析和比较它们之间的异同。
本文中使用的语言是C语言，使用的ide是devc++
一、实验内容
给出一个初始序列，分别用归并法和快速排序两种分治法将所给序列变为有序序列，输出结果，输出是要有文字说明。请任选一种语言编写程序实现上述算法，并分析其算法复杂度
二、实验目的
（1）掌握归并排序和快速排序的划分方法；
（2）掌握归并排序和快速排序的具体分治策略；
（3）在掌握的基础上编程两种排序方法的实现过程。
三、实验步骤
1、写出伪代码进行算法描述
2、使用c++编写程序完成上述算法
3、使用测试用例对算法进行测试
4、对算法的复杂度进行分析
四、实验过程
1、算法分析
归并排序和快速排序都是分治算法的经典代表。两种算法都通过递归来实现，过程非常相似。归并排序非常稳定，但不是原地排序；快速排序，是原地排序算法，应用得更加广泛。
归并排序：将序列分成两个子序列，对每个子序列进行递归排序，然后将两个排好序的子序列合并成一个有序序列。
快速排序：选取一个基准元素，将小于等于基准元素的元素放到左边，大于基准元素的元素放到右边，然后对左右两个子序列递归进行快速排序。
2、写出伪代码
归并排序：
merge_sort(arr, p, r) if p < r q = (p + r) / 2 merge_sort(arr, p, q) merge_sort(arr, q+1, r) merge(arr, p, q, r)merge(arr, p, q, r) n1 = q - p + 1 n2 = r - q let L[1..n1+1] and R[1..n2+1] be new arrays for i = 1 to n1 L[i] = arr[p + i - 1] for j = 1 to n2 R[j] = arr[q + j] L[n1+1] = infinity R[n2+1] = infinity i = 1 j = 1 for k = p to r if L[i] <= R[j] arr[k] = L[i] i = i + 1 else arr[k] = R[j] j = j + 1快速排序：
quick_sort(arr, low, high) if low < high pivot_location = partition(arr, low, high) quick_sort(arr, low, pivot_location - 1) quick_sort(arr, pivot_location + 1, high)partition(arr, low, high) pivot_item = arr[low] left_mark = low + 1 right_mark = high done = False while not done while left_mark <= right_mark and arr[left_mark] <= pivot_item left_mark += 1 while right_mark >= left_mark and arr[right_mark] >= pivot_item right_mark -= 1 if right_mark < left_mark done = True else swap arr[left_mark] with arr[right_mark] swap arr[low] with arr[right_mark] return right_mark3、代码实现
#include <iostream>using namespace std;void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; }}void mergeSort(int arr[], int l, int r) { if (l >= r) { return; } int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r);}int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j <= high - 1; j++) { if (arr[j] < pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[high]); return (i + 1);}void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); }}int main() { // 归并排序 cout << "归并排序" << endl; cout << "请输入待排序序列长度："; int n; cin >> n; cout << "请输入待排序序列："; int a[n]; for (int i = 0; i < n; i++) { cin >> a[i]; } mergeSort(a, 0, n - 1); cout << "排序后的序列为："; for (int i = 0; i < n; i++) { cout << a[i] << " "; } // 快速排序 cout << endl << endl << "快速排序" << endl; cout << "请输入待排序序列长度："; cin >> n; cout << "请输入待排序序列："; for (int i = 0; i < n; i++) { cin >> a[i]; } quickSort(a, 0, n - 1); cout << "排序后的序列为："; for (int i = 0; i < n; i++) { cout << a[i] << " "; } return 0;}4、代码详解
上述代码实现使用C语言实现了归并排序和快速排序两种分治算法
归并排序是一种分治算法，它将待排序的序列分成两个子序列，对每个子序列进行递归排序，然后将两个排好序的子序列合并成一个有序序列。具体来说，mergeSort函数实现了归并排序。mergeSort函数的参数包括待排序数组arr、数组左端点l和右端点r。如果l>=r，则返回；否则，计算中间点m=(l+r)/2，对左半部分arr[l…m]进行递归排序，对右半部分arr[m+1…r]进行递归排序，最后将左右两个排好序的子序列合并成一个有序序列。
快速排序也是一种分治算法，它选取一个基准元素，将小于等于基准元素的元素放到左边，大于基准元素的元素放到右边，然后对左右两个子序列递归进行快速排序。具体来说，partition函数实现了快速排序。partition函数的参数包括待排序数组arr、数组左端点low和右端点high。首先选取基准元素pivot=arr[high]，然后从low到high-1遍历数组arr。如果arr[j]<pivot，则将arr[i]和arr[j]交换，并将i加1。最后将arr[i+1]和arr[high]交换，并返回i+1
5、用例测试
6、复杂度分析
归并排序：将待排序序列分成若干个子序列，每个子序列都是有序的。然后再将有序子序列合并成整体有序序列。归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。快速排序：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)。当n趋近于无穷大时，归并排序和快速排序的时间复杂度都是O(nlogn)。归并排序的时间复杂度始终都是O(nlogn)，而快速排序虽然最坏情况下时间复杂度为O(n^2)，但平均情况下时间复杂度为O(nlogn)，最坏情况发生的概率也比较小，因此应用得更加广泛
总结
这篇文章介绍了分治法和减治法的算法设计思想，以及它们在排序问题中的应用。文章提到了许多经典的分治法和减治法的应用，例如快速排序、归并排序、堆排序等。这些排序算法都有各自的优缺点，需要根据不同的场景和需求选择合适的算法。文章还介绍了本实验的目的和内容，即通过排序中分治法的程序设计，掌握分治法和减治法在排序问题上的应用，了解不同排序算法的原理、步骤、性能和特点，能够使用高级语言实现和测试这些排序算法，并能够分析和比较它们之间的异同。