一、归并排序
基本思想： 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序使用的是，二叉树后序遍历的思想，归并排序是将区间逐个分解为一个个小区间，直到不能分割为止，然后一步步 归并起来 ，逐层返回。两个有序数组归并：依次比小，小的尾插到新空间
用三指针将两数组合并
归并递归版本
先完成左区间的排序，再完成右区间的排序，最后合并两区间，把tmp数组拷回原数组
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin == end)
{
return;
}
//小区间优化
if (end - begin + 1 < 10)
{
InserSort(a + begin, end - begin + 1);
return;
}
int mid = (begin + end) / 2;
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1, end, tmp);
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}归并非递归版本
我们设定一个 gap ，控制我们的区间大小，gap 就是归并时每组的数据个数。
通过每次改变gap 实际上也就是改变了区间大小，就模拟除了归并递归到底，从小区间合并逐渐到大区间合并的过程。所以我们就让gap 每次 × 2，这样子就是归并每次扩大区间的过程。
使用一个变量i来遍历每一个gap情形下的各个进行归并的序列组(每个序列组由两个子数组构成)
void MergeSortNonR(int* a, int n)
{
int gap = 1;
int* tmp = (int*)malloc(sizeof(int) * n);
while (gap < n)
{
int j = 0;
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
free(tmp);
}可是一旦数组长度不能被整除时就会发生数组越界，比如数组长度为13，gap为4，所以我们需要调整一下
这里我们可以分为三种越界：
1.end1越界，begin2越界，end2越界
2.begin2越界，end2越界
3.end2越界
第一种修正区间，可以归并完了统一拷贝
if (end1 >= n)
{
end1 = n - 1;
//不存在的区间
begin2 = n;
end2 = n - 1;
}
else if (begin2 >= n)
{
//不存在的区间
begin2 = n;
end2 = n - 1;
}
else if (end2 >= n)
{
end2 = n - 1;
}void MergeSortNonR(int* a, int n)
{
int gap = 1;
int* tmp = (int*)malloc(sizeof(int) * n);
while (gap < n)
{
int j = 0;
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
if (end1 >= n)
{
end1 = n - 1;
begin2 = n;
end2 = n - 1;
}
else if (begin2 >= n)
{
begin2 = n;
end2 = n - 1;
}
else if (end2 >= n)
{
end2 = n - 1;
}
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
}
memcpy(a, tmp, sizeof(int) * n);
gap *= 2;
}
free(tmp);
}第二种不修正区间，边归并边拷贝
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}void MergeSortNonR(int* a, int n)
{
int gap = 1;
int* tmp = (int*)malloc(sizeof(int) * n);
while (gap < n)
{
int j = 0;
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
free(tmp);
}归并排序特性及复杂度
对于归并递归版本，每次都是区间二分，然后开始递归的。所以递归层数是严格logN ，每次递归中时间复杂度为O(N) ，所以总体时间复杂度为O(N*logN) ；对于非递归，gap每次乘 2 ，每次 gap 处理的时间复杂度为 O(N) ，时间复杂度也是 O(N *logN)。
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
二、计数排序
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
这里有两种下标处理方式，绝对映射和相对映射
绝对映射就是数据是多少下标就是多少，数组大小为排序数据的最大元素，缺点也很明显，当最大元素很大，或者是出现负数时，就无法映射了，所以这里我们引出了相对映射，相对映射也可以处理负数的情况。
相对映射：
1.找出待排序的数组中最大和最小的元素。
2.统计数组中每个值为 i 的元素出现的次数，存入数组 count 的第 i 项。
3.对所有的计数累加（从 count 中的第一个元素开始，每一项和前一项相加）。
4.反向填充目标数组：将每个元素 i 放在新数组的第 count(i) 项，每放一个元素就将count(i) 减1。
void CountSort(int* a, int n)
{
int min = a[0];
int max = a[0];
for (int i = 1; i < n; i++)
{
if (min > a[i])
{
min = a[i];
}
if (max < a[i])
{
max = a[i];
}
}
int range = (max - min) + 1;
int* arr = (int*)malloc(sizeof(int) * range);
memset(arr, 0, sizeof(int) * range);
for (int i = 0; i < n; i++)
{
arr[a[i] - min]++;
}
int k = 0;
for (int i = 0; i < range; i++)
{
while (arr[i]--)
{
a[k++] = i + min;
}
}
}计数排序特性及复杂度
计数排序的缺陷就是，不能处理整形之外的数据，比如浮点数，字符串，还有数据跨列大时，空间也会浪费
计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
时间复杂度：O(MAX(N,范围)) 。
空间复杂度：O(范围) 。
稳定性：稳定。
排序总结
排序的稳定性：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i] 在r[j] 之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
就是数组前后元素相同时，排完序后两数前后顺序不改变
排序性能测试：
void TestOP()
{
srand(time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
}
int begin1 = clock();
InserSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
BubbleSort(a3, N);
int end3 = clock();
int begin4 = clock();
SelectSort(a3, N);
int end4 = clock();
int begin5 = clock();
HeapSort(a3, N);
int end5 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("BubbleSort:%d\n", end3 - begin3);
printf("SelectSort:%d\n", end4 - begin4);
printf("HeapSort:%d\n", end5 - begin5);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
}
