归并排序c语言链表实现,归并排序链表实现

素颜马尾好姑娘i 2022-10-15 00:59 221阅读 0赞

该楼层疑似违规已被系统折叠 隐藏此楼查看此楼

void sort() \{

//其意义是if(empty() || size()==1 ) 但是这样做没有效率

if (node->next == node || node->next->next == node)return;

list carry;//缓冲链表

list counter\[64\];//链表数组,也是缓冲数组的counter\[i\]代表第i个位置上元素有2的i次方个 int fill = 0;//表示在counter\[64\]这个数组里面用了多少

while (!empty()) \{ carry.splice(carry.begin(),\*this,begin());//把首节点放入缓冲链表

int i = 0;

/\*

\*一开始carry 获得一个节点,但是不足以启动以下循环,然后这个节点

\*被交换到counter\[0\], fill++,第二次carry 获得一个节点(此时仍然

\*只有一个节点),启动下面的循环一次,counter\[0\]合并和carry,此时counter\[0\]

\*有两个节点,然后counter\[0\]的内容被交换给carry,循环结束,经过下面两步后

\*fill=2,carry 重新为空,counter\[0\]为空,counter\[1\]有两个节点

\*如此上述过程,每次从list取一个元素,让其存在于counter链表数组中

\*最终归并

\*/

while (i < fill && !counter\[i\].empty())

\{

counter\[i\].merge(carry);//把缓冲carry合并到这个list

carry.swap(counter\[i++\]);//把这个list重新换给缓冲carry

\}

carry.swap(counter\[i\]);//循环结束把缓冲carry的内容换到缓冲数组上

if (i == fill)

\++fill;

\}

for (int i = 1;i < fill;++i)

counter\[i\].merge(counter\[i - 1\]);

swap(counter\[fill - 1\]);

\}

可以参考一下STL双链表的 归并排序

发表评论取消回复

表情：

评论列表（有 0 条评论，221人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode.148.排序链表——归并排序

leetcode.148.排序链表我们可以用[147. 对链表进行插入排序][147.]的方法来解。 class Solution { public

水深无声/ 2022年12月23日 00:42/ 0 赞/ 212 阅读

相关归并排序 C语言实现

归并排序 ( Merging Sort )就是将两个或两个以上的有序表合并成一-个有序表的过程。将两个有序表合并成个有序表的过程称为2-路归并，2-路归并最为简单和常用。

川长思鸟来/ 2022年12月23日 00:35/ 0 赞/ 195 阅读

相关 (高频考题)148. 排序链表(归并排序)

题目要求时间空间复杂度分别为O(nlogn)O(nlogn)和O(1)O(1)，根据时间复杂度我们自然想到二分法，从而联想到归并排序；对数组做归并排序的空间复杂度为 O(n

阳光穿透心脏的1/2处/ 2022年12月10日 03:44/ 0 赞/ 201 阅读

相关归并排序c语言链表实现,归并排序链表实现

该楼层疑似违规已被系统折叠隐藏此楼查看此楼 void sort() \{ //其意义是if(empty() || size()==1 ) 但是这样做没有效率 if (n

素颜马尾好姑娘i/ 2022年10月15日 00:59/ 0 赞/ 222 阅读

相关归并排序（C语言实现）

\include <stdio.h> \include <stdlib.h> void merge(int A\[\], int p, int q, int r)

谁借莪１个温暖的怀抱￠/ 2022年09月23日 08:29/ 0 赞/ 202 阅读

相关 Leetcode 148. 排序链表(归并)

题目重述给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链

傷城~/ 2022年09月14日 14:22/ 0 赞/ 206 阅读

相关链表排序--归并排序

要求在空间复杂度为O(1)的情况下对链表进行排序，在不考虑时间复杂度的情况下可以考虑冒泡排序，只对链表中的值进行操作，这样时间复杂度为O（n^2）。用归并排序，时间复杂度为O（

￡神魔★判官ぃ/ 2022年06月07日 07:10/ 0 赞/ 205 阅读

相关链表排序算法java实现（链表的快速排序、插入排序、归并排序）

难易程度：★★ 重要性：★★★ 链表的排序相对数组的排序更为复杂些，也是考察求职者是否真正理解了排序算法（而不是“死记硬背”） 1. 链表的插入排序

左手的ㄟ右手/ 2022年05月09日 05:54/ 0 赞/ 283 阅读

相关链表排序-归并

链表排序，可以插入排序，我就不写了。实现归并排序归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Con

男娘i/ 2022年05月08日 06:06/ 0 赞/ 254 阅读

相关 leetcode:148. 排序链表(归并排序)

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。示例 1: 输入: 4->2->1->3 输出: 1->2->3->4 示例

矫情吗；*/ 2021年09月28日 15:10/ 0 赞/ 340 阅读