1.插入排序
直接插入排序
思想：将待排序的元素插入到有序序列中，并保持有序，直到所有待排序元素插入完为止，得到一个新的有序序列。
//升序
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i - 1;int tmp = a[i];//将tmp插入[0,end]区间中，保持有序while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}
首先将单趟的排序排好，再排多趟。单趟中tmp始终是end的后一个元素，while循环中注意当tmp大于a[end]时跳出循环，此时end有两种情况，第一种tmp比所有元素都小，end–到下标为-1位置，第二种end在下标有效区间内，a[end + 1] = tmp，这个式子都满足,完美实现。时间复杂度为O(N^2)
希尔排序
void ShellSort(int* a, int n)
{int gap = n;// gap > 1 预排序// gap == 1 直接插入排序while (gap > 1){gap /= 2;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end > 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}
这里是gap为3的例子，实际中gap应动态变化
希尔排序又称缩小增量法，是对直接排序的优化。两步1.预排序，分组插排，使数组接近有序2.直接插入排序。
gap取法，当gap越大时大的元素能更快到末尾小的更快到头部，越不接近有序，所以采用动态变化的方法来确定gap，gap>1时是预排序，由n不断减小，一般可采取gap/=2或gap/3+1来计算，刚开始能使元素跳得更快，当gap==1时已接近有序，相当于直接插入排序，但更高效了。复杂度为0(N^1.3)
2.选择排序
直接选择排序
void SelectSort(int* a, int n)
{int left = 0, right = n - 1;while (left < right){int min = left, max = left;for (int i = left + 1; i <= right; i++){if (a[i] < a[min]){min = i;}if(a[i]>a[max]){max = i;}}swap(&a[left], &a[min]);//如果max和left重叠，交换修正一下if (max == left){max = min;}swap(&a[right], &a[max]);left++;right--;}}
每一次从待排元素中选出最小和最大的元素，放在起始和末尾位置，直到排完，每趟只选一个最值元素来排也行。
思想：每趟排序选完后，a[min]和a[left]交换，a[right]和a[max]交换，然后left，right缩小范围继续排序。其中max的初始化是left和right无所谓，因为在循环中max通过比较大小会被重新赋值，需注意的是max和left可能重叠，当left和min交换后，相当于max也被交换到min的位置，不在原来位置，这时就需要修正。时间复杂度在最好和最坏情况下都为O(N^2),不管怎样都需要排一遍才知道是否有序。
堆排序
//向下调整，条件：左右子树都是大堆/小堆
void AdjustDown(int* a, int n, int parent)
{//n为数组有效元素个数，只要左孩子下标在该范围内循环成立int child = parent * 2 + 1;while (child < n){//选出左右孩子中大的那一个if (child + 1 < n && a[child + 1] > a[child]){//条件判断child+1确保下标有效性child++;}if (a[child] > a[parent]){swap(&a[child], &a[parent]);//更新递归下去parent = child;child = parent * 2 + 1;}else{break;}}
}//排升序 -- 建大堆
void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}
本质也是选择排序，将数组想象成特殊的完全二叉树，排升序建大堆，每次将堆顶元素与堆尾元素交换，再通过向下调整法调整满足堆序，这时次大的元素在堆顶，重复操作即可。排降序建小堆，思路相同。
3.交换排序
冒泡排序
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){bool exchange = false;for (int i = 1; i < n-j; i++){if (a[i - 1] > a[i]){swap(&a[i - 1], &a[i]);exchange = true;}}if (exchange == false){break;}}}
元素两两比较，大的后挪小的前移，c语言中就认识它了。
时间复杂度最坏O(N*2),最好O(N),和之前学习的冒泡不同，这里加了一个exchange的状态看在第一趟排序中是否发生交换，若没有证明元素已经有序，直接退出即可，提高了效率。
虽然冒泡排序和直接插入排序的时间复杂度各情况都相同，但直插排序效率更高一些，在元素已有序的情况下二者效率相同，接近有序的情况下，有一些差距，部分有序的情况下差距较大，因为直插排是部分挪动，而冒泡是整体挪动。
3.2快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
3.2.1hoare版
void QuickSort1(int* a, int left, int right)
{//返回条件if (left >= right){return;}//随机选key//randi中加个left因为key取值范围在不同区间/*int randi = left + (rand() % (right - left));if (randi != left){swap(&a[randi], &a[left]);}*///三数选中int midi = GetMidNumi(a, left, right);if(midi != left)swap(&a[midi], &a[left]);int begin = left, end = right;int key = left;while (left < right){while (left<right && a[right]>=a[key])right--;while (left < right && a[left] <= a[key])left++;swap(&a[left], &a[right]);}swap(&a[key], &a[left]);key = left;//[bigin,key-1] key [key+1,end] 递归QuickSort1(a,begin, key - 1);QuickSort1(a, key+1, end);
}
既可以选左边做key，也可以选右边做key。左边做key，右边先走，可以保证相遇位置比key要小or相遇位置就是key的位置。反之，相遇位置比key要大或就是key的位置。相遇情况分析：以左边做key为例1.R先走找到小，L找大没找到，L遇到R。2.R找小，没找到，要么遇到一个比key小的位置(R不是第一次出发)，要么直接遇到key(R第一次出发)。
递归返回条件判断：当left<=right下标时区间不存在，结束调用递归
代码注意：在嵌套的while循环中，内层while循环成立条件要判断下标的有界性，否则将一直循环下去造成数组越界访问，同时在数组元素进行比较时要加上=号，否则将卡住，无法遍历下去。跳出循环swap完后记得更新key下标位置，因为接下来要划分区间进行递归
3.2.2挖坑法
思想：以选左为key为例，先将第一个数据保存在key中，行成一个坑位，右边先走遇到比key小的填坑，然后自身行成一个新坑，左边再走，如此循环下去，直到左右相遇，将key换到此时坑的位置，划分区间，进行递归。
void QuickSort2(int* a, int left, int right)
{//返回条件if (left >= right){return;}//三数选中int midi = GetMidNumi(a, left, right);if (midi != left)swap(&a[midi], &a[left]);int begin = left, end = right;int hole = left;int key = a[left];while (left < right){while (left < right && a[right] >= key)right--;a[hole] = a[right];hole = right;while (left < right && a[left] <= key)left++;a[hole] = a[left];hole = left;}a[hole] = key;//[bigin,hole-1] hole [hole+1,end] 递归QuickSort2(a, begin, hole - 1);QuickSort2(a, hole + 1, end);
}
要进行遍历和递归操作，需提前保存下标，创建hole变量记录坑位下标，嵌套循环不变，当左右两边走到合适位置时对坑位进行赋值，同时更新下标位置。
3.2.3前后指针法
思想：用prev和cur分别记录前后下标。1.cur找到比key小的值，++prev，cur和prev位置的值进行交换，再++cur. 2.cur找到比key大的值，++cur
说明：1.prev紧跟着cur(prev下一个就是cur) 2.prev跟cur中间隔着比key大的一段值的区间。
void QuickSort3(int* a, int left, int right)
{int begin = left;//返回条件if (left >= right){return;}//三数选中int midi = GetMidNumi(a, left, right);if (midi != left)swap(&a[midi], &a[left]);int prev = left, cur = left+1,key=left;while (cur <= right){//if (a[cur] < a[key] )if(a[cur] < a[key] && ++prev!=cur)swap(&a[prev], &a[cur]);cur++;}swap(&a[prev],&a[key]);key = prev;QuickSort3(a,begin,key-1);QuickSort3(a, key+1, right);}
循环if语句中，利用了与操作的特性，先是判断cur和key大小关系，若不满足直接++cur继续循环，若满足看第二个条件++后prev的下标是否和cur相同，相同代表两位置的数一样，没必要交换，不同则交换。
3.2.4时间复杂度分析及优化
严格来讲每一层n个数都要减去前面所有基准值个数之和，但减去后总体量级没变，可以认为时间复杂度为0(N*logN).
最坏情况下及数组元素有序，这时n每层n的大小将形成等差数列，如果还从头或尾来选key时间复杂度将来到O(N*2)。所以我们可以通过优化选key来达到优化时间复杂度的效果。
一.随机选key法
二.三数取中法
int GetMidNumi(int*a, int left, int right)
{int mid = (left + right)/2;if (a[left] > a[mid]){if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}elsereturn right;}if (a[left] < a[mid]){if (a[left] > a[right]){return left;}else if (a[mid] < a[right]){return mid;}elsereturn right;}
}
GetMidNumi中通过三个元素比较选出中间值，使用if的嵌套最多三次比较即可选出。三数取中意为在数组头，尾，中间的三个元素中取中间值的元素做key，这样可避免数组有序从边界选key造成的时间复杂度最坏情况。
3.2.5小区间优化法
若元素理想，将其看成一棵满二叉树进行快排，那么最后一层将有一半的元素，对最后一层元素进行划分区间，调用递归的次数将非常大，于是想到定一个合理的区间数，若小于这个区间数调用其他算法来排序，避免多次递归以及可能引发的栈溢出问题，大于这个区间就继续快排，如此往复，能实现效率优化。
void QuickSort4(int* a, int left, int right)
{if (left >= right){return;}if ((right - left + 1) > 10){//前后指针法快排QuickSort3(a, left, right);}else{//直接插入排序InsertSort(a,right-left+1);}
}
选择直接插入排序基于以下几点优势
1.内存效率高，仅需常数额外空间，适用于资源受限环境
2.局部有序性适应良好，当部分数据有序时，插入排序能更快完成任务
3.小规模性能优越，在小数据集上表现优于快排，减少递归和函数调用次数
3.2.6非递归法
递归可能存在深度太深造成栈溢出的问题，可以通过栈来实现快排的非递归法。
通过栈实现的原因：
1.快排的核心在于递归的划分数组，一般先处理左子数组，再处理右子数组，栈后进先出的特性保证了两子数组处理顺序匹配。
2.相比队列：队列先进先出的特性会导致先处理较早划分出的较大区间，小区间被推迟处理，违反了由小到大依次处理的顺序，增加了时间复杂度。队列是广度优先特性。
3.栈后进先出的特性以及压栈，出栈模拟了快排划分子区间，递归调用的方法，栈支持“深度优先”的处理方式，能够快速集中处理较小的子区间，减少整体递归深度和函数调用开销
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = QuickSort3(a, begin, end);if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}
先调用之前实现栈的函数。当栈不为空循环继续，因为栈后进先出的特性要先入right再入left，出就是先出left再出right，获取栈头部元素后记得删除，再调用一次快排函数获得keyi基准值的下标位置，再由此划分区间循环下去。
ps：这里的QuickSort3和3.2.3的不同，加了int的返回值，并且没有调用递归，用来活得基准值下标并返回。
3.2.7三路划分
快排数据在有大量重复元素时会导致分区不平衡，key可能在left和right遍历完数组后没有交换到中间位置，传统分区无效，可以采用三路划分思想来解决。
设置left为左边界值，right为右边界值，cur从left+1位置起代表当前值。还是假设key=a[left]
1.a[cur]<key时交换left和cur的位置，left++，cur++，都往后挪动一位
2.a[cur]==key时，cur++
3.a[cur]>key时，交换cur和right位置，right–，由于此时cur下标位置元素可能大于或小于key，故不动，作为元素中转站，继续下一轮遍历比较，直到cur>right时结束循环。
核心思想总结：
1.跟key相等的值往后推 2.比key小的甩到左边 3.比key大的甩到右边 4.根key相等的就在中间
void QuickSort5(int* a, int begin, int end)
{if (begin >= end){return;}//小区间优化if ((end - begin + 1) < 15){InsertSort(a, end - begin + 1);}else{//三数取中可以结合随机选key来优化部分场景int midi = GetMidNumi(a, begin, end);if (midi != begin)swap(&a[midi], &a[begin]);int key = a[begin];int left = begin, right = end, cur = begin + 1;while (cur <= right){if (a[cur] < key){swap(&a[left], &a[cur]);left++;cur++;}if (a[cur] > key){swap(&a[right], &a[cur]);right--;}if (a[cur] == key){cur++;}}//划分好区间[begin,left-1][left,right][right+1,end]//递归调用QuickSort5(a, begin, left - 1);QuickSort5(a, right+1, end);}}
4.归并排序
分治法包含三阶段
1.分解：将原问题拆分为若干子问题
2.解决：递归解决子问题
3.合并：将子问题的解整合为原问题的解
归并特指分治的第三阶段操作，核心将两个有序序列合并为一个新有序序列。
归并排序是采用分治算法的典型应用，将一组数据不断划分递归到单个数据，归并返回不断向上使上一层数据组有序，直到原数据组有序。
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end){return;}//子区间递归排序int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid+1, end, tmp);//归并int begin1 = begin, end1 = mid, begin2 = mid + 1, end2 = end;//由于begin1在不断变化，创建i来保存tmp下标int i = begin;//思路类似二叉树后序遍历，两个子区间有序后再整个区间有序while (begin1 < end1 && begin2 < end2){//两个区间比较赋值if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}//当两个子区间数据个数不同时，将其中剩余区间的数据一一赋值到tmp//不知道剩余哪个区间，写两个循环看谁满足while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}//将tmp中数据拷贝回原数组for (int i = 0; i < end; i++){a[i++] = tmp[i++];}}void MergeSort(int* a, int n)
{int *tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a,0,10,tmp);free(tmp);
}
只需要开辟一个内存空间大小为n的数组即可，两个有序空间依次比较，小的尾插到该数组，归并后返回原数组。
4.1非递归法
省略掉依次递归到单一数据的过程，直接每组从一个数据开始归并，随着每组归并的数据越来越多，直到整体有序。
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){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 (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}//观察区间是否越界printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);int j = i;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));}printf("\n");gap *= 2;}free(tmp);
}
该部分为控制边界条件的代码，在数据元素为奇数时会失效，所以需要修正。这里采取归并一部分，拷贝一部分返回的方法，可以避免复杂边界讨论情况，和未归并元素被拷贝回元素覆盖的问题。
5.计数排序
思想：绝对位置映射创建计数数组的长度将从0到待排序数据中的最大值，采用相对映射的方式。首先确定待排序数组的数据范围，min到max，创建长度为max-min+1的计数数组。遍历原数组，统计每个数据出现的次数，存入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 = (int*)calloc(range, sizeof(int));if (count == NULL){perror("calloc fail");return;}//将数据存入计数数组for (int i = 0; i < n; i++){count[a[i] - min]++;}int j = 0;for (int i = 0; i < range; i++){//计数数组count[i]表示表示原数组中等于i+min的元素总数while (count[i]--){//将元素拷贝回原数组a[j++] = i + min;}}free(count);
}
各排序算法复杂度和稳定性总结
稳定性定义：相等元素的相对顺序在输出中保持不变。
简单选择排序(直接)：在类似前三个元素是221的情况下不稳定。
希尔排序：相同的数据可能会被分到不同的组预排序，不稳定。
堆排序：在类似建大堆实现升序排序时，通过删除末尾元素和向下调整法保持堆序不稳定
快速排序：在划分出的不同子区间内有和头尾部相同的数据时不稳定。
