排序算法之合并排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了排序算法之合并排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1889字，纯文字阅读大概需要3分钟。

内容图文

合并排序法 (Merge Sorting) 是外部排序最常使用的排序方法。

主要应用场景是：若数据量太大无法一次完全加载内存，

可使用外部辅助内存来处理排序数据，主要应用在文件排序。
排序方法：
将欲排序的数据分别存在数个文件大小可加载内存的文件中，

再针对各个文件分别使用“内部排序法” 将文件中的数据排序好写回文件。

再对所有已排序好的文件两两合并， 直到所有文件合并成一个文件后，

则数据排序完成。

 

   合并排序是使用到了分治方法（Divide and Conquer）。

　　Divide：将原问题分解为若干子问题，其中这些子问题的规模小于原问题的规模。

　　Conquer：递归地求解子问题，当子问题规模足够小时直接求解。

　　Merge：将子问题的解合并得到原问题的解。

 

下面是代码实现部分：

class Merge{
	public void merge_sort(int arr[], int start, int end)
	{
		//当数组长度大于0时，继续进行分割
		if(start < end)
		{
			//每次分割都是找到中间位置，作为分割点
			int m = (start + end) / 2; 
			//分割的前半段，继续进行分割
			merge_sort(arr, start, m);
			//分割的后半段，也继续进行分割。都进行分割的前提是，长度大于0，且还能分割
			merge_sort(arr, m+1, end);
			
			//分割完成后，进行合并
			combine_arrays(arr, start, m, end);
		}
	}
	
	public void combine_arrays(int arr[], int start, int m, int end)
	{
		int length = end - start + 1;
		int temp[] = new int[length];
		int i = start;
		int j = m+1;
		int c = 0;
		
		//把两段数组中比较，较小的那个放到temp中
		while(i<=m && j<=end)
		{
			if(arr[i] < arr[j])
			{
				temp[c] = arr[i];
				i++;
				c++;
			}
			else
			{
				temp[c] = arr[j];
				j++;
				c++;
			}
		}
		
		//当前面比较结束，前半段剩下的部分
		while(i <= m)
		{
			temp[c] = arr[i];
			i++;
			c++;
		}
		
		//当后半段比较结束，后半段剩下的部分
		while(j <= end)
		{
			temp[c] = arr[j];
			j++;
			c++;
		}
		
		//合并成一个数组
		 c = 0;
		 for(int t = start; t <= end; t++,c++)
		 {
			 arr[t] = temp[c]; //把排序好了的数组，放到原来的数组中
		 }
	}
}

 

然后是调用部分：

int arr[] = {-9, -50, 100, 20, 35, 7, 1, 56};
		
		Merge ms = new Merge();
		ms.merge_sort(arr, 0, arr.length-1);
		
		for(int i = 0; i < arr.length; i++)
		{
			System.out.println("arr[" + i + "] = " + arr[i]);
		}

 

结果如下：

合并排序一般是处理内存一次放不下这么大数据的时候，采用分而治之的思路来做。

 

 

 

 

内容总结

以上是互联网集市为您收集整理的排序算法之合并排序全部内容，希望文章能够帮你解决排序算法之合并排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---