首页 > 代码库 > 数据结构--插入排序
数据结构--插入排序
插入排序算法主要有三种:直接插入排序、折半插入排序、希尔排序
1、直接插入排序:
/**
* 直接插入排序,
* 1、从i-->length-1开始做插入扫描
* 2、初始化一个要插入的元素(1步骤中的)
* 3、从0-->i开始做插入排序操作
* 如果要插入的元素小于0-->i中的某一个元素,则做位置替换,
* 否者,执行第一步(i+1)步骤
* 4、结束
* 时间复杂度:∑(i+1)/2 = (n2+3n+4)/4 =~ n2 ,(1<=i<=n);
* 空间复杂度:需要一个空间地址作交换,故O(1);
*/
def
StraightInsertionSort(
list
):
for
i
in
range
(
1
,
len
(
list
)):
for
j
in
range
(i,
0
,
-
1
):
if
list
[j] <
list
[j
-
1
]:
tmp
=
list
[j
-
1
]
list
[j
-
1
]
=
list
[j]
list
[j]
=
tmp
print
list
return
list
2、折半插入排序
/**
* 折半插入排序
* 1、从i-->length-1开始做插入扫描
* 2、初始化一个要插入的元素(1步骤中的)
* 3、从0-->i开始做折半查找插入操作
* a、通过折半的方式定位要插入的元素的位置X
* b、将位置X及以后的元素往后移动一位
* c、将位置X赋值为要插入的元素
* 4、结束
* 时间复杂度:∑(i+1)/2 = (n2+3n+4)/4 =~ n2 ,(1<=i<=n);
* 空间复杂度:需要一个空间地址作交换,故O(1);
*/def
BinaryInsertionSort(
list
):
for
i
in
range
(
1
,
len
(
list
)):
low
=
0
high
=
i
tmp
=
list
[i]
while
low <
=
high:
mid
=
(low
+
high)
/
2
if
list
[mid] > tmp:
high
=
mid
-
1
else
:
low
=
mid
+
1
"""this line is special, bucause python‘s list can be get [-2] element"""
if
i
-
1
<
=
high:
continue
"""find the high tag, then remove j - 1 --> j, last reset index [high + 1] element to tmp"""
for
j
in
range
(i, high
+
1
,
-
1
):
list
[j]
=
list
[j
-
1
]
list
[high
+
1
]
=
tmp
print
list
return
list
3、希尔排序
"""
delta = 10 / 2 = 5
49 38 65 97 26 13 27 49 55 4
1A 1B
2A 2B
3A 3B
4A 4B
5A 5B
delta = 5 / 2 = 2
13 27 49 55 4 49 38 65 97 26
1A 1B 1C 1D 1E
2A 2B 2C 2D 2E
delta = 2 / 2 = 1
4 26 13 27 38 49 49 55 97 65
1A 1B 1C 1D 1E 1F 1G 1H 1I 1J
delta = 1 / 2 = 0
4 13 26 27 38 49 49 55 65 97
"""
def
shellSort(
list
):
delta
=
len
(
list
)
while
delta
/
2
>
0
:
delta
=
delta
/
2
for
i
in
range
(delta,
len
(
list
)):
tmp
=
list
[i]
j
=
i
-
delta
while
j >
=
0
and
tmp <
list
[j]:
list
[j
+
delta]
=
list
[j]
j
-
=
delta
list
[j
+
delta]
=
tmp
print
list
return
list
数据结构--插入排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。