【标 题】：常见排序算法的实现(一)-插入排序
【关键字】：
【来 源】：http://www.cppblog.com/converse/archive/2006/07/03/9309.html
【关键字】：
【来 源】：http://www.cppblog.com/converse/archive/2006/07/03/9309.html
常见排序算法的实现(一)-插入排序
插入排序是最简单最直观的排序算法了,它的依据是:遍历到第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;
????}
}
算法的复杂度也是简单的,排序第一个需要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;????}}
【相关文章】
没有相关文章
没有相关文章
【随机文章】
mangle表中 TTL TOS MARK 的操作
巧寻Word空格
单模光纤系统
WIN2003下Web服务器配置(实现WAP应用)
CMMI SE/SW V1.1 简介
无聊恋爱？恋爱无聊？
教你根据名称识别电脑病毒
XML详解----Schema
[原创].NET2.0环境下的Ajax选型和应用（提供Demo源码下载）
主窗体和子窗体之间如何相互操作对方的控件
【相关评论】
没有相关评论
【发表评论】
|