当前位置: 首页 > article >正文

数据结构5(初):续写排序

目录

1、外排序

2、计数排序


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");//读文件1。
	if (fout1 == NULL)
	{
		printf("打开文件失败\n");
		exit(-1);
	}

	FILE* fout2 = fopen(file2, "r");//读文件2。
	if (fout2 == NULL)
	{
		printf("打开文件失败\n");
		exit(-1);
	}

	FILE* fin = fopen(mfile, "w");//写出归并文件。
	if (fin == NULL)
	{
		printf("打开文件失败\n");
		exit(-1);
	}

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

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

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

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

void MergeSortFile(const char* file)//待排文件
{
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		printf("打开待排文件失败\n");
		exit(-1);
	}
	int n = 10;//每组数据有10个,我们在该测试中,仅仅只测试100个数据的外排序,所以每组分为了10个数据。
	int a[10];//将num每次读取的数据放入该数组中。

	int i = 0;
	int num = 0;//每次读取的数据暂时存放在此处。

	char subfile[20];
	int filei = 1;
	memset(a, 0, sizeof(int) * n);//初始化数组a

	while (fscanf(fout, "%d\n", &num) != EOF)
	{
		if (i < n - 1)
		{
			a[i++] = num;
		}
		else
		{
			a[i] = num;

			QuickSort(a, 0, n - 1);//使用快速排序进行内存上的排序。

			sprintf(subfile, "%d", filei++);

			FILE* fin = fopen(subfile, "w");
			if (fin == NULL)
			{
				printf("打开文件失败\n");
				exit(-1);
			}
			for (int j = 0; j < n; j++)
			{
				fprintf(fin, "%d\n", a[j]);
			}
			fclose(fin);

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

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

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

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

int main()
{
	MergeSortFile("../DataSort.txt");

	return 0;
}

 对于这个例子,读者不必要关注这个代码是不是写的有点不规范,只需要明白外排序的思想即可。

2、计数排序

思想:计数排序又称为鸽巢原理,操作步骤:

1. 统计相同元素出现次数。

2. 根据统计的结果进行排序。

例如:

//计数排序
void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		if (a[i] > max)
		{
			max = a[i];
		}
	}
	int range = max - min + 1;
	int* countA = (int*)malloc(sizeof(int) * range);
	memset(countA, 0, sizeof(int) * range);

	//
	for (int i = 0; i < n; i++)
	{
		countA[a[i] - min]++;
	}

	int k = 0;
	for (int j = 0; j < range; j++)
	{
		while (countA[j]--)
		{
			a[k++] = j + min;
		}
	}
}

计数排序的特性总结:

1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限(仅仅只适用于整数的排序)

2. 时间复杂度:O(N+range)。

3. 空间复杂度:O(range)。

4. 稳定性:稳定


http://www.kler.cn/a/611528.html

相关文章:

  • 手搓全自动文章多平台发布系统:2、重要模块的设计
  • 国产化适配 - YashanDB、达梦数据库与MySQL 的兼容性及技术选型对比分析
  • R语言交互项-formula
  • 【C++】STL库_list 的模拟实现
  • 大数据学习栈记——HBase操作(shell java)
  • Couchbase存储引擎Magma和Couchstore
  • Stable Diffusion绘画插件(ControlNet )
  • Eclipse Debug 调试
  • 汇编(六)——汇编语言程序格式及MASM
  • OpenGL绘制文本
  • Vue的实例
  • Three.js 快速入门教程【十八】射线拾取模型——鼠标点击屏幕选中模型或物体
  • 【AI大模型】搭建本地大模型GPT-J:详细步骤及常见问题
  • 计算机视觉中的椭圆带权平均算法全解析
  • 【NLP 44、实践 ⑪ 用Bert模型结构实现自回归语言模型的训练】
  • Docker技术系列文章,第七篇——Docker 在 CI/CD 中的应用
  • 全息教学系统的软件开发,沉浸式数字沙盘展示系统如何改变历史教学
  • 孟德尔随机化:脑卒中研究新钥匙
  • Linux 设备分类详解:字符设备、块设备与网络设备解析
  • Java后端API限流秘籍:高并发的防护伞与实战指南