什么叫做插入排序！

C:\java>java Sort

0=2

1=3

2=4

3=5

4=12

5=21

6=32

7=34

8=44

9=56

C:\java>java arrayQsort

0=2

1=3

2=4

3=5

4=12

5=21

6=32

7=34

8=44

9=56

插入法：

插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张

#include <iostream.h>

void InsertSort(int* pData,int Count)

{

int iTemp;

int iPos;

for(int i=1;i<Count;i++)

{

iTemp = pData[i];

iPos = i-1;

while((iPos>=0) && (iTemp<pData[iPos]))

{

pData[iPos+1] = pData[iPos];

iPos--;

}

pData[iPos+1] = iTemp;

}

}

void main()

{

int data[] = {10,9,8,7,6,5,4};

InsertSort(data,7);

for (int i=0;i<7;i++)

cout<<data[i]<<" ";

cout<<"\n";

}

倒序(最糟情况)

第一轮：10,9,8,7->9,10,8,7(交换1次)(循环1次)

第二轮：9,10,8,7->8,9,10,7(交换1次)(循环2次)

第一轮：8,9,10,7->7,8,9,10(交换1次)(循环3次)

循环次数：6次

交换次数：3次

其他：

第一轮：8,10,7,9->8,10,7,9(交换0次)(循环1次)

第二轮：8,10,7,9->7,8,10,9(交换1次)(循环2次)

第一轮：7,8,10,9->7,8,9,10(交换1次)(循环1次)

循环次数：4次

交换次数：2次

上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，

因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)<=

1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)（这里说明一下，其实如果不是为了展示这些简单

参与评论

相关内容

最近更新

·c 编q-m算法

·数据结构课程设计

·索爱W958性价比

·O2 XDA Atom 手机的性能

·哪里可以下载手机上Txt的歌词

·N73最新软件版本？那个好？

·N73存储卡上装的内容多会影响机器..

·三星E908输入哪几个字符能查通话..

·A780刷机文件

·QQ留言出现问题，窗口自动关闭

最近热点

·数据库课程设计报告和设计实例

·QQ群个性公告大全

·好记星 E900+驱动下载。。

·请问在哪里可以下载兼容DVD的解码..

·如何在qq空间里下载免费的播放器..

·电脑如何进入cmos,如何设置cmos？

·qq空间免费设置，请问我怎样在QQ..

·Springdale-G 的主板驱动

·哪里有万能转换器下载

·8开纸的大小

网站推荐

·Dev-c++与Allegor平台的搭建方法

·关闭QQ游戏后跳出的广告

·数据库oracle在C++程序中使用方法

·“please input 7 or more chara..

·解决提示rundll32.exe不能结束的

·Cool n Quiet2.0 介绍

·SDHC（High Capacity SD Memory ..

·什么是RAMDAC

·中国移动提示我“您目前应缴话费..

·you need to enablble active sc..