长春市快速建站网站,网站建设大赛海报,昆山网站优化建设,wordpress用户登陆1. 介绍
归并排序#xff08;Merge Sort#xff09;是一种采用分治法#xff08;Divide and Conquer#xff09;策略的排序算法。该算法首先将已有序的子序列合并#xff0c;得到完全有序的序列。在归并排序中#xff0c;合并操作是将两个有序表合并成一个有序表的过程。…1. 介绍
归并排序Merge Sort是一种采用分治法Divide and Conquer策略的排序算法。该算法首先将已有序的子序列合并得到完全有序的序列。在归并排序中合并操作是将两个有序表合并成一个有序表的过程。
归并排序的原理是将数组不断分成两半直到每个子数组只有一个元素然后将这些子数组合并成一个有序的数组。合并操作需要两个子数组都是有序的因此归并排序需要先对数组进行分解然后再进行合并。
以下是归并排序的实现步骤
将待排序的数组不断分成两半直到每个子数组只有一个元素。这一步被称为分解。对每个子数进行排序可以使用任何有效的排序算法。这一步被称为求解。将所有已排序的子数组合并成一个有序的数组。这一步被称为合并。
归并排序的时间复杂度是 O(n log n)其中 n 是数组的大小。这是因为它需要将数组分解成两半然后再合并成一个有序的数组。归并排序的空间复杂度是 O(n)因为在合并过程中需要额外的空间来存储临时变量。
2. 代码实现
#include iostream
using namespace std; // 归并操作将有序数组a和b合并成一个有序数组c
void merge(int a[], int b[], int c[], int m, int n) { int i 0, j 0, k 0; // i、j、k分别指向数组a、b、c的起始位置 while (i m j n) { // 比较a和b中的元素将较小的元素放入c中 if (a[i] b[j]) { c[k] a[i]; } else { c[k] b[j]; } } while (i m) { // 将数组a中剩余的元素放入c中 c[k] a[i]; } while (j n) { // 将数组b中剩余的元素放入c中 c[k] b[j]; }
} // 归并排序函数将数组a中的元素进行排序
void mergeSort(int a[], int n) { if (n 1) { // 如果数组只有一个元素或为空直接返回 return; } int mid n / 2; // 计算数组的中间位置 int left[mid]; // 存储数组a左边部分的元素 int right[n - mid]; // 存储数组a右边部分的元素 for (int i 0; i mid; i) { // 将数组a左边部分的元素放入left数组中 left[i] a[i]; } for (int i mid; i n; i) { // 将数组a右边部分的元素放入right数组中 right[i - mid] a[i]; } mergeSort(left, mid); // 对left数组进行归并排序 mergeSort(right, n - mid); // 对right数组进行归并排序 merge(left, right, a, mid, n - mid); // 将left和right两个有序数组合并成一个有序数组a
} // 测试归并排序函数
int main() { int a[] {38, 27, 43, 36, 16, 25, 6, 22}; // 待排序的数组 int n sizeof(a) / sizeof(a[0]); // 数组的大小 mergeSort(a, n); // 对数组进行归并排序 for (int i 0; i n; i) { // 输出排序后的数组元素 cout a[i] ; } cout endl; return 0;
}上述代码实现了一个基于分治法的排序算法——归并排序总结如下
归并排序将数组不断分成两半直到每个子数组只有一个元素。然后对每个子数组进行排序最后将所有已排序的子数组合并成一个有序的数组。merge函数实现了合并操作将两个有序的数组合并成一个有序的数组。mergeSort函数是归并排序的主要实现。首先判断数组长度如果只有一个元素或为空直接返回。然后计算中间位置将数组分成左右两部分。接着对左右两部分递归地进行归并排序最后调用merge函数将两个有序数组合并成一个有序数组。在main函数中定义了一个待排序的数组a然后调用mergeSort函数对其进行归并排序。最后输出排序后的数组元素。时间复杂度为O(n log n)空间复杂度为O(n)。
