首页 > 代码库 > 插入排序------直接插入排序
插入排序------直接插入排序
最优复杂度：当输入数组就是排好序的时候，复杂度为O(n)，而快速排序在这种情况下会产生O(n^2)的复杂度。
最差复杂度：当输入数组为倒序时，复杂度为O(n^2) 其实插入排序的复杂度和逆序对的个数一样，当数组倒序时，逆序对的个数为n(n-1)/2，因此插入排序复杂度为O(n^2)。
插入排序比较适合用于“少量元素的数组”。
如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
代码实现如下：
插入排序的改进：二分插入排序
对于插入排序，如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目，我们称为二分插入排序，代码如下：
void InsertSort_Binary(RecType R[],int n) { int i,j,left,right,mid; RecType temp; for(i=1;i<n;i++) { temp=R[i]; left=0; right=i-1; //初始化左右边界 while(left<=right) //采用二分法查找新元素插入的位置 { mid=(left+right)/2; if(R[mid].key>temp.key) right= mid-1; else left = mid+1; } for(j=i-1;j>0;j--) R[j]=R[j+1]; //将新元素插入位置后面的元素像后移动一位 R[left]=temp; //插入新元素 } }
当n较大时，二分插入排序的比较次数比直接插入排序的最差情况好得多，但比直接插入排序的最好情况要差，所当以元素初始序列已经接近升序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列。
插入排序------直接插入排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。