# 表插入排序

这种方式需要引入一个有序循环集合，并在有序循环集合中将最小、最大的元素分别标记为first、end
取无序集合的的每个元素从有序集合的最小元素开始比较直到匹配的合适的位置插入。
与2-路插入排序原理比较，引入了链表的概念，避免元素的移动。

nputArr = [ 11,10,199383, 34, -1,-32,-29, 4, 0, 34, 5, 4, 36, 1, 8, 123, 453, 1008]

length = len(inputArr)

print("未排序集合:{0}".format(inputArr))
# 定义个链表结构
class Element(object):
    def __init__(self,currItem,nextElement=None):
        self.currItem=currItem
        self.nextElement=nextElement

# 初始化链表头
firstElement=Element(inputArr[0])
endElement=firstElement.nextElement
for index in range(1,length):
    item=inputArr[index]
    # 小于头的
    if(item<=firstElement.currItem):
        firstElement=Element(item,firstElement)
        if(endElement==None):
            endElement = firstElement.nextElement
        continue
    # 第二个元素
    if(firstElement.nextElement==None):
        endElement=firstElement.nextElement=Element(item)
        continue
    # 大于头的
    if(item >= endElement.currItem):
        endElement.nextElement=Element(item)
        endElement=endElement.nextElement
        continue
    
    ## 大于头且小于尾的
    curr=firstElement
    next=curr.nextElement
    while (next!=None):
        if(item<=next.currItem):
            curr.nextElement = Element(item,next)
            break
        curr=next
        next=curr.nextElement

# 输出
outIndex=0
next=firstElement
while(next!=None):
    inputArr[outIndex] = next.currItem
    outIndex+=1
    next=next.nextElement

print("已排序集合:{0}".format(inputArr))