首页 > 代码库 > 插入排序（InsertionSort）
插入排序（InsertionSort）
生活中的“插入排序”
扑克牌我们大部分人都玩过，当然也都知道该怎么把刚抓上来的牌放哪里，最后得到一手排好的牌。但其中所蕴含的算法原理
不知道你有没有想过。计算机科学家把人的这一直观想法翻译为计算机程序于是便有了我们所说的插入排序：
图示
代码（C++）
/*************************************
函数：插入排序
说明：对区间[low, high)的数据排序
时间复杂度：O(n + inverse)
*************************************/
void insertionSort(int* low , int* high)
{
for(int* cur = low; ++cur < high; ) ///实际是从第二个元素开始插入，因为第一个已经有序了
{
int tmp = *cur; ///临时保存要插入的值
int* destPos = cur; ///记录当前要插入的元素的正确安放位置，这里初始化为本来的位置
while(--destPos >= low && *destPos > tmp) ///测试上一个是否是目标位置
*(destPos + 1) = *destPos;
*(destPos + 1) = tmp; ///最后一次测试失败使得destIndex比实际小1
}
}这里使用指针作为输入参数是比输入元素个数是有优势的：常数更小，移植性更强。inverse是什么
从上面的函数说明中得知算法的时间复杂度 O（n + inverse），O（n）很容易理解就是外层循环遍历n个元素。
内层循环的次数便是inverse，而inverse便是数学上逆序数的概念：
假设A[1...n]是一个有n个不同数的数组。若i < j 且 A[i] > A[j]，则对偶（i，j）称为A的一个逆序，逆序数就是逆序之和。
逆序数用来描述一组数据无序的程度。而插入排序过程中每移动一次元素便“修复”一个逆序，所以内层循环次数 = inverse。
1.很容易得知inverse的范围：0 <= inverse <= n(n - 1) / 2
2.inverse的期望为 n(n - 1) / 4，即为最差情况的一半。
2.inverse的期望为 n(n - 1) / 4，即为最差情况的一半。
关于期望的证明很简洁易懂，是我从数据结构和算法分析那本书上看来的：
假设元素是互异的。
对排列分组：每个排列与其反转后得到的逆排列分为一组，这样一来每对元素（i，j）
会对任一组中的其中一个排列贡献一个逆序，这样每组都有C(n,2) = n(n - 1) / 2个逆序，平均每个排列有n(n - 1) /4
假设元素是互异的。
对排列分组：每个排列与其反转后得到的逆排列分为一组，这样一来每对元素（i，j）
会对任一组中的其中一个排列贡献一个逆序，这样每组都有C(n,2) = n(n - 1) / 2个逆序，平均每个排列有n(n - 1) /4
现在来测试一个随机排列inverse的大小：
void insertionSort(int* low , int* high)
{
int inverse = 0; ///逆序数
for(int* cur = low; ++cur < high; )
{
int tmp = *cur;
int* destPos = cur;
while(--destPos >= low && *destPos > tmp)
{
*(destPos + 1) = *destPos;
inverse++; ///修复一个逆序
}
*(destPos + 1) = tmp;
}
}下面是测试数据（假设元素互异，且随机排列）：
优化
当数据量很大时利用二分查找插入排序和希尔排序都是很不错的，不过数据量大的时候插入排序常数小这一优势就没什么用了，基本上丧失了战斗力。
所以这里做的优化都是以小数据输入作为基本条件的。
对上面的代码分析发现就算第i个元素本来就在正确位置还是会被自己给替代一次，下面的代码解决了这一浪费：
/*************************************
函数：优化版插入排序
说明：对区间[low, high)的数据排序
时间复杂度：O(n + inverse)
*************************************/
void improvedInsertionSort(int* low , int* high)
{
for(int* cur = low; ++cur < high; ) ///实际是从第二个元素开始插入，因为第一个已经有序了
{
int tmp = *cur; ///临时保存要插入的值
int* destPos = cur; ///记录当前要插入的元素的正确安放位置，这里初始化为本来的位置
///把第一次测试单独提出来
if(*(--destPos) > tmp)
{
do
{
*(destPos + 1) = *destPos;
}while(--destPos >= low && *destPos > tmp); ///测试上一个是否是目标位置
*(destPos + 1) = tmp; ///最后一次测试失败使得destIndex比实际小1
}
}
}通过把第一次测试单独提出来，使得在正确位置的元素不用执行多余的最后一条赋值语句。
但这一优化是十分十分有限的，因为第i个元素就在第i个位置的条件就是这一元素是前i个元素中最大的，这一概率为 1 / i ，所以n个元素中大约只有ln(n)个元素满足条件
它唯一的优点就是在任何情况都不会使运算更费时。
后记
实在是想不到什么好的优化方案，所以如果你知道其他更好的优化方法或上面内容有什么问题请在下面评论。
插入排序（InsertionSort）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。