排序
前面我们已经了解了排序中的插入排序，选择排序以及交换排序。本篇文章将介绍剩下的归并排序和非比较排序中的计数排序，同时介绍各种排序算法的稳定性，并对排序进行一下总结。
一.归并排序
概念
归并排序是指将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
算法分析及实现
归并思想是对两个已经有序的数组进行合并，重新组成一个新的有序的数组，因此归并算法的根本思想是将要排序的数组划分成多个已经有序的数组，然后在一一进行归并，最后得到一个有序的数组。因此，归并排序的算法实现就很明显了：在归并算法中我们借助一个临时数组来存储有序的序列，最后将这个数组的内容拷贝到原数组中即可。
故归并排序的代码为：
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)//只有一个元素时，结束递归
return;
int mid = (left + right) / 2;
//先将区间划分为[left, mid] 和 [mid + 1, right]两个部分
//递归[left, mid] 使左半部分有序
_MergeSort(a, left, mid, tmp);
//再递归[mid + 1, right] 使右半部分有序
_MergeSort(a, mid + 1, right, tmp);
//将递归的区间归并
int index = left;
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
//此时[begin1, end1] 和 [begin2, emd2]两个区间已经有序
//将两个区间归并为一个有序的数组
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
//将tmp数组拷贝到原数组中
int i = 0;
for (i = left; i < index; i++)
{
a[i] = tmp[i];
}
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}
这里用MergeSort函数本身递归不方便，因此使用一个子函数来实现递归，从而达到我们想要达到的目的。
非递归算法实现
在学习斐波那契数列的代码实现时，我们知道有两种方式即递归和非递归。其中斐波那契数列的递归实现是通过F(n) = F(n - 1) + F(n - 2)这个公式实现的，但在实际运行中n取到几十就会造成栈溢出了。因此需要采用改成非递归的形式来优化代码，即从n = 0 开始循环到n计算斐波那契数列。
同样的对于归并排序的非递归实现我们可以借鉴斐波那契的思想，即引入一个变量groupNum来记录每次归并的数据长度，让groupNum从1开始循环到n（当然有可能不会整除，但没关系）,从而实现归并排序的非递归代码。
因此，归并排序的非递归代码为：
//非递归版本
void MergeSortNonR(int* a, int n)
{
//临时数组拷贝要归并的数据
int* tmp = (int*)malloc(sizeof(int) * n);
int groupNum = 1;
while (groupNum <= n)
{
for (int i = 0; i < n; i += groupNum * 2)//每趟归并的间隔 * 2
{
//归并区间[begin1, end1] 和 [begin2, end2]
int begin1 = i, end1 = i + groupNum - 1;
int begin2 = i + groupNum, end2 = i + groupNum * 2 - 1;
//考虑边界
//1.区间[begin2, end2]不存在
if (begin2 >= n)
{
//进行修改，构造一个不存在的区间
begin2 = n;
end2 = n - 1;
}
//2.end1越界
if (end1 >= n)
{
//修改end1使之不越界
end1 = n - 1;
}
//3.end2越界
if (end2 >= n)
{
//修改end2使[begin2, end2]合理
end2 = n - 1;
}
//归并
int index = begin1;//从下标为begin1的元素开始
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
}
//每次归并完后将tmp数组拷贝回a数组
for (int i = 0; i < n; i++)
{
a[i] = tmp[i];
}
groupNum *= 2;//每次归并后组距*2
}
free(tmp);
}
这里需要注意的是对于边界的处理，注意理清逻辑上的层层递进。
小结
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
二.计数排序
概念
前面介绍的排序都是通过比较大小对数组进行排序的，接下来我们要来介绍一种不通过比较的排序算法，即计数排序。
计数排序，顾名思义，就是统计数组中每个元素出现的次数,然后根据每个元素出现的次数进行排序的方法。
算法分析
计数排序的代码实现是比较简单的，只需要统计每个数字出现的次数，再还原到原数组去即可。
需要注意的时当数组中的数字过大时，我们可以将这个数组映射到[0, max - min]这个范围的数组中去。
因此，计数排序的代码实现为：
void CountSort(int* a, int n)
{
//找数组中的最大值和最小值
int i = 0;
int max = a[0];
int min = a[0];
for (i = 0; i < n; i++)
{
if (min > a[i])
min = a[i];
if (max < a[i])
max = a[i];
}
//将数组a中的元素映射到下标为[0, max - min]的数组中
int range = max - min + 1;//count数组的元素个数
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL)
{
printf("calloc fail\n");
exit(-1);
}
//遍历数组a，记录下每个数字出现的次数
for (i = 0; i < n; i++)
{
count[a[i] - min]++;
}
//根据count数组将原数组进行排序
int index = 0;
for (i = 0; i < range; i++)
{
while (count[i]--)
{
a[index++] = i + min;
}
}
free(count);
}
小结
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(MAX(N,范围))
- 空间复杂度：O(范围)
实际上，计数排序的使用只有在待排序的数据相对比较集中且出现次数较多的情况下，因此使用场景十分有限。
排序算法的稳定性
一.稳定性的概念
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
二.分析各种排序算法的稳定性
1.直接插入排序
稳定性：稳定。
直接插入排序由于是将要排的数插入到已经排好的序列中，因此相同的数的顺序和原先的相同。
2.希尔排序
稳定性：不稳定
由于希尔排序进行预排序时，若有相同的数在不同的组，这时相同数的相对顺序可能会发生改变，因此，希尔排序是不稳定的。
3.直接选择排序
稳定性：不稳定
每次从后面选出最值交换时，可能会导致相同的数的原先顺序改变，因此算法是不稳定的。
4.堆排序
稳定性：不稳定
堆排序无论是在调整堆时，还是在建堆过程中，抑或是堆顶元素于最后一个元素交换时都可能导致相同的数的相对位置发生变化，因此其是不稳定的。
5.冒泡排序
稳定性：稳定
冒泡排序每一趟都是将最大的数冒到数组末尾，在此过程中若有相同的数不发生交换，则保证了排序算法的稳定性。
6.快速排序
稳定性：不稳定
快速排序在划分区间时，如果从右往左比从左往右更快遇到相同的数，那么其相对顺序将发生改变，因此快速排序是不稳定的。
7.归并排序
稳定性：稳定
归并排序对于要归并的两个区间，若遇到相同的数，只需要将前面区间的数先归并即可保证排序的稳定性。
注：所有算法都可以是不稳定的，但有的排序算法可以保证稳定性，因此我们讨论这种可以稳定的情况。
三.稳定性的意义
在日常生活中我们可能依据多种关键值来排序，比如年龄，姓名等。如果已经按照姓名排好了顺序，再依据年龄排序，若排序是不稳定的，那么相同年龄的人的原先顺序可能会被打乱，那么这样的排序算法是不够优秀的。因此，排序的稳定性是很有意义的。
总结
