外排序(磁盘I/O文件)(c语言)

目录

一.外排序处理

1.1库函数查询推荐

1.2需要的库函数 (如下)

1.2.1库函数(fscanf) 为例

1.2.2运行截图

二.外排序详解

?编辑2.1小文件快速排序

2.3小文件归并排序

2.3主函数分析

2.4主函数代码

三.全部代码

3.1注意事项

3.2全部代码

3.3运行结果

一.外排序处理

外排序是一种处理超出内存容量的大量数据的排序算法。

外排序的核心思想在于将大数据集分割成小部分，每部分单独排序后，再将这些有序的部分合并成一个大的有序文件。具体来说，外排序包括两个主要步骤：

分割和内部排序：由于数据量巨大，无法一次性加载到内存中，因此需要将数据分割成能够装入内存的小批次进行排序。这些小批次的数据被排序后写入临时文件。

归并过程：经过分割和排序得到的多个有序的临时文件，通过归并算法合并成一个完整的有序文件。在归并过程中，通常采用多路归并技术来减少I/O操作次数，从而提高排序效率。

此外，为了优化性能，外排序还可能使用一些高级策略，如败者树（用来增大归并的路数）和置换-选择排序（用来增大归并段的长度以减少归并段个数）等方法，旨在减少磁盘读写次数，因为磁盘I/O通常是外排序中最耗时的部分。

值得一提的是，外排序的一个典型应用场景是对大型数据库或数据仓库中的记录进行排序，这在数据分析、大数据处理等领域非常常见。

1.1库函数查询推荐

fscanf - C++ Reference大家可以在这查询C语言所需的库函数信息，特别推荐大家去查询，

这里以用百度翻译插件为例，虽然翻译的有点小问题，但大致上还是能看懂的

1.2需要的库函数 (如下)

需要的文件库函数有(fopen;fscanf;fprintf,sprintf)

fopen打开文件...

fscanf把文件数据输出....

fprintf函数用于文件操作。通过指定的格式和参数，将信息发送到由流指定的文件中..

sprintf将格式化的数据写入到字符串中的函数....

这里以上面的库函数(fscanf)为例: int fscanf(FILE * stream, const char* format, ...);

这个函数可以把文件中的数据读取出来，具体操作如下：

1.2.1库函数(fscanf) 为例

这里的调用fscanf();通过while循环可以依次的输出文件中的数据

SortData.txt中放入200个随机数。

void ArrPrintf(int* a,int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d
", a[i]);
	}
}

Test1(const char* file)
{
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		printf("打开文件失败
");
		exit(-1);
	}
	
	int a[100];
	int n = 100;
	int i = 0;
	int num = 0;
	int filei = 1;

	while (fscanf(fout, "%d
", &num) != EOF)
	{

		a[i++] = num;

	}
	ArrPrintf(a, n);
}
int main()
{
	//MergeSortFile("SortData.txt");
	Test1("SortData.txt");
	return 0;
}

1.2.2运行截图

可以看出，这里的控制台输出的结果与文件中存放的数据顺序是相同的

二.外排序详解

先对一个大文件进行拆分，这里拆分为新的10份文件，每份文件使用快速排序排好序(升序)

然后再使用归并算法对文件进行合并，本文进行模拟实现

2.1小文件快速排序

对分割后的每份小文件中的数据进行快排，使得10份小文件中的数据全变为有序(升序)；这里使用的快速排序是前后指针法和三位取中优化后的快排；

快速排序3种实现方法及优化(详细图解)

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);

}

2.3小文件归并排序

从第1份小文件开始，逐个后者合并(这里用来合并的文件是创建的新文件)。合并采用的算法为归并算法，对该算法不清晰的可以参考下面这篇文章

归并排序(递归和非递归方法)

void _MergeFile(const char* file1, const char* file2, const char* mfile)
{
	FILE* fout1 = fopen(file1, "r");
	if (fout1 == NULL)
	{
		printf("打开文件失败3
");
		exit(-1);
	}

	FILE* fout2 = fopen(file2, "r");
	if (fout2 == NULL)
	{
		printf("打开文件失败4
");
		exit(-1);
	}

	FILE* fin = fopen(mfile, "w");
	if (fin == NULL)
	{
		printf("打开文件失败5
");
		exit(-1);
	}

	int num1, num2;
	int ret1 = fscanf(fout1, "%d
", &num1);
	int ret2 = fscanf(fout2, "%d
", &num2);
	while (ret1 != EOF && ret2 != EOF)
	{
		if (num1 < num2)
		{
			fprintf(fin, "%d
", num1);
			ret1 = fscanf(fout1, "%d
", &num1);
		}
		else
		{
			fprintf(fin, "%d
", num2);
			ret2 = fscanf(fout2, "%d
", &num2);
		}
	}

	while (ret1 != EOF)
	{
		fprintf(fin, "%d
", num1);
		ret1 = fscanf(fout1, "%d
", &num1);
	}

	while (ret2 != EOF)
	{
		fprintf(fin, "%d
", num2);
		ret2 = fscanf(fout2, "%d
", &num2);
	}

	fclose(fout1);
	fclose(fout2);
	fclose(fin);
}

2.3主函数分析

把原文件分割为10份小文件，这里的原文件元素个数是已知的200个随机数。

注意：这里的使用
sprintf()库函数对文件命明方式

2.4主函数代码

void MergeSortFile(const char* file)
{
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		printf("打开文件失败1
");
		exit(-1);
	}

	// 分割成一段一段数据，内存排序后写到，小文件，
	int n = 10;//分割次数
	int a[20];//把数据读进数组中，后续排序完后会拷贝回小文件
	int sizeArr = 20;//数组大小
	int i = 0;
	int num = 0;
	char subfile[20];
	int filei = 1;

	memset(a, 0, sizeof(int) * sizeArr);
	while (fscanf(fout, "%d
", &num) != EOF)
	{
		if (i < sizeArr - 1 )
		{
			a[i++] = num;
		}
		else
		{
			a[i] = num;
			QuickSort(a, 0, sizeArr - 1);
			sprintf(subfile, "sub\sub_sort%d", filei++);
			FILE* fin = fopen(subfile, "w");
			if (fin == NULL)
			{
				printf("打开文件失败2
");
				exit(-1);
			}
			for (int j = 0; j < sizeArr; j++)
			{
				fprintf(fin, "%d
", a[j]);
			}
			fclose(fin);

			i = 0;
			memset(a, 0, sizeof(int) * sizeArr);
		}
	}

	// 利用互相归并到文件，实现整体有序
	char mfile[100] = "sub\sub_sort12";
	char file1[100] = "sub\sub_sort1";
	char file2[100] = "sub\sub_sort2";
	for (int i = 2; i <= n; ++i)
	{
		// 读取file1和file2,进行归并出mfile
		_MergeFile(file1, file2, mfile);

		strcpy(file1, mfile);
		sprintf(file2, "sub\sub_sort%d", i + 1);
		sprintf(mfile, "%s%d", mfile, i + 1);
	}

	printf("%s文件排序成功
", file);
	fclose(fout);
}

int main()
{
	MergeSortFile("SortData.txt");

	return 0;
}

三.全部代码

3.1注意事项

大家需要使用这个案例测试的话，需要自行准备400个随机数字(注意：1个数据占一行且为txt格式)，如果想正常运行，需要创建一个空的sub文件，和400数字的txt文件

3.2全部代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>

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);

}

void _MergeFile(const char* file1, const char* file2, const char* mfile)
{
	FILE* fout1 = fopen(file1, "r");
	if (fout1 == NULL)
	{
		printf("打开文件失败3
");
		exit(-1);
	}

	FILE* fout2 = fopen(file2, "r");
	if (fout2 == NULL)
	{
		printf("打开文件失败4
");
		exit(-1);
	}

	FILE* fin = fopen(mfile, "w");
	if (fin == NULL)
	{
		printf("打开文件失败5
");
		exit(-1);
	}

	int num1, num2;
	int ret1 = fscanf(fout1, "%d
", &num1);
	int ret2 = fscanf(fout2, "%d
", &num2);
	while (ret1 != EOF && ret2 != EOF)
	{
		if (num1 < num2)
		{
			fprintf(fin, "%d
", num1);
			ret1 = fscanf(fout1, "%d
", &num1);
		}
		else
		{
			fprintf(fin, "%d
", num2);
			ret2 = fscanf(fout2, "%d
", &num2);
		}
	}

	while (ret1 != EOF)
	{
		fprintf(fin, "%d
", num1);
		ret1 = fscanf(fout1, "%d
", &num1);
	}

	while (ret2 != EOF)
	{
		fprintf(fin, "%d
", num2);
		ret2 = fscanf(fout2, "%d
", &num2);
	}

	fclose(fout1);
	fclose(fout2);
	fclose(fin);
}

void MergeSortFile(const char* file)
{
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		printf("打开文件失败1
");
		exit(-1);
	}

	// 分割成一段一段数据，内存排序后写到，小文件，
	int n = 10;//分割次数
	int a[20];//把数据读进数组中，后续排序完后会拷贝回小文件
	int sizeArr = 20;//数组大小
	int i = 0;
	int num = 0;
	char subfile[20];
	int filei = 1;

	memset(a, 0, sizeof(int) * sizeArr);
	while (fscanf(fout, "%d
", &num) != EOF)
	{
		if (i < sizeArr - 1 )
		{
			a[i++] = num;
		}
		else
		{
			a[i] = num;
			QuickSort(a, 0, sizeArr - 1);
			sprintf(subfile, "sub\sub_sort%d", filei++);
			FILE* fin = fopen(subfile, "w");
			if (fin == NULL)
			{
				printf("打开文件失败2
");
				exit(-1);
			}
			for (int j = 0; j < sizeArr; j++)
			{
				fprintf(fin, "%d
", a[j]);
			}
			fclose(fin);

			i = 0;
			memset(a, 0, sizeof(int) * sizeArr);
		}
	}

	// 利用互相归并到文件，实现整体有序
	char mfile[100] = "sub\sub_sort12";
	char file1[100] = "sub\sub_sort1";
	char file2[100] = "sub\sub_sort2";
	for (int i = 2; i <= n; ++i)
	{
		// 读取file1和file2,进行归并出mfile
		_MergeFile(file1, file2, mfile);

		strcpy(file1, mfile);
		sprintf(file2, "sub\sub_sort%d", i + 1);
		sprintf(mfile, "%s%d", mfile, i + 1);
	}

	printf("%s文件排序成功
", file);
	fclose(fout);
}

int main()
{
	MergeSortFile("SortData.txt");

	return 0;
}

3.3运行结果

sub_sort1到sub_sort1为分割的10个小文件

中间这串递增的文件为开头的图mfile

其中的sub_sort12345678910为排序最终的文件

以上就是本期补齐的内容，欢迎参考指正，如有不懂，欢迎评论或私信出下期！！！