个人技术笔记

插入排序

发布时间：2015-11-06  栏目：软件算法  评论：0 Comments

插入排序很好理解，一个形象的比喻就是在打牌时，新摸了一张牌，如何把这张牌插入到已有的牌里。此方法简单易用，但是时间复杂度偏高，为O(n*n)。

算法原理：把数组从前往后搜索，之前的部分都是排过序的，每次把后面的一个新的值插入到前面的队列中，插入的方法采用比较法，如果小于前面的就交换。

 

以下代码编译通过：

#include <stdio.h>

void insertsort(int* datas, int length)

{

int i,j;

int k,key;

if((datas==NULL)||(length==0))

printf(“Check your input please!”);

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

{

for(j=i-1,k=i;j>=0;j–,k–)

{

if(datas[j]>datas[k])

{

key=datas[k];

datas[k]=datas[j];

datas[j]=key;

}

else

break;

}

}

}

 

int main(int agrv, char* argc[])

{

int data[9]={12,45,67,9,100,23,67,10,7};

insertsort(data,9);

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

printf(“%d “, data[i]);

printf(“\n”);

return 0;

}

 

运行g++编译：

g++ test.cpp -o test

./test

 

留下评论

You must be logged in to post a comment.