链表的插入排序

chosen0ne

2605人浏览 · 2010-01-18 20:09:00

chosen0ne · 2010-01-18 20:09:00 发布

相对于在数组上进行插入排序，链表的插入排序效率会更高一点，更形象（因为的确是插入的）。假设序列a[0..n-1]，a[0..j]是已排序的子序列，a[j+1]是待插入的元素。那么数组的插入排序时，不仅需要元素的比较，还要进行元素移动。而链表的插入排序时，仅仅需要通过比较找到插入位置，然后执行插入即可。所以，链表的排序中，插入排序是相对效率较高的排序

void List::insertSort(){ Node *headNode=new Node(head,0);//链表头结点 Node *last=head;// 已排序链表的尾 Node *now; //当前待插入节点 while(last->getNext()!=NULL){ now=last->getNext(); for(Node *iter=headNode;iter!=now;){ if(iter->getNext()->getData() < now->getData()) iter=iter->getNext(); else{///找到插入位置，在iter后 if(iter==last){ last=last->getNext(); } else{ last->setNext(now->getNext()); now->setNext(iter->getNext()); iter->setNext(now); } break; } } } head=headNode->getNext(); }

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能