博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
排序算法之插入排序
阅读量:4192 次
发布时间:2019-05-26

本文共 1360 字,大约阅读时间需要 4 分钟。

排序算法之插入排序

1插入排序的思想

假设在一个有序序列中e[0]~e[i-1]i个元素已经排好序,则当要将第i+1个元素e'插入该序列时,只需将第i+1个元素与从e[0]开始到e[i-1]元素进行比较,当发现第j个元素e[j]在序列中应在e'前,且e[j+1]应在e'后时,将该有序列中从e[j+1]e[i-1]的元素向后移动一个单元。最后将e'插入原来e[j+1]所在的位置。重复前面的动作直到将所有的元素插入该有序列中为止。

2插入排序的实现思想

在一个无序序列中,一个只有一个元素e[0]的序列是有序的。此时按照上面的算法思想将e[1]插入该有序序列中。如此往复,直到将原无序序列中所有的元素都插入该有序序列中为止。< /p>

3插入排序的具体实现

/*

C代码的插入排序

有序序列为整数的由小到大序列

*/

void insertSort(int e[],int n){

int i,j;

int temp;

for(i=1;i

temp=e[i];

for(j=i-1;j>=0;j--){

if(e[j]

break;

}

e[j+1]=e[j];

}

e[j+1]=temp;

}

}

#!/usr/bin/perl

#perl代码的插入排序

#有序序列为整数的由小到大序列

sub insertSort{

my(@e)=@_;

my($i,$j)=(0,0);

my($temp)=0;

for($i=1;$i<@e;$i++){

$temp=$e[$i];

for($j=$i-1;$j>=0;$j--){

if($e[$j]<$temp){

last

}

@e[$j+1]=@e[$j];

}

@e[$j+1]=$temp;

}

return(@e);

}

#!/usr/local/bin/python

#Python代码的插入排序

#有序序列为整数的由小到大序列

def insertSort(e):

i=j=0

n=len(e)

for i in range(1,n):

temp=e[i]

for j in range(0,i+1):

j=(i-1)-j

if(e[j]

break

e[j+1]=e[j]

e[j+1]=temp

return(e)

4算法分析

插入排序最坏的情况是初始序列与要求的序列逆序。此时,每次插入都需要将插入项后的元素向后移动。

插入排序的复杂度为n(n-1)/2=O(n^2) 且 是稳定排序
插入排序的性能和原始序列的情况密切相关。当原始序列非常接近排序后的序列时,插入排序的效率是很高的。当原始序列与排序后的序列互为逆序时,插入排序的效率最差。

文外音:

很早以前就想写这样的文章了,所以今天有些时间就写了。感觉我的Blog很久都没更新了,突然发现自己貌似有些变懒惰了。我觉得很多人把算法理解的过于狭隘了,其实算法本身并没有意义。我之后还会用有类似的文章出来,如果各位有兴趣的话可以关注一下。如果各位有什么问题,可以到上提出。

NERVE软件开发组(NDT)

NERVEDevelopment Team
北斗星君
(黄庠魁)

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1879611

你可能感兴趣的文章
关于在openstack的环境变量.bashrc自定自己简化命令
查看>>
Openstack Heat Project介绍(转)
查看>>
How to Perform an Upgrade from Icehouse to Juno(ice升级到juno)
查看>>
高扩展性网站的50条原则(转)-思维导图
查看>>
解决openstack novnc一段时间后自动挂断登录不上问题,novncproxy dead but pid file exists
查看>>
构建OpenStack的云基础架构:ManageIQ(转)
查看>>
云管理软件 ManageIQ(转)
查看>>
CentOS 7.0,启用iptables防火墙(转)
查看>>
DISCUZ浅析之COOKIE篇
查看>>
实战DDD(Domain-Driven Design领域驱动设计:Evans DDD)
查看>>
SSH中各个框架的作用以及Spring AOP,IOC,DI详解
查看>>
openstack juno 配置vmware(vcenter、vsphere)
查看>>
远程debug调试(eclipse)之openstack windows
查看>>
PAAS平台对比:OpenShift VS CloudFoundry【51CTO调研报告】
查看>>
JAX-RS(java restful实现讲解)(转)
查看>>
Spring MVC与JAX-RS比较与分析
查看>>
openstack官方docker介绍
查看>>
头痛与早餐
查看>>
[转]在ASP.NET 2.0中操作数据::创建一个数据访问层
查看>>
Linux命令之chmod详解
查看>>