基本的五类排序算法（插入，选择，交换，归并，基数排序）。排序：将数据元素的一个任意序列，重新排列成一个按关键字有序的序列。
排序的稳定性：待排序列中有大于等于2个相同的项，且排序前后，相同项的相对位置是否发生了变化（如果变化了就是不稳定的排序，不变化就是稳定的）
内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；（待排序列全部放入内存）
插入累排序：（直接插入，折半插入，希尔排序）
直接插入排序：
先将序列中第 1 个记录看成是一个有序子序列， 然后从第 2 个记录开始，逐个进行插入，直至整个序列有序。
通常是先把第一个记录看成是一个有序的序列，然后从第二个记录开始依次进行比较
r2处的38比第一个记录 r1处的49小，那么38插入到49的前面，把插入位置之后的记录顺次的后移一位，同时把带插入记录临时保存在 r0处（复制监视哨）。
然后把38插入到 r1处
下面是整个过程，一共7趟排序过程
特点：在最后一趟排序前，此序列没有一个记录到其最终位置。（所有的插入类排序的特点）
1 //递增排序 2 void insertSort(int list[]) 3 { 4 int j = 0; 5 int i = 0; 6 int temp = 0; 7 //对待排序列直接插入排序 8 //一般把第一个记录先看成是有序子序列，然后从第二个记录开始，逐个的和前面去比较，插入 9 for (i = 1; i <= 8; i++) { 10 //和前面的有序子序列的记录，逐个的比较，直接插入 11 if (list[i] < list[i - 1]) { 12 //复制为监视哨 13 temp = list[i]; 14 //移位 15 list[i] = list[i - 1]; 16 //继续顺次的和前面的记录进行比较，如果还有不小于它的，那么继续后移，直接插入排序 17 for (j = i - 1; temp <= list[j]; j--) { 18 //记录后移 19 list[j + 1] = list[j]; 20 //插入 21 list[j] = temp; 22 } 23 } 24 } 25 } 26 27 int main(void) 28 { 29 int source[8] = {49, 38, 65, 97, 76, 13, 27, 49}; 30 31 insertSort(source); 32 33 for (int i = 0; i < 8; i++) { 34 printf(" %d ", source[i]); 35 } 36 37 return 0; 38 }
13 27 38 49 49 65 76 97 Program ended with exit code: 0
算法评价
最好的情况：待排序记录按关键字从小到大排列（正序）
比较次数:
，移动次数：0
最坏的情况：待排序记录按关键字从大到小排列（逆序）
比较次数：
，移动次数： 
一般情况：待排序记录是随机的，取平均值。 比较次数和移动次数均约为： n^2/4
时间复杂度：T(n)=O(n²) （最坏情况下），最好的情况是O（n），平均时间复杂度是O(n²)
空间复杂度：S(n)=O(1) ，且直接插入排序是稳定排序
折半插入排序
用折半查找方法确定插入位置的排序。思想类似直接插入排序，只不过，要设置 mid=不大于(low+high)/2的最大整数，当插入到 mid 左边（做半区），则改变 high（mid-1），如果插入到 mid 右边，则改变 low（mid+1）。
初试序列，同样是把第一个记录看成是有序的子序列，然后从第二个记录开始，依次进行比较
假设只有最后的20这个记录了
mid=（0+6）/2=3，指向39处，20比mid 的值小，插入到 mid 左边，改变 high=mid-1
重新计算 mid=1，指向13处，继续和20比较，20比 mid的值大，插入到 mid 右边，改变 low=mid+1
计算 mid=2，指向30，20比 mid 的值30小，插入到 mid 左边，改变 high=mid-1
直到low>high时，由折半查找得到的插入位置为low或high+1。
//递增排序 void insertHalfSort(int list[]) { int j = 0; int i = 0; int low = 0; int high = 0; int mid = 0; int temp = 0;//临时监视哨 //一般把第一个记录先看成是有序子序列，然后从第二个记录开始，前面去比较，折半插入 for (i = 1; i <= 8; i++) { //复制为监视哨 temp = list[i]; low = 0; high = i - 1; //当 low>high,则找到了插入位置，为 low或者 high+1 while (low <= high) { //循环计算 mid 的值 mid = (int)((low + high) / 2); //待插入记录和 mid进行比较 if (temp < list[mid]) { //改变 high high = mid - 1; }else{ //改变 low low = mid + 1; } } //循环结束，说明找到了插入位置，进行移位 for (j = i - 1; j >= low; j--) { list[j + 1] = list[j]; } //插入 list[low] = temp; } }
折半插入，适用于记录较多的场景，但是记录的移动次数和直接插入排序一样，故时间复杂度一样。
最好是 o（n），最差是 O(n²)，平均是 O(n²)。空间复杂度是 o（1）。
特点：折半插入排序的比较次数和初始的序列无关，因为折半的次数一定，折一次比较一次。和直接插入比较，仅减少了比较次数，移动次数不变。折半插入排序是稳定排序
希尔排序（缩小增量排序）
基本思想：对待排序列先作“宏观”调整，再作“微观”调整。先取一个正整数 d1 < n，把所有相隔 d1 的记录放在一组内，组内进行直接插入排序；然后取 d2 < d1，重复上述分组和排序操作，直至 di = 1，即所有记录放进一个组中排序为止。其中 di 称为增量。且增量 d逐渐变小。
增量d 的取法：最后一个值一定为1，且其余的值没有除1之外的公因子。
如图，增量为5，把相隔5的记录放到一组内，组内进行直接插入排序
分别把增量为5的记录找出，放在一组内，每组内直接插入排序
分别对子序列进行插入排序
缩小增量d=3
分别把增量 为3的记录找出
找完之后，缩小增量d=1，进行插入排序
直接插入排序适用于基本有序的情况，而希尔排序会使整个序列更加的有序。
特点：希尔排序是不稳定的排序方法
增量序列取法；
如何选择增量序列以产生最好的排序效果，至今仍没有从数学上得到解决。
1)、没有除 1 以外的公因子；
2)、最后一个增量值必须为 1。
希尔排序可提高排序速度
1)、记录跳跃式前移，在进行最后一趟排序时，已基本有序。
2)、分组后 n 值减小，n^2 更小，而 T(n)=O(n^2)，所以 T(n) 从总体上看是减小了。时间复杂度为 O（n log2（n）），控件复杂度为 o（1）
