@[TOC](Shell Sort:)

谢尔排序基本知识：

我们注意到插入排序的对比次数，在最好的情况下是O（n），这种情况发生在列表已是有序的情况下，实际上，列表越接近有序，插入排序的对比次数就越少。
从这个情况入手，谢尔排序以插入排序为基础，对无序表进行“间隔”划分子列表，每个字列表都执行插入排序！

粗看上去，谢尔排序以插入排序为基础，可能并不会比插入排序好
但由于每趟都会使列表更加接近有序，这个过程会减少很多原先需要的“无效”比对。
其时间复杂度是：（n的2/3次方）

谢尔排序代码：

# -*-coding:utf-8 -*-
# @Author:到点了,心疼徐哥哥
# 奥利给干！！！
def shellSort(alist):
    subiscount=len(alist)//2
    while subiscount>0:
        for startposition in range(subiscount):
            gapcharu(alist,startposition,subiscount)
        print("After increments of size",subiscount,"The list is",alist)
        subiscount = subiscount//2
def gapcharu(alist,start,gap):
    for i in range(start+gap,len(alist),gap):
        xinxiang=alist[i]
        position=i
        while position >= gap and alist[position - gap] > xinxiang:
            alist[position] = alist[position - gap]
            position = position - gap
        alist[position] = xinxiang
alist=[11,25,5,9,4,55]
shellSort(alist)
print(alist)

@TOC

插入排序基本知识

插入排序时间复杂度是O（n的平方），但算法思路和冒泡排序选择排序不同；
插入排序维持一个已经排好序的子列表，其位置始终在列表前部，然后逐步扩大这个子列表直到全表。
第一趟，子列表中只有一个数据项，将第二个数据作为新项插入到子列表中，这样就具有了两个数据项。
第二趟，再继续将第三个数据项跟前两个数据项比对，并移动比自身大的数据项，空出位置来，以便加入到子列表中。
经过n-1趟的对比和插入，子列表扩展到全表，排序完成。

1.插入排序的对比主要用来寻找新项的插入位置
2.最差的情况是每趟都与子列表中的所有项进行比对，总对比次数与冒泡排序相同，数量仍是O（n的平方）
3.最好的情况是列表已经排好序时，每趟仅进行一次比对，总次数O（n）

插入排序代码

#-*-coding:utf-8 -*-
#@Author:到点了,心疼徐哥哥
#奥利给干！！！
def cahru(alist):
    for index in range(1,len(alist)):
        xinxiang=alist[index]
        position=index
        while position>0 and alist[position-1]>xinxiang:
            alist[position]=alist[position-1]
            position=position-1
        alist[position]=xinxiang
alist=[11,5,9,66,3,1]
cahru(alist)
print(alist)