排序3——C语言

1. 归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。

思路：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
下图为归并的全过程

将序列分割，若子区间无序，对子区间再分割，直至子区间有序（只有一个数时）再进行合并（相当于合并两个有序数组）。合并数据时，不能直接覆盖再原数组，会造成数据丢失，因此需要开辟一个辅助数组。

//归并排序
//复杂度O(N*logN)
void _MergeSort(int* array, int* tmp, int begin, int end)//左右闭区间
{
	//只有一个值，不用归并
	if (begin == end)
		return;

	//分成两组分别递归，归并
	int mid = (begin + end) / 2;
	_MergeSort(array, tmp, begin, mid);
	_MergeSort(array, tmp, mid + 1, end);

	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
 
    //归并过程
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (array[begin1] <= array[begin2])
		{
			tmp[i++] = array[begin1++];
		}
		else
		{
			tmp[i++] = array[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		tmp[i++] = array[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = array[begin2++];
	}

	//拷贝回原数组
	memcpy(array + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* array, int numsArr)
{
	//开辟辅助数组
	int* tmp = (int*)malloc(sizeof(int) * numsArr);
	if (tmp == NULL)
	{
		return;
	}

	_MergeSort(array, tmp, 0, numsArr - 1);

	free(tmp);
	tmp = NULL;
}

归并排序的缺点，空间复杂度为O（N），即额外需要一块辅助空间。

2. 计数排序

计数排序的思路：

1. 统计相同元素出现次数（遍历一遍数据即可）
2. 根据统计的结果将序列回收到原来的序列中

举例如下图

这里会面临两个问题

1. 数据过大，数据范围分散
2. 数据有负数，下标没有负数
   问题一会导致一个问题，开的辅助空间很大，比如数据为{ 1 ，19 ，33，50，69}，五个数需要开辟70个空间，太浪费。事实上，计数排序不适用于数据范围分散的情况，如果当数据范围很大很 分数时，就不要采用计数排序了。

问题二可以采用相对映射的方法来解决。让每一个数都减去最小值，那么如果有负数，减去最小值（也是负数，可能是本身）之后的值肯定大于等于0，就可以满足数组的下标了。还原回去时，数据再加上最小值即可。

//计数排序
//时间复杂度O(N+range)，空间复杂度O(range)
//适合于数据范围小的情况
void CountSort(int* array, int numsArr)
{
    //最大最小值
	int max = array[0], min = array[0];
	for (int i = 1; i < numsArr; i++)
	{
		if (array[i] < min)
			min = array[i];
		if (array[i] > max)
			max = array[i];
	}
    //开空间
	int range = max - min + 1;
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
		return;

	//统计每个数出现的次数(相对映射)
	for (int i = 0; i < numsArr; i++)
	{
		count[array[i] - min]++;
	}
	//修改数组
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			array[j++] = i + min;
		}
	}
}

3. 各排序的稳定性及复杂度

有关常见排序就介绍完毕了，总结一下复杂度和稳定性。一个排序的稳定性是指，两个相同的值在排序前后的相对位置没有改变，则该排序为稳定排序。否则不稳定。

冒泡排序：
相邻数据不等才会进行交换，因此为稳定排序。时间复杂度：O（N^2）空间复杂度O（1）

直接插入排序：
数据不相等才会进行插入，两个相等的数，在插入前后不会改变相对位置，因此为稳定排序。
时间复杂度O（N^2）空间复杂度O（1）

归并排序：
稳定排序，时间复杂度O（N*logN）空间复杂度O（N）

希尔排序：
不稳定排序，且看下面的例子。时间复杂度O（N^1.3）空间复杂度O（1）

直接选择排序：
不稳定，例子如下图，时间复杂度O（N^2）空间复杂度O（1）

堆排序：
不稳定，例子如下图，时间复杂度O（N*logN）空间复杂度O（1）

快速排序：
不稳定，例子如下图，时间复杂度O（N*logN）空间复杂度O（logN）

总结：三稳定四不稳定。关于常用排序就介绍完了。