相比于定义一个循环双向链表来实现插入排序来说，下面的实现采用一个单向循环链表来实现，并且不需要定义一个单向循环链表类，而是把一个list（数组/顺序表）当成单向循环链表来用，list的元素是一个包含两个元素的对象，一个是数值，一个是指向下一个list元素的指针（list的元素下标），list的第一个元素（下标为0的元素）是单链表的头结点，它不存放数据，起到哨兵的作用。
排序的时候，把一个数据元素插入一个位置，不需要移动数据，只需要修改该位置前一个list元素和待插入数据元素的指针域就行，其实就是个单向链表的插入操作。
通过一遍循环操作完成排序之后，顺序表就被链表化了。
下面给出一个顺序表被链表化的过程的图示：
可以很方便的按照访问链表的方式来完成对数据的有序（正序/逆序）遍历访问，但如果是执行查找，不能进行二分查找，只能顺序查找，效率不高，所以还需要把顺序表变成有序表。
有两种方式来实现这一点。
第一种，可以new一个空的list，遍历链表，依次把访问到的元素append到list中，最后返回这个list。
第二种，就地对顺序表重排，实现的逻辑并不复杂，思路是依次取链表的数据元素把它们依次从前往后排在顺序表中，如果它们本身就在应该排的位置什么都不用做，取下一个数据元素继续，如果它们不在应该排的位置上，那么把它们和当前占着该位置的数据元素交换，并且把它们的指针域改成交换出去的数据元素交换到的位置，当后续对被交换出去的数据元素排位的时候，根据它前一结点指针域访问的是它在顺序表中旧（最初）的位置，需要从现在占用它旧位置的数据元素的指针域去取它的当前位置，但有可能在前面的排位过程中它的位置被调换了多次，因此这可能是一个连锁式的查找过程，这个算法的复杂性全在这一点上了。
下面给出一个顺序表重排变成一个有序表的过程的图示：
下面给出代码实现：
这个算法的亮点是实现了顺序表和链表的互转，挺有启发意义的。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ri-ji/40211.html