目录
1.什么是排序？
排序是计算机的一种操作方法，其目的是将一组“无序”的记录序列调整为“有序”的记录序列，主要分为内部排序和外部排序。
若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
2.直接插入排序?
2.1多趟实现
2.11实现原理
如下图，插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。它在实现上，通常采用in-place排序（即只需用到的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
?2.12代码实现
void InsertSort(int* a, int n)
{
int i ;
for (i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
//end后一位
while (end >= 0)
{
if (tmp < a[end])
{
a[end+1] = a[end ];
end--;
//因为插入这个数不仅和后边的数比较，还要大于前面的数，
//所以end范围要缩小
}
else
//这一步有两种第一种是比较好了，
//第二种是要插入的数小于所有数。直接结束
{
break;
}
}
a[end + 1] = tmp;
}
}
2.2时间复杂度计算?
3.希尔排序
3.1实现原理：
希尔排序是将待排序的数组元素 按下标的一定增量分组（gap） ,分成多个子序列,然后对各个子序列进行直接插入排序算法排序; 然后依次缩减增量再进行排序,直到增量为1时,进行最后一次直接插入排序,排序结束。”
?实际意思是例如上面的11个数，我们可以按增量gap为3分组（gap<11）,分成了1， 4， 7， 11；2， 5， 8， 12；还剩下3， 6， 9三个，虽然不满4个，但是我们也把它分为一组。然后把这三组数的每一组数都从大到小排列，然后三组继续按照它原来下标位置，将数排列，最后整体在排列。
3.2预排序
先把无序数组大致排成一个升序数组
?这就是预排序，数组已经大差不差有一个升序的样子，但是个别数顺序要改一下。
3.21单趟实现
?3.22一组gap实现
?3.23整体实现（多组gap实现）
void ShellSort(int* a, int n)
{
int i = 0;
int gap=3;
for (int j = 0; j < gap; j++)
{
for (i = 0; i < n - gap; i += gap)
//i<倒数第二个数据即可，最后一个和倒数第二个直接比较
{
int end = i;
int tmp = a[end + gap];
//end的后一位
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
｝
3.3预排序的实现
接下来就是微调和怎样确定gap。
void ShellSort(int* a, int n)
{
int i = 0;
while (gap > 1)
{
gap = gap / 3 + 1;//缩小gap范围，+1，保证最后gap范围
//不为0，还可以计算
for (i = 0; i < n - gap; ++i) //先算后加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;
}
}
}这个++i，相当于在最后源码最后面是i++,?
?为啥上面的最外层for循环省略了？
++i就可以是i从第一gap组比较完移到第二等组，所以就少一循环。
?为啥gap要有一组循环？
注意预排不是只有一组，要进行好多组。