目录
快排优化2：当递归区间比较小的时候就不再递归用快排方法排序。可以用其他排序处理小区间。
一、插入排序
0-end有序，在end+1位置插入一个数。tmp记录下n+1下标的数。从下标为n开始向前遍历数组，遍历到的数就是每次要和tmp比较的数。
升序：
? ? 1.这个数比tmp大，把这个数往后挪一个位置，然后下标向前，找下一个要比较的数。
?? ?2.这个数比tmmp小，把tmp放该数后面(0-end 本身就有序，所以如果tmp比end小那就直接放到最后，不用跟前面的数比较)
时间复杂度：O（N^2）
最差情况：逆序
最优情况：顺序有序或者接近顺序有序。123456，每个数据都是直接插入到后面，一个都没挪。
最优时间复杂度：O(N)
//插入排序
void InsertSort(int *a, int n)//升序
{
//0-end有序，在end+1位置插入一个数。tmp记录下n+1下标的数。从下标为n开始向前遍历数组，遍历到的数就是每次要和tmp比较的数。
//升序：
//1.这个数比tmp大，把这个数往后挪一个位置，然后下标向前，找下一个要比较的数。
//2.这个数比tmmp小，把tmp放该数后面(0-end 本身就有序，所以如果tmp比end小那就直接放到最后，不用跟前面的数比较)
for (int i = 0; i < n - 1; i++)//外层套个循环，内层只是让一个新来的数插入，使数据有序。
{
int end = i;
int tmp = a[end + 1];//用tmp存储想要插入的数
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp; // 2.这个数比tmmp小，把tmp放该数后面。不能在else位置写，因为有可能走完while循环（一直在调换位置，没进入过else）。end<0,end的下一个位置是这组数的头。
}
}二、希尔排序
升级版的插入排序
1.预排续（接近顺序有序）
???分组，每间隔gap的数据为一组。在一组中的数都间隔gap，在原位置排序。
2.直接插入排序
排升序，gap越小，越接近有序，gap越大，越不接近有序。gap==1的时候直接插入排序，数组有序。
那gap要怎么设计？
gap = gap / 3 + 1;
保证最后一次（gap==1）是直接插入排序，和之前的分组预排不一样。
//希尔排序
void ShellSort(int* a, int n)
{
//1.预排续（接近顺序有序）
//分组，每间隔gap的数据为一组。在一组中的数都间隔gap，在原位置排序。
//2.直接插入排序
int gap=n;
while(gap>1)
{
gap = gap / 3 + 1;//保证最后一次（gap==1）是直接插入排序，和之前的分组预排不一样
for (int i = 0; i < n - gap; i++)//用来更新end，n-gap是这组数的最后一个数， 所以i < n - gap（i是用来控制end的），最后一次插入n-gap位置的数
{
int end = i;
int tmp = a[end + gap];//用tmp存储想要插入的数，0-end有序，插入end的后一个数，就是end+gap
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[gap];
end -= gap;
}
else
{
break;
}
a[end + gap] = tmp;
}
}
}
}时间复杂度：
(精确答案)
因为太复杂了所以我们只进行估算：N*
如果gap每次 /3+1，那就以3为底
如果gap每次 /2，那就以2为底
分析如下：
1.第一层循环：
N/3/3/3/3...==1
3^X==N
X=
?
2.第二层循环：
拿第一次举例子 gap=N/3....
循环n-gap次也就是 3/2 N，时间复杂度就是N
3.第三层循环：
?gap越大，里面的循环几乎可以忽略不计。gap非常大的时候，一步跳3/N，一组数可能是3个，所以第三层循环可以忽略不记。
当gap很小，里面的循环几乎可以忽略不计。gap是1或者2，数列已经很接近有序了，不会进行太多次的调换，很快就break出循环。
三、选择排序
直接选择排序
1. 时间复杂度：O（N^2）
2. 稳定性：不稳定
//直接选择排序
void Swap(int * a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void SelectSort(int * a, int n)
{
assert(a);
int begin = 0, end = n - 1;//遍历的过程中选出一个最大数一个最小数，最小数放到左边，最大数放到右边。begin++，end--，缩小范围往中间逼近
while (begin < end)//奇数个begin==end的时候就结束。偶数个end<begin时结束。
{
int min_i = begin, max_i = begin;//最大数和最小数的下标
for (int i = begin + 1; i <= end; i++)//从第二个数开始比
{
if (a[i] < a[min_i])
{
min_i = i;
}
if (a[i] > a[max_i])
{
max_i = i;
}
}
//走完之后找到begin和end之间 最大的和最小的数
Swap(&a[begin], &a[min_i]);
//max在begin位置的时候就出问题了。先调换min和begin。然后你找到的max位置的数就被换走了
//修正一下
if (begin == max_i)
{
max_i = min_i;
}
Swap(&a[end], &a[max_i]);
begin++;
end--;
}
}插入排序和直接选择排序哪个更好？插入排序
插入排序最优的情况是O（N）? 直接选择排序是O（N^2）。当数列部分有序的时候插入排序是很有优势的。
四、堆排序
首先要建堆。向上调整建堆比较复杂，使用向下调整建堆。
升序建大堆，降序建小堆。
void AdjustDown(HPDataType* a, int size, int parent)
{
int child = parent * 2 + 1;//先假设左孩子是小的那个
while (child<size)//最坏的情况，孩子的下标大于等于size就停止调整
//1.选出左右孩子中小的那一个
{
if (child+1<size && a[child] > a[child + 1])//完全二叉树，最后一个节点可能没有兄弟节点，child+1下标会超出数组范围，形成越界访问。所以增加条件child+1<size
{
child++;//如果右孩子是小的那个，更改child
}
//2.小的孩子和父亲比较，如果比父亲小，交换父亲和孩子
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
//如果孩子比父亲大，调整结束
else
{
break;
}
}
}
void HeapSort（int*a，int n）//n是数组大小
{
for(int i=(n-1-1)/2;i>=0;i--)
{
AdjustDown(a,n,i);
}
}五、冒泡排序
时间复杂度：O（N^2） 最好的情况是O（N）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
//冒泡
void BubbleSort(int *a, int n)
{
assert(a);
for (int j = 0; j < n; j++)//第一次把最大的数换到最后，第二次把次大的数放到倒数第二个位置
{
int exchange = 0;
for (int i = 1; i < n; i++)
{
if (a[i - 1] > a[i]) //相邻两个元素比较
{
Swap(&a[i - 1], &a[i]);//前一个大的话就交换位置，把大的换到后面。
exchange = 1;
}
}
//相邻的数两两相比，exchange==0时，说明没有发生任何一次调换，即数列已经有序，跳出循环，不需要再继续了
if (exchange == 0)
{
break;
}
}
}
六、快速排序
? ?1.hoare版
//快排
int PartSort1(int *a, int begin, int end)//霍尔版
{
int left = begin, right = end;
int keyi = left;//存储key的下标
while (left < right)//等于的时候跳出
{
//右边先走，找比key小的数,找到一个停止
while (a[right] >= a[keyi] && left < right)
{
right--;
}
//左边再走，找比key大的数
while (a[left] <= a[keyi] && left < right)
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);//left==right 下标是哪个都行
keyi = left;//key现在在left下标位置，更新一下keyi
return keyi;
}
void QuikSort(int *a, int begin, int end)
{
//区间不存在或者只有一个值不需要再处理
if (begin >= end)
{
return;
}
int keyi = PartSort1(a, begin, end);
QuikSort(a, begin, keyi - 1);//递归
QuikSort(a, keyi + 1, end);
}1.? ??选出key值，可以选最左边也可以选最右边
? ? ? ? 左边作key，右边先走
? ? ? ? 右边作key，左边先走? ??（后面有解析）
2.? ??排升序的情况：
单趟排完之后，左边的数比key小，右边的数比key。我们选左边第一个数作为key值。定义left和right变量，右边先走，比key大就就继续走，每次找到比key小的数就停止不再继续往前走。左边后走，找到比key大的数就停止。left和right位置的数交换。直到left和right相遇，结束。将key与相遇位置的数交换。key就到了它应该在的位置。更新keyi（key的下标）
3.? ??将数列分为区间：begin——keyi-1? |? keyi? ?|? keyi+1——end
void QuikSort(int *a, int begin, int end)；
使用递归的方式 调整区间左边 ，再右边。
有两种情况不用继续调整，区间没有数（begin==end）或区间只有一个数（begin>end）。
- 数列只有?0 1 位置两个元素，begin==0，end==1
- 假设经过上一轮调整交换，1位置为key，左区间只有一个数，右区间没有数。
- keyi=1? 左区间： 0（begin）——0（keyi-1）? ? 右区间：1（keyi+1）——0（end）?
while (a[right] >= a[keyi] && left < right)
等于key的时候要进去。防止出现死循环
5 5 .........5。一直不进去就会死循环
left<right是为了防止越界。如果right一直往left走，left没动，left和right都在0位置。因为上面加了等于的条件，right进入--，形成越界。所以还要添加left<right条件。
为什么left和right一定会相遇而不是错开？
? ? ? ? ? ? ? ? ? 
? ? ? ? ??
?这个是直接选择排序的部分代码。在这个while循环里，begin和end是同时往中间逼近的。每次一步。所以有可能相遇，也有可能错开。
而我们这个版本的快速排序是右边先走，左边再走。一方在走的时候一方是停止不动的。所以他们一定会相遇。
为什么左边作key就要从右边先走？
我们排升序，左边应该是小的数。在这个版本的排序中left和right相遇时，需要交换keyi位置（左边第一个数）和相遇位置的数。 排升序，需要左边都比key小，右边都比key大?。
相遇位置的数要去左边第一个，所以一定要是比key小的数。?
左边做key右边先走是为了保证相遇位置的数是比key小的数或者就是key的位置。? ? ? ? ? ?
情况一：R先走，停下来。L再走，遇到了R。R在的位置就是比key小的数。
情况二：R先走，一直没有找到比key小的数，R遇见了L。
在这里面又分了两种情况：
1.R直接走到了key的位置，L没动过，L和R相遇。相遇位置就是key应该在的位置
2.R先走，找到一个小数，停止，L再走，找到一个大数，停止。交换两数。这时候L所在的位置放的是一个比key小的数。进入下一次循环，R先走，再也没有遇到比key小的数了，R去和L相遇。相遇位置的数就是比key小的数
2.挖坑法
//挖坑法
int PartSort2(int *a, int begin, int end)
{
int key = a[begin];
int piti = begin;
while (begin < end)//相遇时跳出，大体思路和霍尔版差不多
{
while (begin < end && a[end] >= key)//找到大的往前走，找到小的停止
{
end--;
}
//找到一个数放到坑里，并更新坑的位置
a[piti] = a[end];
piti = end;
while (begin < end && a[begin] <= key)//找到小的往后走，找到大的停止
{
begin++;
}
//找到一个数放到坑里，并更新坑的位置
a[piti] = a[begin];
piti = begin;
}
//begin和end相遇，相遇位置一定是坑，因为end和begin其中一个一定是坑。
//把key填到坑里
a[piti] = key;
return piti;
}
void QuikSort(int *a, int begin, int end)
{
//区间不存在或者只有一个值不需要再处理
if (begin >= end)
{
return;
}
int keyi = PartSort2(a, begin, end);
QuikSort(a, begin, keyi - 1);//递归
QuikSort(a, keyi + 1, end);
}? ? ?
大体思路还是和hoare版一样。左边作key从右边开始先走。左边比key小的数，找到停止。把这个数放到坑里，该数位置形成新坑，更新坑位置。右边再走，找比key大的数，找到放坑里，更新坑位置。直到end和begin相遇。把key放到相遇位置的坑里。??
挖坑法和霍尔版两种方法在排序过程中可能排出来的不一样。选择题可能出不定项选择，所以只明白一种思路是不够的。
例：
7 3 8 9 1 2
挖坑法：第一次排出来? ?2?3 1 7 9 8
霍尔版：第一次排出来???1 3 2 7 9 8
快排优化1：三数取中选key
数列有序或接近有序，如果选固定位置（最左边或最右边第一个作key），key每次都是排序后的最大数或最小数。
N +N-1+N-2+...1
时间复杂度：O（N^2）
快排问题2：数据量大的时候还容易栈溢出
解决方法：
1.随机选key
2.三数取中。第一个 中间 最后一个。选不是最大也不是最小的那个
int GetMidIndex(int *a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[end] < a[begin])
{
return begin;
}
else if (a[mid] < a[end])
{
return mid;
}
else
{
return end;
}
}
else//a[begin]>=a[mid]
{
if (a[end] > a[begin])
{
return begin;
}
else if (a[mid] > a[end])
{
return mid;
}
else
{
return end;
}
}
}快排优化2：当递归区间比较小的时候就不再递归用快排方法排序。可以用其他排序处理小区间。
区间小于10个数时，不再递归，可以减少80%以上的递归次数。使用插入排序。
在sort.h文件中声明? extern int CallCont；
对下面的前后指针法快排进行优化举例
3.前后指针法
//前后指针法
int PartSort3(int * a, int begin, int end)
{
int keyi = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end)
{
//cur找到的数比key小就停下，然后prev往前走一步，再把prev位置的大数和cur位置的小数交换。prev位置一直是大小数的分界线。调整结束后prev包括prev之前的全是小数，除了第一个的key数值。prev之后的全是大数。
while (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
??cur找到的数比key小就停下，然后prev往前走一步，再把prev位置的大数和cur位置的小数交换。prev位置一直是大小数的分界线。调整结束后prev包括prev之前的全是小数，除了第一个的key数值。prev之后的全是大数。
4.前后指针法优化版本（三数取中和小于10数用插入排序）
//插入排序
void InsertSort(int *a, int n)//升序
{
//0-end有序，在end+1位置插入一个数。tmp记录下n+1下标的数。从下标为n开始向前遍历数组，遍历到的数就是每次要和tmp比较的数。
//升序：
//1.这个数比tmp大，把这个数往后挪一个位置，然后下标向前，找下一个要比较的数。
//2.这个数比tmmp小，把tmp放该数后面(0-end 本身就有序，所以如果tmp比end小那就直接放到最后，不用跟前面的数比较)
for (int i = 0; i < n - 1; i++)//外层套个循环，内层只是让一个新来的数插入，使数据有序。
{
int end = i;
int tmp = a[end + 1];//用tmp存储想要插入的数
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp; // 2.这个数比tmmp小，把tmp放该数后面。不能在else位置写，因为有可能走完while循环（一直在调换位置，没进入过else）。end<0,end的下一个位置是这组数的头。
}
}
//前后指针法 加入三数取中的优化
int PartSort3(int * a, int begin, int end)
{
CallCount++;
int keyi = begin;
int prev = begin;
int cur = begin + 1;
int midi = GetMidIndex(a, begin, end);
Swap(&a[keyi], a[midi]);
while (cur <= end)
{
//cur找到的数比key小就停下，然后prev往前走一步，再把prev位置的大数和cur位置的小数交换。prev位置一直是大小数的分界线。调整结束后prev包括prev之前的全是小数，除了第一个的key数值。prev之后的全是大数。
while (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}
void QuikSort(int *a, int begin, int end)
{
//区间不存在或者只有一个值不需要再处理
if (begin >= end)
{
return;
}
if (end - begin > 10)
{
int keyi = PartSort3(a, begin, end);
QuikSort(a, begin, keyi - 1);//递归
QuikSort(a, keyi + 1, end);
}
else
{
InsertSort(a, end - begin + 1);
}
}
以上是递归版快排。
递归的问题：深度太深会栈溢出
1.改成循环
2.用数据结构模拟——用栈或队列都行
4.用栈实现快排
?
void QuickSortNonR(int *a, int begin, int end)
{
ST st;
StackInit(&st);
StackPush(&st, end);
StackPush(&st, begin);
while (!StackEmpty(&st))
{
int left = StackTop(&st);
StackPop(&st);
int right = StackTop(&st);
StackPop(&st);
int keyi = PartSort3(a, left, right);//调整一次，二分区间
//left——keyi-1? |? keyi? ?|? keyi+1——right
if (keyi + 1 < right)//区间有数
{
StackPush(&st, right);
StackPush(&st, keyi + 1);//先入左还是入右都一样。先入左再入右，取栈顶的时候就是右->左。根左右
}
}
StackDestroy(&st);
}栈是像前序遍历。
队列像层序遍历。
七、归并排序
1.递归版
有点像后序，先不断往下递归，到头了开始归并，再往上走。
归并两个有序数组。双指针，创建新数组归并，再拷贝回原数组。
从开始的1 1归并成2数一组。2 2再归并，成4数一组......最终所有数都被归并成有序的。
时间复杂度：N*logN? ?
深度logN，每一层不管是一个一个归，还是两两归，遍历数组时加起来大概都是循环N次来把数组走完。递归里面套循环，所以就是乘。
void _MergeSort(int *a, int begin, int end, int *tmp)
{
if (begin >= end)//区间只有一个数或者没有数就停止
{
return;
}
int mid = (begin + end) / 2;
//[begin , mid] [mid+1 , end] 分治递归，让子区间有序。先往下递归二分，最后到头了往回走开始排序归并。
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1, end, tmp);
//归并
int begin1 = begin,end1=mid;
int begin2 = mid + 1, end2 = end;
int i = begin1;//i是tmp下标。不一定是从0开始。因为归并的两个组可能是 8-9 和 10-11
while (begin1 <= end1 && begin2 <= end2)//有一组走完就会跳出
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)//走到这一步有可能两组数都拷完了。也有可能只有一组先走完，没走完的一组本来就是有序的，剩下的数也有序，直接挨个往tmp拷就行。
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)//这两个循环，谁没走完谁进来，只能进来一个。至于到底哪个没走完，都写上就不用思考了。
{
tmp[i++] = a[begin2++];
}
//拷回原数组a
memcpy(a, tmp, (end - begin1 + 1) * sizeof(int));
}
void MergeSort(int *a, int n)
{
int *tmp = (int *)malloc(sizeof(int)*n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}2.非递归版（循环版）
用栈？跟快排一样？用栈去模拟适合前序(队列适合层序)不适合后序。快排是选出一个key，找出左区间和右区间。归并是先分区间，往回返的时候开始归并。用栈的话，先把区间入进去，又拿出来继续处理分割。当要归并的时候就找不到区间了。
递归最终分出来的区间一定是一个数，一个数。我们自己用循环先两两归并->变成两两有序
归完了把数据拷贝回去
把两两有序的一组和另一组再进行归并? ->? 每组四个数有序
四数一组再和另一组归并? ->? 每组八个数有序
........
1.数组总大小不是2的次方倍都会越界。
1 3 5 2 7 6这组数一 一归并时没问题。二二归并，【1 3】和【5 2】归并。如果还是按照计算【7 6】和越界的一组数归并。
所以我们需要通过调整边界来防止越界
2.循环的归并并不是严格的二分。
10，6，7，1，3，9，4，2，5，6 （共10个数）
下标0-7一组，那右边区间按照严格二分应该是8-15。但右区间真的有这么多数吗？实际只有两个数。 在循环归并中，几个跟几个归都有可能。4个和2个。4个和4个。
除了begin1（由i控制，所以在数组下标范围内）。end1，begin2，end2都有可能越界。
如果区间只剩一个数了还需要归并吗？?
10， 6，7 ，1，3，9，4，2，5 （共9个数）
下标：【0 1】-【2 3】? ?【4 5】-【6 7】? ?【8 9】-【10 11】? ? ? ? ? ? ?（9-11越界）
取决于是tmp整体往回拷贝，还是归并一次就往回拷贝一次的局部拷贝。
整体拷需要。通过归并的过程把数放在tmp里，每组归并都结束后，最后把tmp完全拷到a，如果这个数没有进行归并过程的话，就没有放到tmp里，tmp里放的就是随机值，拷到a里也拷回去一个随机值。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
局部拷不需要。
所以两种方法对于越界的处理是不一样的。
怎么修正？? ? ? ? ? ?
10， 6，7 ，1，3，9，4，2，5 ，6（共10个数）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
下标：【0 -?3】? -?【4 -7】? ? ? 【8?-11】?-【12- 15】?? ??
end1越界，begin1和end1也越界。如果这样修正：end1=n-1，begin2=end2=n-1。
【8 9】-【9?9】?是不行的
这样处理相当于2个数和1个数归并。（把9位置的数多归并了一次，相当于给数组又加了一个和9位置数相等的数进行归并）。但tmp大小有限，我们不知道8 9位置谁大谁小，也就不能保证放进去的是有序的8和9，还是两个9 9。?
整体拷：
局部拷：
?整体拷：
void MergeSortNonR(int *a, int n)
{
int *tmp = (int *)malloc(sizeof(int)*n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
int gap = 1;
while (gap < n)//一个gap最多就是n-1个数，这时右区间没有数
{
for (int i = 0; i < n; i += 2 * gap)//跳两个gap（一个小组中的两组数已经归并完成），进行下一小组的归并
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, 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)//必须是else if。因为如果是else，前期没越界也会进去修正一下。
{
end2 = n - 1;
}
//归并
int j = begin1;//j是tmp下标。不一定是从0开始。因为归并的两个组可能是 8-9 和 10-11
while (begin1 <= end1 && begin2 <= end2)//有一组走完就会跳出
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)//走到这一步有可能两组数都拷完了。也有可能只有一组先走完，没走完的一组本来就是有序的，剩下的数也有序，直接挨个往tmp拷就行。
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)//这两个循环，谁没走完谁进来，只能进来一个。至于到底哪个没走完，都写上就不用思考了。
{
tmp[j++] = a[begin2++];
}
}
memcpy(a, tmp, sizeof(int)*n);
gap *= 2;
}
free(tmp);
}局部拷：
void MergeSortNonR(int *a, int n)
{
int *tmp = (int *)malloc(sizeof(int)*n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
int gap = 1;
while (gap < n)//一个gap最多就是n-1个数，这时右区间没有数
{
for (int i = 0; i < n; i += 2 * gap)//跳两个gap（一个小组中的两组数已经归并完成），进行下一小组的归并
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap-1;
//end1越界或begin2越界，就可以不归并了
if (end1 >= n || begin2 >= n)
{
break;
}
else if (end2 >= n)
{
end2 = n - 1;
}
//局部拷要记录个数
int m = end2 - begin1 + 1;
//归并
int j = begin1;//j是tmp下标。不一定是从0开始。因为归并的两个组可能是 8-9 和 10-11
while (begin1 <= end1 && begin2 <= end2)//有一组走完就会跳出
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)//走到这一步有可能两组数都拷完了。也有可能只有一组先走完，没走完的一组本来就是有序的，剩下的数也有序，直接挨个往tmp拷就行。
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)//这两个循环，谁没走完谁进来，只能进来一个。至于到底哪个没走完，都写上就不用思考了。
{
tmp[j++] = a[begin2++];
}
memcpy(a + i, tmp + i, sizeof(int)*m);
}
//memcpy(a, tmp, sizeof(int)*n);//整体拷在这里
gap *= 2;
}
free(tmp);
}八、计数排序
统计a数组每个数出现的次数，按出现次数写回原数组。
采用相对映射：100 ，100，102，103，104，105
cout 位置0下标表示该数是100
1下标表示101
2下标表示102
.........
| count数组 | 2 | 0 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|---|---|
| count数组下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| count数组下标所映射的数 | 100 | 101 | 102 | 103 | 105 | 105 |
找a数组中最大数和最小数，算出数值范围，开辟一个能映射出所有a数组数的count数组。
将a数组里存储的数和count数组的下标建立映射关系，并用count数组存储该数的出现次数。count下标位置存储该数的个数，下标加min就是该数的大小。
时间复杂度：O（max（n,range））
找大小O（N），统计次数O（N），回写排序O（range）
空间复杂度：O（range）
void CountSort(int*a, int n)
{
int min = a[0], max = a[0];
for (int i = 1; i < n; i++)//找最大数和最小数，算出数值范围
{
if (a[i] < min)
{
min = a[i];
}
if (a[i] > max)
{
max = a[i];
}
}
int range = max - min + 1;
int *count = (int*)malloc(sizeof(int)*range);//开辟一个计数数组
if(count==NULL)
{
printf("malloc fail\n");
exit(-1);
}
memset(count, 0, sizeof(int)*range);//全都初始化成0
//统计次数
//这个数是几，映射的位置就是该数减min——相对映射。绝对映射：这个数是几就放到几的位置。
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
//回写排序
//count下标位置是该数的个数，下标加min就是该数的大小
int j = 0;
for (int i = 0; i < range; i++)
{
//count数组，i下标位置的数村的是几就往回写几次，下标加min就是该数的大小
while (count[i]--)
{
a[j++] = i + min;
}
}
}