1、直接插入排序
思想：每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，直到全部插入完成。
当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。
当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为O(N^2)。
所以，数据越接近正序，直接插入排序的算法性能越好。 由于只需要一个临时变量进行存储，因此空间复杂度为O(1)。
直接排序过程中，不需要改变相等元素的位置，所以是稳定的算法。
#include<stdio.h>
//直接插入排序
void insertSort(int arr[], int size)
{
int i, j, tmp;
for (i = 1; i < size; i++)
{
tmp = arr[i];
j = i - 1;
while (j >= 0 && tmp < arr[j])
{
arr[j + 1] = arr[j]; //将大的数据往后移
--j;
}
arr[j+1] = tmp; //插入指定位置
}
}
int main()
{
int arr[] = { 49, 38, 65, 97, 76, 13, 13, 859, -1, -2, 27, 49, 0, 114 };
int n = sizeof(arr) / sizeof(arr[0]);
insertSort(arr, n);
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
优化：因为在一个有序序列中查找一个插入位置，以保证有序序列的序列不变，所以可以使用二分查找减少元素比较次数，提高效率。
//二分插入排序
void BinInsertSort(int arr[], int n)
{
for (int i = 1; i < n; ++i)
{
int tmp = arr[i];
int low = 0;
int high = i - 1;
//在前面已经有序的序列中进行二分查找
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[i] < arr[mid])
high = mid - 1;
if(arr[i] >= arr[mid])
low = mid + 1; //找到arr[i]所适合的位置
}
for (int j = i; j > low; j--)
{
arr[j] = arr[j - 1];
}
arr[low] = tmp;
}
}
2、希尔排序
希尔排序又称为缩小增量排序，是直接插入排序算法的一种威力加强版。
思路：步长的选择是希尔排序的重要部分。算法最开始以一定的步长进行排序，然后会继续以更小的步长进行排序，最终算法以步长为 1 进行排序。当步长为 1 时，算法变为直接插入排序，这就保证了数据一定会被全部排序。
希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法。
void ShellSort(int* elem, int first, int last)
{
int dk = last - first;
while (dk > 1)
{
dk = dk / 3 + 1; //排序的间隔----根据先前研究者的经验设置
for (int i = first; i < last - dk; ++i)
{
if (elem[i + dk] < elem[i])
{
int end = i;
int tmp = elem[end + dk];
while (end >= first && tmp < elem[end])
{
elem[end+dk] = elem[end];
end -= dk;
}
elem[end+dk] = tmp;
}
}
}
}
int main()
{
int arr[] = { 49, 38, 65, 97, 76, 13, 13, 859, -1, -2, 27, 49, 0, 114};
int n = sizeof(arr) / sizeof(arr[0]);
ShellSort(arr, 0, n);
return 0;
}
直接插入排序和希尔排序的比较：
1.直接插入排序是稳定的；而希尔排序是不稳定的。
2.直接插入排序更适合于原始记录基本有序的集合。
3.希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
4.希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
5.直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。