目录
1.快速排序（hoare法）
单趟：
（一般）以第一个值为key，通过一系列操作让比它大的值全在其右边，比它小的都在左边
操作方法：定义两个指针left、right，left找大right找小，当找到了2个值以后，交换两个位置的元素；这样操作到left、right相遇，然后把begin位置的key值和left位置的元素交换
此时key值已经排序完成了，因为其左边都是较小值，右边都是较大值
int left = begin, right = end;
int keyi = begin;
while (left < right)//相等时结束循环
{
while (left < right && a[right] >= a[keyi])right--;//left不能大于right
while (left < right && a[left] <= a[keyi]) left++;
//必须要先走右指针，再走左指针
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]); 
整体：
因为key已经排序完了，所以只需要对key的左右区间分别排序即可；对其左右区间分别再次进行快排，一整个问题可以由无数个子问题组成，不难想到使用递归实现
递归出口：begin >= end
如图，此时上一步是 begin = 0，end = 1，left(keyi) = 1；进入到递归调用函数以后，往左递归是(a,0,0) -> 一个单值，往右递归是(a,2,1) -> 不存在值
void QuickSort(int* a, int begin, int end)
{
if (begin >= end) return;
int left = begin, right = end;
int keyi = begin;
while (left < right)//相等时结束循环
{
while (left < right && a[right] >= a[keyi])right--;//left不能大于right
while (left < right && a[left] <= a[keyi]) left++;
//必须要先走右指针，再走左指针
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
QuickSort(a, begin, left - 1);
QuickSort(a, left + 1, end);
}代码优化：
优化1：三数取中
如上图，对于有序的数组，key值永远都取整个区间的最开头一个；（如果是升序）right会直接往左移动到key值位置，因此第一次的循环为N次；
接下来左区间没有东西，往右区间走，又是以开头值为key值，循环N-1次；然后左边区间没有东西（区间begin = 1 ，此处不是看数组来判断的），右边区间又是以开头值为key值……
整体时间复杂度会达到惊人的"N + (N - 1) + …… + 2 + 1 = O(N^2) ,
同时因为每次函数递归调用都需要开辟一个函数栈帧，N个数据的有序数组就得开辟N个栈帧；debug版本（栈帧带着调试信息）下，100000个栈帧就会栈溢出
因此我们可以通过在begin end mid 三个位置中找中间大小的数据，把他作为key值来解决这个问题（数组有序时，key值作为中间大小，能够左右区间都有数据去快排）
优化2：小区间优化
假设每次对某一个区间快速排序完，key都落在了中间位置，那我们可以把函数递归调用看作是一棵完全二叉树在进行先序遍历（当中key值为父节点，左右区间为父节点的左右子树）
如下图，根据完全二叉树的特点，最后一层根节点占到了所有节点的50%，倒数第二层占了25%；由于倒数几层的递归调用开销很大，因此最后几层我们可以不使用快速排序，改用别的排序方法
希尔排序主要用来排大量数据，冒泡快速太拉了，堆排还需要创建堆然后才能排序（每个区间都要创建堆，时间开销比较大），归并排序也得要递归调用，所以插入排序是最好的选择（c++sort函数用的就是插入排序+快排）
三数取中代码：
int GetMid(int* a, int left, int right)
{
int midi = (right - left) / 2;
if (a[left] < a[midi])
{
if (a[midi] < a[right]) return midi;
else if (a[left] < a[right]) return right;
else return left;
}
else //a[left] > a[midi]
{
if (a[midi] > a[right]) return midi;
else if (a[left] < a[right]) return left;
else return right;
}
}
void QuickSort(int* a, int begin, int end)
{
……;
int midi = GetMid(a, begin, end);
Swap(&a[begin], &a[midi]); //key值一定要放在最开头/最末尾的位置
……;
}
小区间优化代码：
if ((end - begin + 1) <= 10) InsertSort(a + begin, end - begin + 1); 只要递归到某一个区间，区间内数据量小于等于10，就停止快排使用插入排序
如果传参传的是a+4，那么在InsertSort函数里，a[0]（函数里逻辑上的数组） = a[4]（实际存储空间里的数组）
hoare法疑问解答：
疑问1：为什么key值一定要放在区间头/尾？
如果key放在中间位置，前面有值，那么有可能left、right在key值前面相遇，本来应该放在key值左边的元素现在放到key值右边了，肯定会出问题
疑问2：为什么key放在区间头，一定要右指针先移动呢？
key值由于放在头部，因此在左右指针相遇后，相遇位置处的值需要小于key值，这样才能保证key左边都是比它小的，右边都是比它大的
右指针是专门去找小的指针，一般性会有以下3种情况：
1.right找到小的以后，left不断找大，一直没找到直到和right相遇 -> 相遇位置值比key小
2.left、right位置的值已经交换过数对，right不断找小一直没找到，与left相遇后由于前一次left、right（新一次找小开始的位置）的交换，当前left所指向的值依旧小于key值
3.left一次也没动过，right不断找小，一直没找到直到与left相遇，此时相当于key和key自己进行了一次位置交换
记忆方法：左边key右边先走，右边key左边先走
2.快速排序（挖坑法）
没有效率提升，但很多hoare法带来的疑问不需要分析了，因此比较好理解
3.快速排序（前后指针法）
1.搞一个prev指针，再搞一个cur指针，初始都在begin位置
2.cur找大（比key大），cur和prev同步向后走，直到cur找到大
3.cur从找大变成找小，大的cur往后走prev不动(由于每次肯定cur先走，所以prev的限制是比较容易的），找到小的让prev先++，然后进行位置交换，此时就类似于把大于key的值翻滚往后移动
4.cur遍历完数组，交换prev和keyi位置元素
如果初始化时cur = begin + 1，那么就用后置++特性，自己和自己交换也可以
int prev = begin, cur = begin ;
int keyi = begin;
while (cur <= end)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
cur++;
}
Swap(&a[prev], &a[keyi]);
性能分析：
时间复杂度：O(NlogN)，总共有logN层，每层需要遍历N个数
空间复杂度：O(logN)，需要开辟logN个栈帧
全部代码（递归版）：
int PartSort1(int* a, int begin, int end)
{
int left = begin, right = end;
int keyi = begin;
while (left < right)//相等时结束循环
{
while (left < right && a[right] >= a[keyi])right--;//left不能大于right
while (left < right && a[left] <= a[keyi]) left++;
//必须要先走右指针，再走左指针
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
return left;
}
int PartSort2(int* a, int begin, int end)
{
int prev = begin, cur = begin ;
int keyi = begin;
while (cur <= end)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end) return;
int midi = GetMid(a, begin, end);
Swap(&a[begin], &a[midi]); //key值一定要放在最开头/最末尾的位置
if ((end - begin + 1) <= 10) InsertSort(a + begin, end - begin + 1);
//hoare法
int left = PartSort1(a, begin, end);
//前后指针法
//int left = PartSort2(a, begin, end);
QuickSort(a, begin, left - 1);
QuickSort(a, left + 1, end);
}4.快速排序（非递归）
非递归一般使用栈or队列来完成
每次递归最重要的就是区间的起始下标与终止下标
所以我们可以：循环没走一次，取栈顶空间，单趟排序然后左右子区间的起止下标入栈[begin, keyi-1] keyi [keyi+1, end] 左右区间后进先出，所以begin如果要先出就得插入时后插入
typedef struct Stack
{
int* a; //动态开辟
int top; //栈顶
int capacity; //可容纳空间
}st;
void Stinit(st* pst)
{
assert(pst);
pst->a = NULL;
pst->capacity = 0;
pst->top = -1;
}
void Stdestory(st* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = 0;
pst->top = -1;
}
void Stpush(st* pst, int x)
{
assert(pst);
//扩容
if (pst->top + 1 == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
int* tmp = (int*)realloc(pst->a, sizeof(int) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[++pst->top] = x;
}
void Stpop(st* pst) //用函数进行封装，易于管理与理解
{
assert(pst);
pst->top--;
}
int Sttop(st* pst)
{
assert(pst);
assert(pst->top >= 0);
return pst->a[pst->top];
}
bool Stempty(st* pst)
{
assert(pst);
return pst->top == -1;
}
int Stsize(st* pst)
{
assert(pst);
return ++pst->top;
}
void QuickSortNON(int* a, int begin, int end)//非递归写法
{
st s;
Stinit(&s);
Stpush(&s, end);
Stpush(&s, begin);
while (!Stempty(&s))
{
int left = Sttop(&s);
Stpop(&s);
int right = Sttop(&s);
Stpop(&s);
//区间下标的获取
int keyi = PartSort2(a, left, right);
// [begin, keyi-1] keyi [keyi+1, end]
if (keyi + 1 < right)//放入右区间的起止下标
{
Stpush(&s, right);
Stpush(&s, keyi + 1);
}
if (left < keyi - 1)//放入左区间的起止下标
{
Stpush(&s, keyi - 1);
Stpush(&s, left);
}
}
}非递归就是从dfs变成了bfs
因为非递归不需要创建函数栈帧，所以没有栈溢出风险；同时栈、队列这类数据结构，空间开辟在堆区，在4G内存中堆区大小为2GB，因此空间大小可以支持更多的数据进行排序
5.归并排序
1.把数组平分成两块，然后对两块分别再平分
2.分到不可再分，开始归
3.归时进行小区间的排序，小区间合并成大区间以后，再对大区间进行排序，以此类推……
4.需要创建一个temp数组进行排序（例如2个数的区间，小的先放进temp，再放大的，自然排序完成了；大的区间，因为左右区间都有序了，所以比较放入temp时也是比较容易的）
5.平分成一个个小区间可以通过递归来实现（子问题是大区间平分成小区间，然后归并成大区间）
void _MergeSort(int* a, int* temp, int begin, int end)
{
//分->exit
//递归出口理由同快排
if (begin >= end) return;
//分->init
int midi = (begin + end) / 2;//二分
//分->r&t
_MergeSort(a, temp, begin, midi);
_MergeSort(a, temp, midi+1, end);
//归并+排序
int begin1 = begin, end1 = midi;//左区间
int begin2 = midi + 1, end2 = end;//右区间
int i = 0;//temp数组下标从0开始
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++];
memcpy(a + begin, temp, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
int* temp = (int*)malloc(n * sizeof(int));
if (!temp)
{
perror("malloc error");
return;
}
_MergeSort(a, temp, 0, n - 1);
free(temp);
temp = NULL;
}代码重点解释：
[begin,midi-1][midi,end]这样来区间划分会导致死循环（如下图1）
最后一层{2,3}的右区间会不断形成{2,3}，a[midi] = 2 a[end] = 3
while (begin1 <= end1) temp[i++] = a[begin1++];
while (begin2 <= end2) temp[i++] = a[begin2++];根据循环退出条件，此时肯定还有一个区间有值，把剩下来没有放进（具体如下图2）
memcpy(a + begin, temp, (end - begin + 1) * sizeof(int));
将结果放入原数组（原数组需要从begin下标处开始覆盖，temp每次新值会覆盖旧值，所以可以多次使用）
性能分析：
时间复杂度：N*logN
某一层假设有4个小区间，每个小区间都遍历一遍相当于数组遍历了一边，时间复杂度为 N
递归看成完全二叉树，总共是进行了 logN 次区间遍历，因此时间复杂度为nlogn
空间复杂度：N
归并排序是一种外排序
假设只有1G内存，把4G的大文件拆分成4个1G的小文件，对4个小文件分别进行排序（用更快的，例如希尔）
然后再对4个小文件使用归并排序，归并成一个大文件，4G的数据就有序了
能够通过小内存来处理大数据的，我们一般称为外排序（可以理解成用内存来完成磁盘的活）
6.归并排序（非递归）
归并的递归不使用栈和队列这类数据结构
快排是操作+左右递归 -> 先序遍历
归并是左右递归+操作 -> 后序遍历
难以通过栈来实现后序遍历，因为后序遍历就决定了得先把下标依次全都放进栈，然后才能操作，使用栈无法实现归并的操作
因此我们可以使用希尔排序的思想，将数据之间看作是多个区间对，例如4个数的数组： [0,1][2,3] -> [0,0][1,1] [2.2][3.3] 从右往左，先是两个数一块排，再是4个数一块排
因此我们可以用到gap作为区间值的距离
[i,i+gap-1][i+gap,i+2*gap-1] 数组下标从0开始算，所以区间终止位置下标需要-1
其余思想与递归实现相同
void MergeSortNON(int* a, int n)
{
int* temp = (int*)malloc(n * sizeof(int));
if (!temp)
{
perror("malloc error");
return;
}
int gap = 1;
while (gap < n)
{
for (int i = 0;i < n;i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;//左区间
int begin2 = i + gap, end2 = i + 2 * gap - 1;//右区间
int j = 0;//temp数组下标从0开始
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++];
memcpy(a + i, temp, (end2 - i + 1) * sizeof(int));//这边i不能用begin，begin已经被修改掉了
}
gap *= 2;
}
free(temp);
temp = NULL;
}当数组的数据不是2的倍数时，有可能会导致数组越界，以下是数组越界的三种情况：
假设有一个有10个数据的数组，归并排序时会出现以下几个越界：
如上图所示，对应了错误2、错误3 [8,9][10,11] & [8,11][12,15]
此时，因为[8,9]区间的值通过前一步的操作已经有序了，所以可以直接结束本次循环（即不用归并）；只有begin1没有越界or第二组越界，end1越界begin2必越界，所以可以放在一个判断语句里判断 -> 不需要归并了，用break就好不用continue，因为越界肯定发生在最后一组区间对上
如上图所示，对应了错误1
此时[0,7][8,9]需要进行归并，所以我们可以手动将 end2 赋为 n-1
全部代码：
void MergeSortNON(int* a, int n)
{
int* temp = (int*)malloc(n * sizeof(int));
if (!temp)
{
perror("malloc error");
return;
}
int gap = 1;
while (gap < n)
{
for (int i = 0;i < n;i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;//左区间
int begin2 = i + gap, end2 = i + 2 * gap - 1;//右区间
if (begin2 >= n) break;
if (end2 >= n) end2 = n - 1;
int j = 0;//temp数组下标从0开始
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++];
memcpy(a + i, temp, (end2 - i + 1) * sizeof(int));//这边i不能用begin，begin已经被修改掉了
}
gap *= 2;
}
free(temp);
temp = NULL;
}7.计数排序（非比较排序）
1.搞一个count数组
2.count数组下标对应的就是原数组中某一个元素，count数组某个下标所对应的元素大小即原数组中某一元素个数
3.原数组里的值都比较大的话，可以通过 count[a[i]-min] 来优化 min为原数组中的最小元素（图）
4. 3 9 100 105 这个数组依旧可以完成排序，min = 3 max = 105 range = 102，105->[102] 100->[97] 9->[6] 3->[0]
5.负数range范围能概括到，并且i+min可以减到负数，因此负数也可以用该办法进行排序
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*)calloc(range, sizeof(int));
if (!count)
{
perror("calloc error");
return;
}
//统计出现次数
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;
}
free(count);
count = NULL;
}calloc(range, sizeof(int))是带初始化的malloc，相当于malloc + memset(count, 0, range * sizeof(int))
性能分析：
时间复杂度：range + N （range是对count数组遍历，原数组N个数，因此还需要 +N ）
空间复杂度：range
只适合整数/数据范围比较集中（相当于用空间换时间）
8.排序稳定性
稳定性关注的是相同值排序以后，相同值的相对顺序是否有发生变化
例如上图的2个5，红前蓝后经过多次排序以后，依然还是红前蓝后，说明是稳定的
为什么需要去判断稳定性呢？
在实践时，一般都是对结构体进行排序；假设有张三、李四两个人的成绩结构体（两人的成绩相同），并且要求张三信息必须要在李四前面，如果不具备稳定性那么张三这条信息就放在李四后了，因此需要去考虑稳定性
插入排序：稳定（相等时不挪动，因此相对顺序没有变）
希尔排序：不稳定（分组不同导致的）
选择排序：不稳定（6 6 1 1 9 7 ，min = 1 begin=0 ,a[0] 和 a[2] 交换位置以后，放在数组首部的元素6失去了稳定性）
冒泡排序：稳定（相等时不交换位置）
快速排序：不稳定（只要left、right下标2值交换位置，就有可能打破原有的相对顺序）
归并排序：稳定（相同值在不同区间，通过a[begin1]<=a[begin2]把a[begin1]放进temp数组即可保证稳定；相同值在相同区间，是通过前面归并的操作到了当前这一步的，肯定稳定）堆排序：不稳定（相同值在不同子树，向上调整建堆时会破坏相对顺序）