1 Introduction

插入排序, 将新的未排序值插入到已排序的队列中, 重复以上流程.

直接插入排序: 通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间.

希尔排序: 缩小增量排序, 记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止.

2 直接插入排序

2.1 Anaylysis

本质上,一种比较类-非线性-插入类-排序.

民主自由的制度,不到最后,谁都不能确定村长是谁!(其实吧,结果还不是一样,选择的方向不同而已)

对比过程如下:

1
2
3
4
5
6
7
你,就是你,你身高多少?185?
比SB1高啊.....
SB1,你往后面走一步,index=SB1之前的位置
比SB2高啊....
SB2,你往后走一步,index=SB2之前的位置
嘿嘿,没有SB3高!
滚到index里面站着吧

插入排序的最优性能:

1
2
3
4
基本有序,此时做的操作基本为0
选择排序就不是咯,还是的选择出最大值
交换排序也是,但是吧
所以,希尔排序才会以插入排序为基础

insertsort

2.2 Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def insertSort(list1):
"""insertSort

:param list1:
"""
list_len = len(list1)

# 1,从改列的第二个元素开始
for i in range(1, list_len):
# 2,记住当前欲插入的元素为tmp
tmp = list1[i]
# 3,空闲位置
index = i
# 4,从前面的已排序序列的尾部开始往前遍历,递减比较
for j in range(i - 1, -1, -1):
if tmp < list1[j]:
list1[j + 1] = list1[j]
index = j
else:
break

list1[index] = tmp

return list1

3 希尔排序

3.1 Analysis

本质上,一种比较类-非线性-插入类-改进的插入-排序, 什么?你说插入排序最优和最差的区别好大?难道说?

  • 最优: 整个队列基本有序,此时O(n)
  • 最差:O(n*n)

最优时的特征: 越是基本有序,比较和移动的次数越小, n越小,O(n*n)越小哦(二分思维),
这就是希尔排序的提出原因, 因为基本插入排序每次移动一个一位, 所以进行了改进.

希尔希尔来临:

1
2
3
初期使用大跨度的间隔比较, 让记录跳跃式的接近它的排序位置.
之后增量减小, 进行小范围的记录跳跃式排序.
最后进行最后一次n=1, 完整的insert sort(n为列表全长)

排序流程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
原始字符串: 13, 14, 94, 33, 82, 25, 59,  ..., 25, 39, 10
如果step = 5,那么就有5列,对每一列进行插入排序:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
==============
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
如果step = 3, 则存在3列
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
=====
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后开始step=1, 进行简单插入排序, 此时大部分数据都是有序的, 理想情况下就是
一直插入末尾.

3.2 Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def shellSort(list1):
"""shellSort

:param list1:
"""
list_len = len(list1)
step = int(round(list_len / 2))

while step > 0:
# 注意,下面的排序思路完全仿照insertsort中的写法
for i in range(step, list_len):
# 第i/step列的第二位元素,之后变为第i/step + 1列,...
temp = list1[i]
index = i
for j in range(i - step, - 1, -step):
if list1[j] > temp:
list1[j + step] = list1[j]
index = j
else:
break
list1[index] = temp

step = int(round(step / 2))

return list1