佛山建网站价格,制作静态动漫网站模板,建设工程造价管理,东莞网站建设免费服务器目录
1、简述
2、复杂度
3、稳定性
4、例子 1、简述
二路归并排序#xff08;Merge Sort#xff09;是一种基于分治法的排序算法#xff0c;通过将数组递归地拆分成两部分#xff0c;分别排序后再合并#xff0c;从而实现整个数组的有序。二路归并排序具有稳定性和高…目录
1、简述
2、复杂度
3、稳定性
4、例子 1、简述
二路归并排序Merge Sort是一种基于分治法的排序算法通过将数组递归地拆分成两部分分别排序后再合并从而实现整个数组的有序。二路归并排序具有稳定性和高效性是一种非常经典的排序算法。
实现步骤
分割 将数组分成两部分分别对每部分进行递归排序。合并 将两个已排序的部分合并成一个有序的整体。
2、复杂度 时间复杂度 最佳情况O(n log n)最坏情况O(n log n)平均情况O(n log n) 空间复杂度 O(n)需要额外的存储空间来合并两个子数组。
3、稳定性
归并排序是一种稳定的排序算法因为在合并时保持了相同元素的相对顺序。 4、例子
#include iostream
#include vector// 合并两个有序子数组
void merge(std::vectorint arr, int left, int mid, int right) {int n1 mid - left 1;int n2 right - mid;// 创建临时数组std::vectorint L(n1);std::vectorint R(n2);// 复制数据到临时数组 L[] 和 R[]for (int i 0; i n1; i)L[i] arr[left i];for (int i 0; i n2; i)R[i] arr[mid 1 i];// 合并临时数组到原数组int i 0, j 0, k left;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(std::vectorint arr, int left, int right) {if (left right) {int mid left (right - left) / 2;// 递归排序两个子数组mergeSort(arr, left, mid);mergeSort(arr, mid 1, right);// 合并两个已排序的子数组merge(arr, left, mid, right);}
}// 测试代码
int main() {std::vectorint array {12, 11, 13, 5, 6, 7};mergeSort(array, 0, array.size() - 1);std::cout Sorted array is \n;for (int num : array)std::cout num ;std::cout std::endl;return 0;
}快捷跳转
排序算法概述 生命不息学习不止若有不正确的地方欢迎指正。
