目录

一、归并排序

 1.1 递归方法静态图

 1.2 归并递归方法 代码:

1.3  思路一 : (非递归，只是用于2^n个数)​编辑

1.4 begin1，end1,begin2,end2如何确定？

1.5 归并排序(非递归)，只适合2^n个数 代码

1.6 为什么说上述思路一只适合于2^n个数的数组呢？

1.7 调整版本一: 大区间进行拷贝

 1.8 调整版本二: 小区间进行拷贝

1.9  特性

二、计数排序(非比较排序)

 2.1 代码

 2.2 特性

三、排序算法复杂度及稳定性总结

一、归并排序

基本思想:归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

 1.1 递归方法静态图

 1.2 归并递归方法 代码:

//归并递归函数
void _MergeSort(int* a,int left,int right,int* temp)
{
	//不再分解
	if (left >= right)
	{
		return;
	}
	int mid = left + ((right - left) >> 2);
	//[left,mid] [mid+1,right]
	//分解
	_MergeSort(a,left,mid,temp);//先分解左区间
	_MergeSort(a,mid+1,right,temp);//再分解右区间

	//合并
	int i = left;
	//分为俩个区间的比较
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	
	//当俩个区间都存在的情况下
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			temp[i++] = a[begin1++];
		}
		else
		{
			temp[i++] = a[begin2++];
		}
	}
	//如果一个已经结束,但是不知道那个区间
	while (begin1 <= end1)
	{
		temp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		temp[i++] = a[begin2++];
	}

	//最后将temp里面的数赋值给a数组[left,right],第一次left = 0,right = 1，然后放到a数组中去
	for (int j = left;j <=right;j++)
	{
		a[j] = temp[j];
	}
}

//归并排序
void MergeSort(int* a,int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp == NULL)
	{
		printf("malloc failedn");
		exit(-1);
	}
	_MergeSort(a,0,n-1,temp);
	free(temp);
	temp = NULL;
}

运行结果:

1.3  思路一 : (非递归，只是用于2^n个数)

 

1.4 begin1，end1,begin2,end2如何确定？

1.5 归并排序(非递归)，只适合2^n个数 代码

//归并排序(非递归)，只适合2^n个数
void MergeSortNonR(int* a, int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp == NULL)
	{
		printf("malloc failedn");
		exit(-1);
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[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;
			printf("[%d,%d] ",begin1,end1);
			printf("[%d,%d] ", begin2, end2);
			int j = i;
			//合并
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					temp[j++] = a[begin1++];
				}
				else
				{
					temp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				temp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				temp[j++] = a[begin2++];
			}
		}
		printf("n");
		//数据拷贝回原数组
		for (int i = 0; i < n; i++)
		{
			a[i] = temp[i];
		}
		gap *= 2;
	}
	

	free(temp);
	temp = NULL;
}

 上述思路一 只适用于2^n个数,运行结果如下图:

gap = 1,即一个数为一组形成一个区间[0,0]和下一组区间[1,1]进行归并

gap = 2,即俩个数为一组形成一个区间[0,1]和下一组区间[2,3]进行归并

gap = 4,即四个数为一组形成一个区间[0,3]和下一组区间[4,7]进行归并

1.6 为什么说上述思路一只适合于2^n个数的数组呢？

那我们将8个数的数组多加一位,形成  int a[] = {10,6,7,1,3,9,4,2,5};

主要核心思想:begin1是不会越界的,因为它是通过i

 如下图所示:

 调整:

1.7 调整版本一: 大区间进行拷贝

//归并排序 方法一 : 进行[0,n-1]之后再进行拷贝(非递归，调整2^n版)
void MergeSortNonR2(int* a, int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp == NULL)
	{
		printf("malloc failedn");
		exit(-1);
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[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;
			
			//调整部分
			if (end1 >= n)
			{
				end1 = n - 1;
			}
			if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}


			printf("[%d,%d] ", begin1, end1);
			printf("[%d,%d] ", begin2, end2);
			int j = i;
			//归并
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					temp[j++] = a[begin1++];
				}
				else
				{
					temp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				temp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				temp[j++] = a[begin2++];
			}
		}
		printf("n");
		//数据拷贝回原数组
		for (int i = 0; i < n; i++)
		{
			a[i] = temp[i];
		}
		gap *= 2;
	}
	free(temp);
	temp = NULL;
}

运行结果:

 1.8 调整版本二: 小区间进行拷贝

//归并排序 方法二 : 小区间进行拷贝
void MergeSortNonR3(int* a, int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp == NULL)
	{
		printf("malloc failedn");
		exit(-1);
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[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;

			//调整:当end1不存在,不需要归并,因为[begin2,end2]也不存在,不需要调整,因为begin1就在a数组中
			//begin2不存在也是如此,也不需要调整,因为俩个区间无法比较
			if (end1 >= n || begin2 >= n)
			{
				break;//跳过归并
			}
			//当end2不存在时,这是[begin1,end1]是存在的,end2及之后的区间中也是有数可以和[begin1,end1]进行比较的
			//所以应将end2 = n-1;将[begin1,end1]和[begin2,n-1]进行归并
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			int j = i;
			//归并
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					temp[j++] = a[begin1++];
				}
				else
				{
					temp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				temp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				temp[j++] = a[begin2++];
			}
			//小区间进行 数据拷贝回原数组
			for (int j = i; j <= end2; j++)
			{
				a[j] = temp[j];
			}
		}
		gap *= 2;
	}
	free(temp);
	temp = NULL;
}

 运行结果:

1.9  特性 1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度： O(N*logN) 3. 空间复杂度： O(N) 4. 稳定性：稳定

二、计数排序(非比较排序) 思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤： 1. 统计相同元素出现次数 2. 根据统计的结果将序列回收到原来的序列中

 2.1 代码

//计数排序（适用于全是正数）
void CountSort(int* a,int n)
{
	//寻找最大值与最小值
	int max = a[0], min = a[0];
	for (int i = 1; i < n;i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	//确定开辟空间大小
	int range = max - min + 1;
	//开辟空间
	int* count = (int*)malloc(sizeof(int)*range);
	memset(count,0, sizeof(int) * range);
	if (count == NULL)
	{
		printf("malloc failedn");
		exit(-1);
	}
	//统计数据出现的次数
	for (int i = 0;i < n;i++)
	{
		count[a[i]-min]++;
	}
	//根据次序排序
	int j = 0;
	for (int i = 0;i < range;i++)
	{
		while(count[i]--)
		{
			a[j++] = i + min;
		}
	}

}

运行结果:

 2.2 特性 1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。 2. 时间复杂度： O(MAX(N,range )) 3. 空间复杂度： O(range ) 4.适用于范围比较集中的整数数组,范围较大或者是浮点数都不适合 5. 稳定性：稳定

三、排序算法复杂度及稳定性总结