首页 > 代码库 > 算法学习笔记（二）：插入排序
算法学习笔记（二）：插入排序
算法思想：A[i]插入到已排序好的A[0,1,2,...i-1]的过程为将A[i]与已排序好的元素比较，找到其应插入的位置，将其后的元素后移一位。
循环这一过程即可完成排序
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
算法复杂度：O（n2）
伪代码
INSERTION-SORT(A)
1forj=2tolength[A]
2dokey=A[j]
3 //InsertA[j] into the sorted sequenceA[1..j-1].
4 i=j-1
5 whilei>0 andA[i] >key
6 doA[i+1] =A[i]
7 i=i-1
8 A[i+1] =key
代码实现：
void insert_sort(int array[],int n){ int temp; for (int j = 1; j < n;++j) { temp = array[j]; int i = j-1; while (i>=0&&array[i]>temp) { array[i+1] = array[i]; --i; } array[i+1] = temp; }}
算法学习笔记（二）：插入排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。