相比于定义一个循环双向链表来实现插入排序来说，下面的实现采用一个单向循环链表来实现，并且不需要定义一个单向循环链表类，而是把一个list（数组/顺序表）当成单向循环链表来用，list的元素是一个包含两个元素的对象，一个是数值，一个是指向下一个list元素的指针（list的元素下标），list的第一个元素（下标为0的元素）是单链表的头结点，它不存放数据，起到哨兵的作用。
排序的时候，把一个数据元素插入一个位置，不需要移动数据，只需要修改该位置前一个list元素和待插入数据元素的指针域就行，其实就是个单向链表的插入操作。
通过一遍循环操作完成排序之后，顺序表就被链表化了。
下面给出一个顺序表被链表化的过程的图示：
可以很方便的按照访问链表的方式来完成对数据的有序（正序/逆序）遍历访问，但如果是执行查找，不能进行二分查找，只能顺序查找，效率不高，所以还需要把顺序表变成有序表。
有两种方式来实现这一点。
第一种，可以new一个空的list，遍历链表，依次把访问到的元素append到list中，最后返回这个list。
第二种，就地对顺序表重排，实现的逻辑并不复杂，思路是依次取链表的数据元素把它们依次从前往后排在顺序表中，如果它们本身就在应该排的位置什么都不用做，取下一个数据元素继续，如果它们不在应该排的位置上，那么把它们和当前占着该位置的数据元素交换，并且把它们的指针域改成交换出去的数据元素交换到的位置，当后续对被交换出去的数据元素排位的时候，根据它前一结点指针域访问的是它在顺序表中旧（最初）的位置，需要从现在占用它旧位置的数据元素的指针域去取它的当前位置，但有可能在前面的排位过程中它的位置被调换了多次，因此这可能是一个连锁式的查找过程，这个算法的复杂性全在这一点上了。
下面给出一个顺序表重排变成一个有序表的过程的图示：
下面给出代码实现：
def sortwrap(inplace=True):
def inner(f):
if inplace:
def sort(source):
source = f(source)
next = source[0][1]
for i in range(1, len(source)):
if i != next:
source[i], source[next] = source[next], source[i]
next, source[i][1] = source[i][1], next
else:
next = source[i][1]
while next <= i and next != 0:
next = source[next][1]
return source
else:
def sort(source):
source = f(source)
pos = source[0][1]
result = []
while pos != 0:
result.append(source[pos][0])
pos = source[pos][1]
return result
return sort
return inner
@sortwrap()
def _insertsort(source):
if not source:
return source
_source = [[0, 0]]
_source += [[i, 0] for i in source]
head = _source[0]
head[1] = 1
_source[1][1] = 0
for i in range(2, len(_source)):
prev = head
while _source[prev[1]] is not head:
if _source[i][0] < _source[prev[1]][0]:
_source[i][1] = prev[1]
prev[1] = i
break
else:
prev = _source[prev[1]]
else:
_source[i][1] = prev[1]
prev[1] = i
return _source
print(_insertsort((49, 38, 65, 97, 76, 13, 27, 52)))这个算法的亮点是实现了顺序表和链表的互转，挺有启发意义的。
