单向链表排序（单链表实现排序）



       相比于定义一个循环双向链表来实现插入排序来说，下面的实现采用一个单向循环链表来实现，并且不需要定义一个单向循环链表类，而是把一个list（数组/顺序表）当成单向循环链表来用，list的元素是一个包含两个元素的对象，一个是数值，一个是指向下一个list元素的指针（list的元素下标），list的第一个元素（下标为0的元素）是单链表的头结点，它不存放数据，起到哨兵的作用。

        排序的时候，把一个数据元素插入一个位置，不需要移动数据，只需要修改该位置前一个list元素和待插入数据元素的指针域就行，其实就是个单向链表的插入操作。

        通过一遍循环操作完成排序之后，顺序表就被链表化了。

        下面给出一个顺序表被链表化的过程的图示：

       可以很方便的按照访问链表的方式来完成对数据的有序（正序/逆序）遍历访问，但如果是执行查找，不能进行二分查找，只能顺序查找，效率不高，所以还需要把顺序表变成有序表。

        有两种方式来实现这一点。

        第一种，可以new一个空的list，遍历链表，依次把访问到的元素append到list中，最后返回这个list。

       第二种，就地对顺序表重排，实现的逻辑并不复杂，思路是依次取链表的数据元素把它们依次从前往后排在顺序表中，如果它们本身就在应该排的位置什么都不用做，取下一个数据元素继续，如果它们不在应该排的位置上，那么把它们和当前占着该位置的数据元素交换，并且把它们的指针域改成交换出去的数据元素交换到的位置，当后续对被交换出去的数据元素排位的时候，根据它前一结点指针域访问的是它在顺序表中旧（最初）的位置，需要从现在占用它旧位置的数据元素的指针域去取它的当前位置，但有可能在前面的排位过程中它的位置被调换了多次，因此这可能是一个连锁式的查找过程，这个算法的复杂性全在这一点上了。

       下面给出一个顺序表重排变成一个有序表的过程的图示：

      下面给出代码实现：

       这个算法的亮点是实现了顺序表和链表的互转，挺有启发意义的。  

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/46424.html