- A+
0x01基本概念
根据排序时数据所占用的存储器的不同，可以将排序分为两大类。一类是整个排序过程完全在内存中进行，称为内部排序；另一类是由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成，称为外部排序。
0x02插入排序
+ 直接插入排序
+ 折半插入排序
+ 希尔排序
+直接插入排序（最简单排序方法）
定义：直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表。
性能：
平均情况O(n2)，最好情况O(n)，最坏情况O(n2)，辅助空间O(1)，稳定。
优点 : 稳定，相对于冒泡排序与选择排序更快；
缺点 : 比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量大的时候；
实现思想：
我们预留了一个哨兵，这里我们将用到它来保存一个临时值。插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，即插入排序是稳定的。
每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
经典排序算法----直接插入排序算法及其改进（稳定）
#伪代码
void InsertSort(SqList *L)
{
int i, j, count1, count2; //定义可去
count2 = count1 = 0;
for (i = 2; i <= L->length;i++)
{
if (L->r[i]<L->r[i-1]) //若是前面第一个都不满足顺序，那么我们就要去循环
{
L->r[0] = L->r[i];
for (j = i - 1; L->r[j]>L->r[0]; j--) //将大的数据全部向后移动，从后向前防止数据覆盖
{
count1++;
L->r[j + 1] = L->r[j]; //记录后移
}
L->r[j + 1] = L->r[0]; //插入到正确位置
count2++;
}
}
printf("loop move count:%d, swap insert count:%d\n", count1, count2); +折半插入排序
定义： 折半插入算法是对直接插入排序算法的改进，排序原理同直接插入算法。 但区别在于在插入到已排序的数据时采用来折半查找（二分查找），取已经排好序的数组的中间元素，与插入的数据进行比较，如果比插入的数据大，那么插入的数据肯定属于前半部分，否则属于后半部分，依次不断缩小范围，确定要插入的位置。
性能：
平均情况O(n2)，最好情况O(nlogn)，最坏情况O(n2)，辅助空间O(1)，稳定。优点 : 稳定，相对于直接插入排序元素减少了比较次数；
缺点 : 相对于直接插入排序元素的移动次数不变；
例子：int[] arr={5,2,6,0,9};经行折半插入排序
#伪代码
void BinaryInsertSort {
int arr[] = { 5 , 2 , 6 , 0 , 9 }; //定义可去
int low,high,m,temp,i,j;
for(i = 1;i<arr.length;i++){
//折半查找应该插入的位置
low = 0;
high = i-1;
while(low <= high){
m = (low+high)/2;
if(arr[m] > arr[i])
high = m - 1;
else
low = m + 1;
}
//统一移动元素，然后将这个元素插入到正确的位置
temp = arr[i];
for(j=i;j>high+1;j--){
arr[j] = arr[j-1];
}
arr[high+1] = temp;
}
}过程：初始状态：设5为有序，其中i为1，即：5 2 0 6 9
第一趟排序：low为0，high为0，则中间值下标为0（（low+high）/2，下文都是如此计算），即5大于2，则插入到5前面，然后i自增。即：2 5 6 0 9
第二趟排序：low为0，high为1，则中间值下标为0，即2小于6，然后low等于中间值得下标加1，继续找中间值为5小于6，则插入到5后面，然后i自增。即：2 5 6 0 9
第三趟排序：low为0，high为2，则中间值下标为1，即5大于0，然后high等于中间值得下标减1，继续找中间值为2大于0，则插入到2前面，然后i自增。即：0 2 5 6 9
第四趟排序：low为0，high为3，则中间值下标为1，即2小于9，然后low等于中间值得下标加上1，继续找中间值为5小于9，然后low等于中间值得下标加上1，继续找中间值为6小于9，则插入到6后面，然后i自增，即：0 2 5 6 9
即最终结果为：0 2 5 6 9
+希尔排序
定义：希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
基本有序：小的关键字基本在前面，大的基本在后面，不大不小的基本在中间
基本思想：简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。
而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。
希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。
然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。
理解希尔排序详细过程
图解排序算法(二)之希尔排序
#伪代码：
void ShellSort(SqList *L)
{
int i, j;
int increment = L->length;
do
{
increment = increment / 3 + 1; //虽然使用/2是一种好理解的方式，但是不是一个效率最好的增量，这里选择/3+1
//我们选择直接插入的方式进行处理
//下面的思路我们全部按照/2来想，我们只需要修改上面的增量即可
for (i = increment + 1; i <= L->length;i++)
{
if (L->r[i]<L->r[i-increment])
{
//需要将L->[i]插入有序增量子表中
L->r[0] = L->r[i];
for (j = i - increment; j>0 && L->r[j] > L->r[0]; j -= increment)
L->r[j + increment] = L->r[j];
L->r[j + increment] = L->r[0];
}
}
} while (increment>1);
}0x04选择排序
0x05归并排序
0x06基数排序
0x07各种内部排序的方法的比较讨论；）
