常见排序算法的实现(一)-插入排序 - 那谁的技术博客 - C++博客

随笔-174 评论-598 文章-0 trackbacks-0

常见排序算法的实现(一)-插入排序

插入排序是最简单最直观的排序算法了,它的依据是:遍历到第N个元素的时候前面的N-1个元素已经是排序好的了,那么就查找前面的N-1个元素把这第N个元素放在合适的位置,如此下去直到遍历完序列的元素为止.
算法的复杂度也是简单的,排序第一个需要1的复杂度,排序第二个需要2的复杂度,因此整个的复杂度就是
1 + 2 + 3 + ... + N = O(N ^ 2)的复杂度.

// 插入排序

void InsertSort(int array[], int length)

{

int i, j, key;

for (i = 1; i < length; i++)

{

key = array[i];

// 把i之前大于array[i]的数据向后移动

for (j = i - 1; j >= 0 && array[j] > key; j--)

{

array[j + 1] = array[j];

}

// 在合适位置安放当前元素

array[j + 1] = key;

}

}

posted on 2006-07-03 15:39 那谁阅读(493) 评论(0) 编辑收藏引用所属分类: 算法与数据结构

标题

姓名

主页


验证码	*

内容(提交失败后,可以通过“恢复上次提交”恢复刚刚提交的内容)

Remember Me?

登录使用高级评论新用户注册返回页首恢复上次提交

[使用Ctrl+Enter键可以直接提交]

.NET频道博客园社区闪存

相关文章:

网站导航:

博客园 BlogJava 博客生活 IT博客网 C++博客 PHP博客博客园社区管理