嵌入式学习day18

链表插入排序学习笔记一、核心思想与算法原理1.1 基本概念插入排序Insertion Sort 是一种简单直观的排序算法其核心思想是将无序区的元素逐个插入到有序区的适当位置最终使整个序列有序。1.2 军训比喻直观理解想象新生军训排队• 初始状态只有一个标兵第一个元素站在正确位置 → 有序区• 其他新生剩余元素随机站着 → 无序区• 教官工作从无序区逐个叫出新生让他们插入到有序区的正确位置初始 [标兵] | 新生A, 新生B, 新生C…有序区 无序区过程 叫出新生A → 比较 → 插入到标兵前/后[标兵, 新生A] | 新生B, 新生C…最终 所有新生按高矮顺序排好1.3 算法伪代码for(intj1;jn;j){// j从1开始第0个元素默认有序keyarr[j];// 从无序区取出第j个元素// 在有序区arr[0..j-1]中从后向前扫描找到插入位置intij-1;while(i0arr[i]key){arr[i1]arr[i];// 元素后移i--;}arr[i1]key;// 插入到正确位置}二、单向链表插入排序详解2.1 链表排序的特殊性数组 vs 链表插入排序关键区别对比维度 数组实现 单向链表实现有序区访问 可随机访问下标 只能顺序访问指针遍历插入操作 需要移动后方所有元素 只需修改指针O(1)时间查找位置 从后往前比较 只能从前往后比较找插入点2.2 算法步骤分解结合图片示意图初始状态head → [4] → [2] → [3] → [1] → NULL• 第一个节点 [4] 视为初始有序区• 从第二个节点 [2] 开始为无序区步骤1划分两个区域有序区: head → [4] → NULL无序区: [2] → [3] → [1] → NULL↑已断开代码关键sorted_head head; // 有序链表头head head-next; // 无序链表头sorted_head-next NULL; // 断开有序与无序区步骤2处理第一个无序节点 [2]有序区查找 [4] 比 2 大 → 2应插在4前面插入结果 head → [2] → [4] → NULL指针操作详解保存 [2] 的下一个节点 [3]在有序区找到插入点[4]前面修改指针[2]→next [4], sorted_head [2]步骤3处理节点 [3]有序区: [2] → [4]查找 2 3 4 → 3应插在2和4之间结果 [2] → [3] → [4]关键技巧• 需要两个指针遍历有序区• prev指向当前比较节点的前一个• curr当前比较节点• 当 curr-data key 时停止在 prev 和 curr 之间插入步骤4处理节点 [1]有序区: [2] → [3] → [4]1比所有都小 → 插入到最前面最终 [1] → [2] → [3] → [4]2.3 完整算法流程// 单向链表插入排序核心代码ListNode*insertionSortList(ListNode*head){if(!head||!head-next)returnhead;ListNode*sorted_headhead;// 有序链表头ListNode*currhead-next;// 从第二个节点开始处理sorted_head-nextNULL;// 断开有序区while(curr){ListNode*next_nodecurr-next;// 保存下一个待处理节点// 情况1当前节点比有序区头还小 → 成为新头if(curr-valsorted_head-val){curr-nextsorted_head;sorted_headcurr;}// 情况2在有序区中间找插入位置else{ListNode*searchsorted_head;// 找到第一个比curr大的节点的前一个位置while(search-nextsearch-next-valcurr-val){searchsearch-next;}// 插入到search之后curr-nextsearch-next;search-nextcurr;}currnext_node;// 处理下一个无序节点}returnsorted_head;}三、链表选择排序简介3.1 选择排序核心思想每次从无序区选择最小或最大元素放到有序区末尾3.2 链表实现特点初始 [4] → [2] → [3] → [1]第1轮找到最小值1与头部4交换[1] → [2] → [3] → [4]第2轮在[2]→[3]→[4]中找到最小值2已在正确位置…依次类推3.3 插入排序 vs 选择排序链表版特性 插入排序 选择排序时间复杂度 最好O(n)最差O(n²) 固定O(n²)空间复杂度 O(1)原地排序 O(1)链表适用性 非常适合 一般稳定性 稳定排序 不稳定交换节点时实际性能 对小规模或基本有序数据效率高 无论数据如何都需要完整遍历四、关键技巧与常见错误4.1 链表插入排序的三个关键指针sorted_head始终指向有序链表的头部prev在有序区查找时指向可能插入位置的前一个节点next_temp必须提前保存当前节点的下一个节点否则断开链接后会丢失4.2 边界情况处理// 处理空链表或单节点链表if(headNULL||head-nextNULL){returnhead;}// 处理插入位置在头节点之前的情况if(curr-valsorted_head-val){curr-nextsorted_head;sorted_headcurr;// 不要忘记更新curr}// 处理插入位置在末尾的情况while(search-next!NULLsearch-next-valcurr-val){searchsearch-next;}// 循环结束后search指向有序区最后一个小于curr的节点4.3 调试技巧画图法初始状态图画出所有节点和指针每一步快照在处理每个节点时画出指针变化前和变化后的状态特别关注哪些指针需要修改、修改的顺序是什么示例调试图处理节点[3]时修改前 sorted→[2]→[4] curr→[3]→[1]search↑(指向2)修改后 sorted→[2]→[3]→[4] curr→[1]五、时间复杂度分析5.1 最坏情况完全逆序初始 [4]→[3]→[2]→[1]每次插入都需要遍历整个有序区第1次比较1次4第2次比较2次4,3第3次比较3次4,3,2总比较次数12…(n-1) n(n-1)/2 → O(n²)5.2 最好情况已经有序初始 [1]→[2]→[3]→[4]每次插入只需要比较一次与有序区尾部总比较次数n-1 → O(n)5.3 空间复杂度• 原地排序只使用常数个额外指针变量• 空间复杂度O(1)六、实际应用与练习建议6.1 什么时候用链表插入排序• 数据规模较小n 100• 链表已经基本有序• 需要稳定排序且空间受限• 作为更复杂算法如TimSort的子过程6.2 推荐练习题目基础实现LeetCode 147 - 对链表进行插入排序变体练习排序循环链表、双向链表对比理解同时实现链表插入排序和选择排序比较性能6.3 学习检查清单能手动模拟插入排序全过程画图能独立写出无bug的链表插入排序代码理解为什么链表插入排序要从前往后找位置能分析各种边界情况了解插入排序在实际系统中的使用场景附录完整C语言实现参考#includestdio.h#includestdlib.htypedefstructListNode{intval;structListNode*next;}ListNode;// 创建新节点ListNode*createNode(intval){ListNode*new_node(ListNode*)malloc(sizeof(ListNode));new_node-valval;new_node-nextNULL;returnnew_node;}// 链表插入排序核心函数ListNode*insertionSortList(ListNode*head){if(headNULL||head-nextNULL){returnhead;}ListNode*sorted_headhead;// 有序链表头ListNode*currhead-next;// 当前待插入节点sorted_head-nextNULL;// 断开有序区while(curr!NULL){ListNode*next_tempcurr-next;// 保存下一个节点// 情况1插入到有序链表头部if(curr-valsorted_head-val){curr-nextsorted_head;sorted_headcurr;}// 情况2在有序链表中查找插入位置else{ListNode*searchsorted_head;// 找到插入点search-next是第一个大于curr-val的节点while(search-next!NULLsearch-next-valcurr-val){searchsearch-next;}// 插入到search之后curr-nextsearch-next;search-nextcurr;}currnext_temp;// 处理下一个节点}returnsorted_head;}// 打印链表用于测试voidprintList(ListNode*head){while(head!NULL){printf(%d - ,head-val);headhead-next;}printf(NULL\n);}// 测试示例intmain(){// 创建链表: 4 - 2 - 3 - 1ListNode*headcreateNode(4);head-nextcreateNode(2);head-next-nextcreateNode(3);head-next-next-nextcreateNode(1);printf(原始链表: );printList(head);ListNode*sortedinsertionSortList(head);printf(排序后链表: );printList(sorted);return0;}关键输出原始链表: 4 - 2 - 3 - 1 - NULL排序后链表: 1 - 2 - 3 - 4 - NULL总结链表插入排序充分体现了链表的优势指针修改高效和劣势不能随机访问。掌握它不仅是为了学习排序算法更是为了深入理解链表这种数据结构的特性和操作逻辑。通过画图理解、手动模拟、代码实现三步走可以扎实掌握这一经典算法。