目录
单链表的快速排序
单链表的插入排序
单链表的快速排序和数组的快排基本思想相同,同样是不断划分。(以从小到大排序为例)取一个结点设其为关键结点,将所有结点的数字与其比较,比关键结点数字大的放在结点的右边,比关键结点数字小的放在关键结点的左边。
单个排序为例(privot指针指向的为关键结点,p为与其比较的数字的结点,i指针指向所比较数字的上一个结点):
此链表设4为关键节点,3比4小因此应该放在4的左边,因此交换两节点的位置。交换结点的代码如下:
交换后则p应该向前移一位,此时p与pr结点相同,不符合以上交换条件,则指针位置并不改变,但由于循环会使p向后移一位,因此在不交换结点时,应该让i指针向后移一位。
以此类推,当此次循环结束可知关键结点左边都比它小,右边都比它大,即关键结点的位置确定了。因此使关键结点左边与右边分成两半,分别以同样的方式排序,即进入递归。通过递归排序完成。
单链表的快速排序代码如下:
(以从小到大为例)插入排序为以第二个数字开始,将每一个数字插入到比它小的数字之前,curr指针所指向的为被插入的结点位置,与前一个结点进行比较,如果它比前一个结点数字小即代表它需要插入。进入内层循环,prev所指向的结点为插入位置的前一个结点,当prev的下一个结点的数字大于我们所要插入的结点数字时,进行插入操作。
因为3比4小因此将3进行插入操作。插入时应先时prev位于头结点位置,进行循环,找到插入点。
插入操作代码如下:
如果curr指向的数字比l指向的数字大,无需插入,则使两个指针都向后移,若出现了插入操作只需使curr放在l的后一个结点。
单链表的插入排序代码如下:
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/bian-cheng-ri-ji/32038.html