一、插入排序
1.算法思想
要求在一个已经有序的数据序列中插入一个数据，并且插入次数据后数据序列依然有序，这时就需要用到一种新的排序方法——插入排序，其基本思想就是每步讲一个待排序的记录，按其关键码值的大小插入到前面已经排序的文件中适当的位置，直至全部插入完为止。
2.具体步骤
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果已排序的元素大于新元素，将其移到下一位置
- 重复步骤3，直至找到已排序的元素小于或者等于新元素的位置
- 将新元素插入
- 重复步骤2-5
3.算法复杂度
时间复杂度：如果将n个元素升序排列，最好的情况是已经升序，这种情况下，只需要进行(n-1)此比较即可；最坏的情况是降序排列，此时需要比较n(n-1)/2次。平均时间复杂度为o(n^2)。
空间复杂度：o(1)
稳定性：在插入过程中，如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，是稳定的。
void InsertSort(int* arr,size_t size)
{
if (NULL == arr || size == 1)
return;
for (size_t i = 1; i < size; i++)
{
int key = arr[i];
int end = i - 1;
while (key < arr[end] && end >= 0)
{
arr[end + 1] = arr[end];
end--;
}
arr[end + 1] = key;
}
}
在插入数据过程中，比较次数可能会比较多，我们可以将直接查找的方改为折半查找，即可得到折半插入排序算法，相比于直接插入排序，有一定的优化。
void InsertSort_B(int* arr,size_t size)
{
if (NULL == arr || size == 1)
return;
for (size_t i = 1; i < size; i++)
{
int key = arr[i];
int left = 0;
int right = i - 1;
int end = i - 1;
while (left <= right)
{
int mid = left + ((right - left) >> 1);
if (key < arr[mid])
right = mid - 1;
else
left = mid + 1;
}
while (left <= end)
{
arr[end + 1] = arr[end];
end--;
}
arr[end + 1] = key;
}
}
二、希尔排序
1.算法思想
希尔排序又称缩小增量法，是直接插入排序的一种改进。其基本思想是：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 dt=1，即所有记录放在同一组中进行直接插入排序为止。
2.具体步骤
假设有10个记录，其关键字分别是：7,5,3,1,9,4,6,2,8；取增量依次为3,1
3.算法分析
希尔排序不需要大量的辅助空间，容易实现。相比于插入排序，效率上有所提高，其时间复杂度也有增量的选取有关。希尔排序没有快速排序快，对于规模非常大的数据排序不是最优的选择；但是希尔排序在最坏的情况下和平均情况下执行效率相差不是很大，快速排序则相差较大，因此，几乎任何排序工作在开始时都可以用希尔排序，若在实际中证明它不够快，再改成快速排序。此外，希尔排序是不稳定的。
void ShellSort(int* arr,size_t size)
{
int gap = size;
while (gap > 1)
{
gap = gap / 4 + 1;
for (size_t i = gap; i < size; i++)
{
int key = arr[i];
int end = i - gap;
while (key < arr[end] && end >= 0)
{
arr[end + gap] = arr[end];
end -= gap;
}
arr[end + gap] = key;
}
}
}
