目录
前言:
一、实验内容
二、实验目的
三、实验步骤
四、实验过程
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_mark
3、代码实现
#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),最坏情况发生的概率也比较小,因此应用得更加广泛
总结
这篇文章介绍了分治法和减治法的算法设计思想,以及它们在排序问题中的应用。文章提到了许多经典的分治法和减治法的应用,例如快速排序、归并排序、堆排序等。这些排序算法都有各自的优缺点,需要根据不同的场景和需求选择合适的算法。文章还介绍了本实验的目的和内容,即通过排序中分治法的程序设计,掌握分治法和减治法在排序问题上的应用,了解不同排序算法的原理、步骤、性能和特点,能够使用高级语言实现和测试这些排序算法,并能够分析和比较它们之间的异同。