目录
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
基本思想
以升序为例，每一趟的冒泡排序都是把一个最大的数放到最后面，如果 a[i-1]>a[i],我们将i-1,i的值进行交换，依次循环反复。
void BubbleSort(int* a, int n){
for(int j=0; j<n; j++){
int flag = 0;
for(int i=1; i<n-j; ++i){
if(a[i] < a[i-1] ){
Swap(&a[i], &a[i-1]);
flag = 1;
}
}
if(flag == 0){
break;
}
}
}
时间复杂度：
最坏的情况：O(N^2)
最好的情况：O(N)
冒泡排序和插入排序相比，顺序有序一样好，接近有序时插入排序更好
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
基本思想：
选一个关键key，一般都是选择头。
单趟：key放在他正确的位置上，key的左边值比key小，key右边值比key大（这是key一趟下来排完后最终要放的位置）
单趟拍完，再想办法让左边区间有序，key的右边区间有序
最后相遇的位置和关键字key进行交换
下面实现快速排序中的单趟排序
void QuickSort(int* a, int n)
{
int left = 0, right = n - 1;
int keyi = left;
while(left < right)
{
while (a[right] >= a[keyi])
{
--right;
}
while (a[left] <= a[keyi])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
}上述代码在下面极端情况下出现越界的问题->加一个判断即可
void QuickSort(int* a, int n)
{
int left = 0, right = n - 1;
int keyi = left;
while(left < right)
{
while (left<right && a[right] >= a[keyi])
{
--right;
}
while (left<right && a[left] <= a[keyi])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
}注意：若不加等号会在下列情况出现死循环
下面实现多趟排序
void QuickSort(int* a,int begin, int end)
{
if (begin >= end)
return;
int left = 0, right = end - 1;
int keyi = left;
while(left < right)
{
while (left<right && a[right] >= a[keyi])
{
--right;
}
while (left<right && a[left] <= a[keyi])
{
++left;
}
Swap(&a[left], &a[right]);
}
int meeti = left;
Swap(&a[keyi], &a[left]);
//[begin,meeti-1]meeti[meeti+1,end];
QuickSort(a, begin, meeti - 1);
QuickSort(a, meeti+1, end);
}将单趟排序单独写出来
int PartSort(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
--right;
while (left < right && a[left] <= a[keyi])
++left;
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
return left;
}
void QuickSort2(int* a, int begin, int end)
{
if (begin >= end)
return;
int keyi = PasrSort(a, begin, end);
//[begin,meeti-1]meeti[meeti+1,end];
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}对于单趟排序的思考：为什么相遇位置的值一定比key小？为什么key选择最左边的值，就要先让右边的数先走先去找小？
为了确保最后相遇时的a[left]<a[key]，只要让右边的数先走，最后停下来时无论是“左边遇到右边”还是“右边遇到左边”，都满足a[left]<a[key]。
一个单趟进行的排序操作的时间复杂度是多少？思考下一次完整的快排需要进行多少趟这样的单趟排序？
一个单趟的时间复杂度是O（N），一个完整的快排需要O（logN）趟这样的单趟排序
基本思想
挖坑法可以选择在0索引处挖坑（即把数拿走保存），然后从右边找一个小的填坑，再从左边找一个大的埋住右边的坑，以此反复循环，直到left与right相遇，最后把key放入相遇点（最后一个坑位）即可
虽然也实现了左边比key小，右边比key大，但是数字的顺序和通过单趟排序实现的不同
int PartSort2(int* a, int left, int right)
{
int key = a[left];
while (left < right)
{
//找小
while (left < right && a[right] >= key)
{
--right;
}
//放到左边的坑位中，右边就形成新的坑
a[left] = a[right];
//找大
while (left < right && a[left] <= key)
{
++left;
}
//放到右边的坑位中，左边就形成新的坑
a[right] = a[left];
}
a[left] = key;
return left;
}对于时间复杂度的分析
分析：对快排影响最大的是选的key，key越接近中位数越接近二分，效率越高
三数取中
小区间优化
int GetMidIndex(int* a, int left, int right)
{
int mid = (left + right) >> 1;
//left mid right
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else//a[left]>a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}int PartSort1(int* a, int left, int right)
{
int midIndex = GetMidIndex(a, left, right);
Swap(&a[left], &a[midIndex]);
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
--right;
while (left < right && a[left] <= a[keyi])
++left;
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
return left;
}进行“三数取中”的意义是什么？
如果我们不进行“三数取中”，快排如果遇见最坏的情况——有序，时间复杂度将会变成O（N^2），如果加了“三数取中”，这一最坏情况将会不复存在（后边俩种单趟排序同理）。
基本思想
1.cur往前走，找到比key小的数据
2.找到比key小的数据以后，停下来，++prev
3.交换prev和cur指向位置的值
直到cur到达最右边的位置结束！
cur还没遇到比key大的数据之前，prev紧跟着cur，cur遇到比key大的值以后，prev和cur之间间隔着一段比key大的数据。
++prev
交换 
以此类推得
实现单趟排序
int PartSort3(int* a, int left, int right)
{
//三数取中
int midIndex = GetMidIndex(a, left, right);
Swap(&a[left], &a[midIndex]);
int keyi = left;
int prev = left, cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && a[++prev] != a[cur])//cur遇到比key小的值后：++prev,且防止自己和自己交换
{
Swap(&a[cur], &a[prev]);
}
++cur;
}
Swap(&a[keyi], &a[prev]);
return prev;
}实现多趟排序（添加小区间优化）
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
//1.如果这个子区间是数据较多，继续选key单趟，分割子区间分治递归
//2.如果这个子区间是数据较小，再去分治递归不太划算
if (end - begin > 20)
{
int keyi = PartSort3(a, begin, end);
//[begin,keyi-1]keyi[keyi+1,end]
QuickSort(a, begin, keyi - 1);;
QuickSort(a, keyi + 1, end);
}
else
{
InsertSort(a+begin+1,end-begin+1);
}
} 
递归，现代编译器优化很好，性能已经不是大问题
最大的问题：递归深度太深，程序本身没问题，但是栈空间不够，导致栈溢出
只能改成非递归，改成非递归两种方式
1.直接改成循环->斐波那契数列的求解
2.树遍历非递归和快排非递归等等，只能有Stack存储数据魔力递归过程
void QuickSortNonR(int* a, int begin, int end)
{
Stack st;
StackInit(&st);
StackPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{
int left, right;
right = StackTop(&st);
StackPop(&st);
left = StackTop(&st);
StackPop(&st);
int keyi = PartSort1(a, left, right);//单趟排序
if (left < keyi - 1)
{
StackPush(&st, left);
StackPush(&st, keyi - 1);
}
if (keyi + 1 < right)
{
StackPush(&st, keyi + 1);
StackPush(&st, right);
}
}
StackDestory(&st);
}
归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法（ Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
void _MergeSort(int* a, int left, int right,int* tmp)
{
if (left >= right)//当区间只存在一个值的时候或者区间不存在时返回
return;
int mid = (left + right) >> 1;
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
//两端有序子区间归并tmp,并拷贝回去
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int i = left;
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++];
//归并完成以后，拷贝回到原数组。
for (int j = left; j <= right; ++j)
a[j] = tmp[j];
}
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);
} 
时间复杂度
O（NlogN)，可以看出他的递归过程中每次都将一组平均分，分完后高度大概是logN，空间复杂度O（N）
基本思想
迭代实现可以用循环来实现，这里我们根据递归思想其实很容易知道，我们控制迭代从最小的子问题出发，保存最小子问题的值，然后提供给后面用，这其实就是一个动态规划的思想，我们可以从利用子问题的解，解决 “大BOSS” 。
两两一归
最后将tmp拷贝回到原数组
void _Merge(int* a,int* tmp, int begin1, int end1,int begin2,int end2)
{
int j = begin1;
int i = begin1;
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++];
//归并完成以后，拷贝回到原数组
for (int j = begin1; j <= end2; ++j)
a[j] = tmp[j];
}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)
{
for (int i = 0; i < n; i += 2 * gap)
{
//[i,i+gap-1][i+gap,i+2*gap-1]
_Merge(a, tmp, i, i + gap - 1, i + gap, i + 2 * gap - 1);
}
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)
{
for (int i = 0; i < n; i += 2 * gap)
{
//[i,i+gap-1][i+gap,i+2*gap-1]
//如果第二个小区间不存在就不需要归并，结束本次循环
int begin1 = i, end1 = i + gap - 1, begin2 = i + gap, end2 = i + 2 * gap - 1;
if (i + gap >= n)
break;
//如果第二个小区间存在，但是第二个小区间不够gap个，结束位置越界了，需要修正一下
if (end2 >= n)
end2 = n - 1;
_Merge(a,tmp,begin1,end1,begin2,end2);
}
gap *= 2;
}
free(tmp);
}1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。2. 时间复杂度： O(N*logN)3. 空间复杂度： O(N)4. 稳定性：稳定
基本思想
1.统计原数组中每个值出现的次数
2.排序：遍历Count数组，对应位置的值出现多少次就往原数组写几个这个值
当然，在对于数据比较大的时候我们可以通过相对映射，让（该值-min）后的数组加一，最后还原回去即可。
void CountSort(int* a, int n)
{
int max = a[0], min = a[0];
for (int i = 0; i < n; i++)
{
if (a[i] > max)
max = a[i];
if (a[i] < min)
min = a[i];
}
int range = max - min + 1;
int* count = malloc(sizeof(int) * range);
memset(count, 0, sizeof(int) * range);
//计数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
//排序
int i = 0;
for (int j = 0; j < range; j++)
{
while (count[j]--)
{
a[i++] = j + min;
}
}
free(count);
}
时间复杂度
计数排序的时间复杂度是O（N+range），只适合一组数据。数据的范围比较集中。如果范围集中，效率很高，并且只适合整数，如果是浮点数、字符串等等就不行了。空间复杂度是O(max-min),即为O(range)，就是我们开的数组是这个区间的范围差。
冒泡排序：俩俩对比，前一个大于后一个才发生交换（升序），不会出现相等值互换顺序的情况，能保证不改变相同值的相对顺序，稳定。
简单选择排序：在进行俩数交换位置的过程当中，可能数组当中有一个数跟发生交换的俩数数值是一样的，这样就改变的相同数之间的相对顺序，不稳定。
直接插入排序：从前到后一个个元素拿出来跟前面的对比，若插入的数值比被对比的数值小，被对比的数值往后挪动；若插入的数值比被对比的数值大，直接插入到被对比数值的后面，并没有改变俩个相同值得相对顺序，稳定。
希尔排序：在预排序时，相同的数据可能在不同的组里面，没办法控制，所以不稳定。
堆排序：比如俩个一样大的数值，一个在“树顶”，一个在“树中”，树顶元素跟最后一个元素发生交换立马影响相同数值的相对顺序，不稳定。
归并排序：能保证相同值得相对顺序不变，稳定。
快速排序：比如数组中存在跟key数值一样的值，而key是肯定会移动的，这样相对顺序就改变了，所以不稳定。
计数排序：计数是在统计每个数出现的次数，但是相同的数哪个在前哪个在后，并没有区分，所以不稳定。