找公司做网站的好处,深圳市建设行业主管部门官方网站,建筑培训机构,广告投放基础知识归并排序
归并排序是一种经典的排序算法#xff0c;属于分治算法的一种。其核心思想是将一个大问题分解成若干个较小的子问题来解决#xff0c;然后根据子问题的解构建原问题的解。在排序问题中#xff0c;归并排序将数组分成两半#xff0c;分别对这两半进行排序#xf…归并排序
归并排序是一种经典的排序算法属于分治算法的一种。其核心思想是将一个大问题分解成若干个较小的子问题来解决然后根据子问题的解构建原问题的解。在排序问题中归并排序将数组分成两半分别对这两半进行排序然后将排序好的两个半部分合并成一个有序的整体。
归并排序的具体步骤如下 分解将待排序的数组分成两部分直到每部分只有一个元素或为空。如果数组只有一个元素或为空则它自然是有序的。
解决递归地对每部分进行归并排序。
合并将排序好的两部分合并成一个有序的整体。
归并排序的算法流程可以用以下伪代码表示
function mergeSort(array)if length of array 1return arrayelsemiddle length of array / 2left mergeSort(first half of array)right mergeSort(second half of array)return merge(left, right)function merge(left, right)result empty arraywhile left is not empty and right is not emptyif the first element of left the first element of rightadd the first element of left to resultremove the first element from leftelseadd the first element of right to resultremove the first element from rightend whileadd the remaining elements of left to resultadd the remaining elements of right to resultreturn result算法流程如下 调用归并排序调用mergeSort函数传入数组和索引0数组起始和n - 1数组结束。
递归分解mergeSort函数首先计算中间索引middle然后对数组的左半部分和右半部分分别进行递归调用。
基线条件当数组的大小小于等于1时递归结束因为单个元素或空数组自然是有序的。
合并在递归调用返回后mergeSort函数调用merge函数传入数组和左右两部分的索引。
合并过程 merge函数创建两个临时数组temp1和temp2分别存储原数组的左右两部分。 使用两个索引i和j分别遍历temp1和temp2比较元素大小并将较小的元素放入原数组的相应位置。 当一个临时数组的所有元素都被合并后将另一个数组的剩余元素拷贝到原数组中。
归并排序是一种稳定的排序算法因为它可以保持相等元素的原始顺序。不过由于它需要额外的空间来存储临时数组因此它的空间复杂度为O(n)。时间复杂度为O(nlogn)。
具体代码如下
#include iostream
#include vectorusing namespace std;// 合并两个有序数组
void merge(vectorint arr, int left, int middle, int right) {// 创建两个临时数组用于存储分割后的数组int n1 middle - left 1; // 左边数组的大小int n2 right - middle; // 右边数组的大小vectorint temp1(n1);vectorint temp2(n2);// 分别将原数组中的元素拷贝到临时数组中for (int i 0; i n1; i) {temp1[i] arr[left i];}for (int j 0; j n2; j) {temp2[j] arr[middle 1 j];}// 合并两个临时数组到原数组中int i 0; // 左边数组的起始索引int j 0; // 右边数组的起始索引int k left; // 合并后数组的起始索引while (i n1 j n2) {if (temp1[i] temp2[j]) {arr[k] temp1[i];i;} else {arr[k] temp2[j];j;}k;}// 将剩余的元素拷贝到原数组中while (i n1) {arr[k] temp1[i];i;k;}while (j n2) {arr[k] temp2[j];j;k;}
}// 归并排序
void mergeSort(vectorint arr, int left, int right) {if (left right) {int middle left (right - left) / 2;// 分割数组并递归调用归并排序mergeSort(arr, left, middle);mergeSort(arr, middle 1, right);// 合并两个有序数组merge(arr, left, middle, right);}
}int main() {vectorint arr {9, 5, 7, 3, 1, 8, 6, 2, 4};int n arr.size();cout 原始数组: ;for (int i 0; i n; i) {cout arr[i] ;}cout endl;// 调用归并排序算法mergeSort(arr, 0, n - 1);cout 排序后的数组: ;for (int i 0; i n; i) {cout arr[i] ;}cout endl;return 0;
}
