概要
-IDE：Pycharm
-Python版本：python3.x
-算法分类：内部排序->插入类排序->直接插入排序
算法思想
直接插入排序是一种最基本的插入排序方法，其基本操作是将第$i$个记录插到前面$i-1$个记录中。然后将大于自身的记录从后往前依次向后移一位.
例如：将第$i$个记录的关键字$K_i$顺次与前面的$K_{i-1},K_{i-2},...,K_1$进行比较，将所有大于$K_i$的记录依次向后移动一位。直到遇到小于$K_i$的记录，假设此记录为$K_j（j<i）$，依次向后移了之后位置$i$必定为空。此时将$K_i$，放入$K_j（j<i）$的位置。
为提高效率，辅设一监视哨（可以自己设置建议使用r[0]）,监视哨作用有两个，一是备份待插入记录，二是防止越界。
算法分析
从空间角度来看，它只需要一个辅助空间。从时间角度来看，耗费时间主要是比较和移动元素。
对于一趟循环来说：
-最好情况顺序：$r[i].key>r[i-1].key$，while循环只执行一次，且不移动记录。
-最坏情况逆序：$r[i].key<r[1].key$，while循环中关键字比较次数和一从次数为$i-1$
对于整个循环来说：
-最好情况下比较总次数达到了$n-1$次，移动记录的次数也达到最小值$2(n-1)$次。
-最坏情况下比较总次数到到了$(n+2)(n-1)/2$次，移动记录的次数也达到了$(n+4)(n-1)/2$次。
算法要点
-使用使用监视哨r[0]临时保存待插入记录。
-从后往前寻找插入位置。
-查找与移动同一循环完成。
稳定性与时间复杂度
| 排序算法 | 稳定性 | 时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|---|---|
| 直接插入 | 稳定 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ |
Python代码清单
# !/usr/bin/python3
# _*_ coding:utf-8 _*_
# 直接插入排序
import sys # 导入sys，使用argv接收外部参数。
import time # 导入time 用time() 进行记时。
import random # 导入随机数包生存随机数
def SSS(number,maxNumber): # 算法，number是传入生成的个数,maxNumber代表生成的最大数
# 生成随机数
timeStart = time.time()
listA = [0] # 0位 监视哨
for i in range(number):
listA.append(random.randint(0, maxNumber)) # 添加生成的值。
timeEnd = time.time()
timeIs = timeEnd-timeStart
print('生成%d个数的时间是%f' % (number, timeIs))
#print(listA[1:])
####################################################
# 进行排序
timeStart = time.time()
for aim in range(2, number+1): # 循环遍历列表,因为设置了监视哨所以生成的位数多了一位，这里遍历自然+1
index = aim # 用来做索引
listA[0] = listA[aim] # 设置监视哨的值。
while(listA[index-1] > listA[0]): # 循环查询监视哨之前的那个值不大于监视哨。
listA[index] = listA[index-1] # 向后挪一位。
index = index-1 # 索引向前一位。
listA[index] = listA[0] #符合条件，进行插入。
timeEnd = time.time()
timeIs = timeEnd-timeStart
print('排序%d个数的时间是%f' % (number, timeIs))
print(listA[1:])
if __name__ == '__main__':
helpInfo = '''
This program is for Straight Select Sorting.
How to use it! Follow the example!
python Straight_Select_Sorting.py 10 100
The 10 representative will generate ten numbers.
100 representative the max-number you make.
'''
command = sys.argv[0:] # 从键盘获取输入信息。
lenght = len(command) # 计算信息长度
if lenght != 3 or 'help' in command: # 第一判断，对长度是否合法与是否有帮助文字进行判断。
print(helpInfo)
else:
try:
number = int(command[1]) # 第二次判断，对输入数据进行int转化，即判断是否为int
maxNumber = int(command[2])
except ValueError:
print(helpInfo)
sys.exit(1) # 若不是int，则退出程序
SSS(number, maxNumber) # 调用方法，生成序列并排序。
总结
学时容易写时难。学得时候我们学得是理论，而写的时候则完全不一样。你需要知道每一步是如何变化的。把一个整体要全部分解为原子，这需要不断的练习。
有什么问题请联系我
QQ：3116316431 (请附上信息）
E-mail：wongyinlong@yeah.net