C++归并排序

秒速五厘米 2022-09-10 04:29 176阅读 0赞

# C++归并排序 #

**算法概述**：  
归并排序是将有序的两个数组进行排序，即将待排序的一个数组不断进行递归，直到递归成两个都只含有一个元素的数组，则对这两个之含有一个元素的数组进行排序，不断回溯，直到回溯到可以将待排序数组分成两个有序数组，之后对其进行最后一次有序数组排序，最后两个有序数组合并为一个有序数组，就得到了需要进行排序的数组，可以从小到大进行排序，也可以从大到小进行排序。

**代码**：

void mergeSort(vector<int>& nums, vector<int>& path, int left, int right)
    { 
    //1.递归返回条件
    	if(left >= right){ 
    		return;
    	}
    	int mid = (left + right) / 2;
    //2.进行左右数组递归
    	mergeSort(nums, path, left, mid);//对左边数组进行递归
    	mergeSort(nums, path, mid + 1, right);//对右边数组进行递归
    //3.每个递归中需要进行的动作，即对两个有序的数组进行合并排序 
    	int l = left;//第一个数组的起始位置
    	int r = mid + 1;//第二个数组的起始位置
    	
    	for(int ix = left; ix <= right; ++ix)
    	{ 
    		path[ix] = nums[ix];
    	}
    	for(int ix = left; ix <= right; ++ix){ 
    		if(ix == mid + 1){ 
    			nums[ix] = path[ix];
    		}else if(ix == right + 1 || path[left] <= path[right]){ 
    			nums[ix] = path[left++];
    		}else{ 
    			nums[ix] = path[right++];
    		}
    	}
    }

**时间复杂度：O(nlog n);  
空间复杂度：O(n);**

发表评论取消回复

表情：

评论列表（有 0 条评论，176人围观）

还没有评论，来说两句吧...

相关阅读

相关归并排序(C实现)

归并排序 > 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序...

向右看齐/ 2024年04月17日 06:26/ 0 赞/ 81 阅读

相关【C语言】归并排序

文章目录一、什么是归并排序二、归并排序步骤图解三、归并排序代码实现 1、递归实现 2、非递归实现四、总结

落日映苍穹つ/ 2024年02月27日 04:22/ 0 赞/ 45 阅读

相关归并排序c++模板

include<iostream> using namespace std; int arr[] = { 5,4,9,3,7,1,8,0};

缺乏、安全感/ 2023年03月06日 05:40/ 0 赞/ 15 阅读

相关 C++归并排序

C++归并排序算法概述：归并排序是将有序的两个数组进行排序，即将待排序的一个数组不断进行递归，直到递归成两个都只含有一个元素的数组，则对这两个之含有一个元素的数组

秒速五厘米/ 2022年09月10日 04:29/ 0 赞/ 177 阅读

相关 C++模板归并排序

C++模板归并排序归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(n log n)。1945年由约翰·冯

旧城等待，/ 2022年08月21日 00:20/ 0 赞/ 222 阅读

相关归并排序 C++实现

// 归并排序.cpp : Defines the entry point for the console application. // \include "stdaf

àì夳堔傛蜴生んèń/ 2022年06月18日 11:37/ 0 赞/ 191 阅读

相关 C++排序算法之归并排序

归并排序（1）算法介绍归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用，归并排序将两个已经有序的序列合并成一个有序的序

阳光穿透心脏的1/2处/ 2022年06月12日 02:42/ 0 赞/ 258 阅读

相关归并排序 C++实现

// 归并排序.cpp : Defines the entry point for the console application. // \include "stdaf

太过爱你忘了你带给我的痛/ 2022年05月15日 13:19/ 0 赞/ 206 阅读

相关归并排序 C++实现

// 归并排序.cpp : Defines the entry point for the console application. // \include "stdaf

雨点打透心脏的1/2处/ 2022年05月15日 13:19/ 0 赞/ 213 阅读

相关归并排序--C语言

今天写的是归并排序，归并排序的定义为：依次将每两个相邻的有序表合并成一个有序表的排序方法。最经常使用的归并方法是2-路归并。假设初始序列含有n个记录，则可看成是n个有序的子

红太狼/ 2022年03月18日 06:26/ 0 赞/ 215 阅读