归并排序及其应用场景

「爱情、让人受尽委屈。」 2022-09-12 03:55 220阅读 0赞

### 文章目录 ###

*  一、归并排序的概念
 *  二、归并排序递归与非递归实现
 *  三、归并排序应用场景
 *  四、归并排序总结

# 一、归并排序的概念 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_20_color_FFFFFF_t_70_g_se_x_16]

# 二、归并排序递归与非递归实现 #

**归并排序递归实现，分治为每个区间元素都有序，那么就得把区间 分治成为1才能保证区间中每个元素都有序，在归并：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_15_color_FFFFFF_t_70_g_se_x_16]

//归并排序
    void _MergeSort(int*arr, int left, int right, int* tmp)
    { 
    	if (left >= right)
    	{ 
    		return;
    	}
    	int mid = left + (right - left) / 2;
    	_MergeSort(arr, left, mid, tmp);
    	_MergeSort(arr, mid + 1, right, tmp);
    
    	int begin1 = left;
    	int end1 = mid;
    
    	int begin2 = mid + 1;
    	int end2 = right;
    
    	int i = left; 
    
    	while (begin1 <= end1&&begin2 <= end2)
    	{ 
    		if (arr[begin1] < arr[begin2])
    		{ 
    			tmp[i++] = arr[begin1++];
    		}
    		else if (arr[begin1]>arr[begin2])
    		{ 
    			tmp[i++] = arr[begin2++];
    		}
    	}
    
    	while (begin1 <= end1)
    	{ 
    		tmp[i++] = arr[begin1++];
    	}
    	while (begin2 <= end2)
    	{ 
    		tmp[i++] = arr[begin2++];
    	}
    
    	for (int j = left; j <= right; j++)
    	{ 
    		arr[j] = tmp[j];
    	}
    }
    void MergeSort(int* arr, int sz)
    { 
    	int* tmp = new int[sz];
    	_MergeSort(arr, 0, sz - 1, tmp);
    	delete[] tmp;
    }

**归并排序非递归实现 ，借助gap值来归并：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_16_color_FFFFFF_t_70_g_se_x_16]  
**注意归并时候发生的三种情况:**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16]

void _MergeSortNonR(int* arr, int begin1, int end1, int begin2, int end2, int* tmp)
    { 
    	int i = begin1;
    	int j = begin1;
    	while (begin1 <= end1&&begin2 <= end2)
    	{ 
    		if (arr[begin1] < arr[begin2])
    		{ 
    			tmp[i++] = arr[begin1++];
    		}
    		else
    		{ 
    			tmp[i++] = arr[begin2++];
    		}
    	}
    	
    	while (begin1 <= end1)
    	{ 
    		tmp[i++] = arr[begin1++];
    	}
    	while (begin2 <= end2)
    	{ 
    		tmp[i++] = arr[begin2++];
    	}
    
    
    	for (; j <= end2; j++)//begin1加加j不受到影响
    	{ 
    		arr[j] = tmp[j];
    	}
    }
    void MergeSortNonR(int* arr, int sz)
    { 
    	int* tmp = new int[sz];
    
    	int gap = 1;
    	while (gap < sz)
    	{ 
    		for (int i = 0; i < sz; i += 2 * gap)
    		{ 
    			int begin1 = i;
    			int end1 = i + gap - 1;
    
    			int begin2 = i + gap;
    			int end2 = i + 2 * gap - 1;
    
    			//如果第二个小区间不存在了
    			if (begin2 >= sz)
    			{ 
    				break;
    			}
    
    			//如果第二个小区间存在，但是第二个小区间不够gap个，结束位置就越界了，需要修正一下
    			if (end2 >= sz)
    			{ 
    				end2 = sz - 1;	
    			}
    			_MergeSortNonR(arr, begin1, end1, begin2, end2, tmp);
    		}
    	}
    }

# 三、归并排序应用场景 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16 2]

# 四、归并排序总结 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_17_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f716fd7a00bc4669a98b71d5857843ef.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/46042c46336140258c5d7103797f839f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/a2985b02d153424d811bde83f88add2b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/88de5d1fff01445a8d8d208bd9eb33f4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/a72be2dbe9c04f8581cb9cb37fad5b06.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/f1395db20a7d4f9e82901edc6a895bac.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/516cc699e76545c4be76d09cceb8c171.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/5306d7d462104663adc2d5e9fb5d1ce7.png