八大排序 -

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表，称为二路归并。

例如：

 我们不断地将区间一半一半地划分，直到只剩下一个数据时开始往回合并 ， 我们利用一个temp数组辅助我们将两段区间合并，最后合并为一个有序区间。

代码实现：

void _Merge(int* a, int* tmp, int begin1, int end1, int begin2, int end2) //使递归和非递归都能用  复用
{
	int i = begin1;
	int j = begin1;

	while (begin1 <= end1 && begin2 <= end2)
	{
        //对两段分组进行排序
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}

	//有一个分组先走完 ， 把剩余的拷贝进tmp
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];

	while (begin2 <= end2)
		tmp[i++] = a[begin2++];
	
	// 归并完成以后，拷贝回到原数组
	for (; j <= end2; ++j)
	{
		a[j] = tmp[j];
	}
}

//归并排序子函数
void _MergeSort(int* a, int left, int right, int* temp)
{
	if (left >= right) //递归结束条件
		return;

	int mid = (left + right) >> 1; // 移位运算效率高
	_MergeSort(a, left, mid, temp); //递归调用左
	_MergeSort(a, mid + 1, right, temp); // 递归调用右

	// 两段有序子区间归并tmp,并拷贝回去
	//int begin1 = left, end1 = mid; //左边区间的边界
	//int begin2 = mid + 1, end2 = right; //右边区间的边界

	_Merge(a, temp, left, mid, mid + 1, right);
}



//归并排序主函数
void MergeSort(int* a, int n)
{

	//开辟临时空间 用于暂存归并的结果
	int* temp = new int[n];
	if (temp == nullptr)
	{
		cout << "new falid !" << endl;
		exit(-1);
	}

	_MergeSort(a, 0, n - 1, temp);//归并开始

	delete[] temp;
}

归并排序的非递归方式在这里我们使用循环的方式来进行合并，我们每次控制参与合并的元素个数，按照 2的次方方式 使 gap 逐渐增加 ，但是gap要满足  gap < n.

 图片中的例子只是一种理想的情况，在这里我们还会遇到三种需要特殊处理的情况：

情况1：当最后一个小组归并时，第一个小区间不够gap个，就不需要归并了。

 情况2：当最后一个小组归并时，第二个小区间存在，第二个区间不够gap个，需要调整边界。

情况3：当最后一个小组归并时，第二个小区间不存在，不需要归并了。

代码实现:

void _Merge(int* a, int* tmp, int begin1, int end1, int begin2, int end2) //使递归和非递归都能用  复用
{
	int i = begin1;
	int j = begin1;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}

	//有一个分组先走完 ， 把剩余的拷贝进tmp
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];

	while (begin2 <= end2)
		tmp[i++] = a[begin2++];
	
	// 归并完成以后，拷贝回到原数组
	for (; j <= end2; ++j)
	{
		a[j] = tmp[j];
	}
}



// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{

	//开辟临时空间 用于暂存归并的结果
	int* temp = new int[n];
	if (temp == nullptr)
	{
		cout << "new falid !" << endl;
		exit(-1);
	}

	int gap = 1;
	while (gap < n) //控制gap < n
	{
		for (int i = 0; i < n; i += 2 * gap) //gap以2的被数增长
		{
			//[i, i + gap - 1]  [ i + gap, i + 2 * gap - 1] 归并一个小组 //画图帮助理解
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			// 情况1,3：如果第二个小区间不存在就不需要归并了，结束本次循环
			if (begin2 >= n)
				break;

			// 情况2 ：如果第二个小区间存在，但是第二个小区间不够gap个，结束位置越界了，需要修正一下
			if (end2 >= n)
				end2 = n - 1;

			_Merge(a, temp, begin1, end1, begin2, end2);
		}
		
		gap *= 2;
	}

	delete[] temp;

}

1.时间复杂度：O(N*logN)   空间复杂度：O(N)

2.归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题

首先，我先说明一下什么是内排序，什么是外排序：
 内排序：数据量相对少一些，可以放到内存中进行排序。

 外排序：数据量较大，内存中放不下，数据只能放到磁盘文件中，需要排序。

 上面介绍的排序算法均是在内存中进行的，对于数据量庞大的序列，上面介绍的排序算法都束手无策，而归并排序却能胜任这种海量数据的排序。

 假设现在有10亿个整数（4GB）存放在文件A中，需要我们进行排序，而内存一次只能提供512MB空间，归并排序解决该问题的基本思路如下：
 1、每次从文件A中读取八分之一，即512MB到内存中进行排序（内排序），并将排序结果写入到一个文件中，然后再读取八分之一，重复这个过程。

那么最终会生成8个各自有序的小文件（A1~A8）。

 2、对生成的8个小文件进行11合并，最终8个文件被合成为4个，然后再11合并，就变成2个文件了，最后再进行一次11合并，就变成1个有序文件了。

注意：这里将两个文件进行11合并，并不是先将两个文件读入内存然后进行合并，因为内存装不下。

这里的11合并是利用文件输入输出函数，从两个文件中各自读取一个数据，然后进行比较，将较小的数据写入到一个新文件中去，然后再读取，再比较，再写入，最终将两个文件中的数据全部写入到另一个文件中去，那么此时这个文件又是一个有序的文件了。

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        

 当然，你也可以这样合并文件：

外排序代码示例：

//将file1文件和file2文件中的数据归并到mfile文件中
void _MergeFile(const char* file1, const char* file2, const char* mfile)
{
	FILE* fout1 = fopen(file1, "r");//打开file1文件
	if (fout1 == NULL)
	{
		printf("打开文件失败\n");
		exit(-1);
	}

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

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

	int num1, num2;
	int ret1 = fscanf(fout1, "%d\n", &num1);//读取file1文件中的数据
	int ret2 = fscanf(fout2, "%d\n", &num2);//读取file2文件中的数据
	while (ret1 != EOF && ret2 != EOF)
	{
		//将读取到的较小值写入到mfile文件中，继续从file1和file2中读取数据进行比较
		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);
		}
	}
	//将file1文件中未读取完的数据写入文件mfile中
	while (ret1 != EOF)
	{
		fprintf(fin, "%d\n", num1);
		ret1 = fscanf(fout1, "%d\n", &num1);
	}
	//将file2文件中未读取完的数据写入文件mfile中
	while (ret2 != EOF)
	{
		fprintf(fin, "%d\n", num2);
		ret2 = fscanf(fout2, "%d\n", &num2);
	}
	fclose(fout1);//关闭file1文件
	fclose(fout2);//关闭file2文件
	fclose(fin);//关闭mfile文件
}
//将文件中的数据进行排序
void MergeSortFile(const char* file)
{
	FILE* fout = fopen(file, "r");//打开文件
	if (fout == NULL)
	{
		printf("打开文件失败\n");
		exit(-1);
	}
	// 分割成一段一段数据，内存排序后写到小文件中
	int n = 10;//一次读取10个数据进行内排序
	int a[10];//读取数据放到数组中，准备进行内排序
	int i = 0;
	int num = 0;
	char subfile[20];//文件名字符串
	int filei = 1;//储存第filei组内排序后的数据的文件的文件名

	memset(a, 0, sizeof(int)*n);//将数组a的空间置0
	while (fscanf(fout, "%d\n", &num) != EOF)//从文件中读取数据
	{
		if (i < n - 1)//读取前9个数据
		{
			a[i++] = num;
		}
		else//读取第10个数据
		{
			a[i] = num;
			QuickSort(a, 0, n - 1);//将这10个数据进行快速排序
			sprintf(subfile, "%d", filei++);//将储存第filei组内排序后的数据的文件的文件名命名为filei
			FILE* fin = fopen(subfile, "w");//创建一个以字符串subfile[20]为名字的文件并打开
			if (fin == NULL)
			{
				printf("打开文件失败\n");
				exit(-1);
			}
			//将内排序排好的数据写入到subfile文件中
			for (int i = 0; i < n; i++)
			{
				fprintf(fin, "%d\n", a[i]);
			}
			fclose(fin);//关闭subfile文件

			i = 0;
			memset(a, 0, sizeof(int)*n);//将a数组内存置0，准备再次读取10个数据进行内排序
		}
	}
	// 利用互相归并到文件，实现整体有序
	char mfile[100] = "12";//归并后文件的文件名
	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);//下一次归并后文件的文件名
	}

	fclose(fout);//关闭文件
}
//主函数
int main()
{
	MergeSortFile("Sort.txt");//将Sort.txt文件中的数据进行排序
	return 0;
}

 注：代码中使用的是第二种文件合并的方式。

//这里的外排序使用 2021dragon 的内容，写的非常仔细，图也画的整齐好看。

版权声明：本文为CSDN博主「2021dragon」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/chenlong_cxy/article/details/116563972

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用

这里我们使用相对映射的方式进行排序。

代码实现：

void CountSort(int* a, int n)
{
	int Max = a[0]; //找到最大和最小确定边界
	int Min = a[0];

	for (int i = 0; i < n; ++i)
	{
		if (a[i] > Max)
			Max = a[i];

		if (a[i] < Min)
			Min = a[i];
	}

	int range = Max - Min + 1;  //实际存储的个数
	int* count = new int[range]; // 开辟空间
	memset(count, 0, sizeof(int) * range); //将这段空间初始化为0

	for (int i = 0; i < n; ++i) //使用相对映射，统计相同数字出现的次数
	{
		count[a[i] - Min]++;
	}

	int i = 0; 
	for (int j = 0; j < range; ++j) //从映射的空间中输出到 a 中
	{
		while (count[j]--)
		{
			a[i++] = j + Min;
		}
	}

	delete[] count;

}

①绝对映射的方式可能会对空间造成大量浪费，例如： 只有两个数据 100,99，我们只需要排两个数据，但是需要开辟101 个int类型空间； 而相对映射的方式就比较合理了，我们尽可能使用相对映射的方式进行排序。

②计数排序只适合一组数据，数据的范围比较集中. 如果范围集中，效率是很高的，但是局限性也在这里，并且只适合整数，如果是浮点数、字符串等等就不行了。

③时间复杂度 O(N+range)   空间复杂度： O(range)