数据结构直接插入排序

直接插入排序时间复杂度如何算?可分为正序和倒序两种情况?需要计算过程和思路,

3个回答

这个要根据排序表本身来判定。从最好的角度来说,当这个排序表自己就是有序的时候是最简单的,比如{1,3,5,7,8,9}这个序列,我们只需要比较次数,也就是L.r[i]和L.r[i+1]的比较,一共比较了n-1次,由于序列是有序的,所以并没有数据的移动,所以空间复杂度为o(0).

最坏的情况就是逆序排序,比如{6,5,4,3,2,1}。[(n-1)(n+2)]/2次,数据的移动达到(n+4)(n-1)/2次,空间复杂度为o(n^2).由于排序是随机的,所以直接插入排序的平均空间复杂度为o(n^2)。(时间复杂度为o(1))

qq_33578343
陌上人已老 链表是不用移动,但是顺序表需要
4 年多之前 回复
isaaccwoo
isaaccwoo 复杂度跟数据结构有关的吧,如果要是用链表存的话,插入的操作直接插节点就可以了,并不需要移动数据啊
4 年多之前 回复

http://book.51cto.com/art/201108/287053.htm
光根据正序倒序没法分析,还要看你原先待排数据、排序顺序。具体分析看上面链接。


直接插入排序
  插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。
     本节介绍两种插入排序方法:直接插入排序和希尔排序。

直接插入排序基本思想

1、基本思想
     假设待排序的记录存放在数组R[1..n]中。初始时,R[1]自成1个有序区,无序区为R[2..n]。从i=2起直至i=n为止,依......
答案就在这里:数据结构--直接插入排序
----------------------Hi,地球人,我是问答机器人小S,上面的内容就是我狂拽酷炫叼炸天的答案,除了赞同,你还有别的选择吗?

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问