海量数据排序—外排序之归并实现外排序排序_外排序实现

目录

一，什么是外排序

二,准备工作

三，归并排序文件写法

1.准备

2,分割字文件

1，把大文件分割成子文件。

2，分割代码

2，对分割好的子文件取排序，

3.给子文件取名字    1，2，3，4，5，6，7....这样子。

4，放数据到子文件

5，迭代，剩下的数据依次放入不同子文件

三，子文件进行归并。

1.画图：

2.归并子函数：也就是一次归并

3.归并代码：

4.完整代码

四，结果展示

五，代码链接

---

一，什么是外排序

1.其实外排序就是在文件中进行排序，那我们知道在文件中访问数据有很多限制，比如不可以随机访问啊，只能通过文件指针访问啊，等等。那我们为什么还要在文件中排序也就是外排序呢？

【1.】数据量过大，比如海量数据：举个例子，比如又100亿整形需要你排序，我们算一算100亿个整形放在内存中要多大空间呢。

1KB=1024byte；

1MB=1024KB：

1G=1024MB；

我们知道一个整形是4个字节，也就是4byte；

1024*1024*1024大概估计是10亿的样子，也就是说1G内存大概就只能运行10亿字节的样子。

而100亿个整形是400亿个字节，全部加载到内存中的话将需要40个G的内存，一般的电脑根本没有，就算是公司的操作系统也是要跑其他很多的程序的，这个代价显然是太大了，并且是没有的，更何况如果数据更大呢？，加内存是不能解决这类问题的。

二,准备工作

先来一个快排：QuickSort(int* a, int left, int right)：

快排写法前面总结有的，这里就不介绍了。

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
			return mid;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
	else // a[begin] > a[mid]
	{
		if (a[mid] > a[end])
			return mid;
		else if (a[begin] < a[end])
			return begin;
		else
			return end;
	}
}
 
void QuickSort(int* a, int left, int right)
{
	assert(a);
	if (left >= right)
		return;
 
	int midIndex = GetMidIndex(a, left, right);
	Swap(&a[midIndex], &a[right]);
 
	int prev = left - 1;
	int cur = left;
	int keyindex = right;
 
	while (cur < right)
	{
		if (a[cur] < a[keyindex] && ++prev != cur)
			Swap(&a[prev], &a[cur]);
 
		++cur;
	}
	Swap(&a[++prev], &a[keyindex]);
 
	int div = prev;
 
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
 
}

三，归并排序文件写法

1.准备

我们写的是外排序嘛，那就是在文件中排序，我们先准备一个文件，里面放入100个数据，这里我们只是进行模拟，不需要真的放100亿个数据，哈哈。文件里面数据大小随便写，但是数据的格式一定要统一，不然后面文件读取不好搞了就。

2,分割字文件

这里其实有俩个步骤我们和在一起搞了。

1，把大文件分割成子文件。

这里我们有100个数据，我们按照10个一组的去分为是个。

2，分割代码