拓冰网站定制 
示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇技术指南以 doocs/leetcode 仓库中 basic/sorting/InsertionSort/README.md 为核心系统讲解插入排序Insertion Sort的算法思想、执行流程、复杂度分析并完整给出 Python、Java、C、Go、Rust、JavaScript、C# 七种语言的仓库级实现。读完本文你将理解如何动态地向有序集合插入数据并保持有序这一核心思想掌握插入排序与冒泡排序的本质区别并能直接运行仓库中现成的多语言示例代码。从一个问题说起动态地往有序数组插入数据先看一个经典场景一个已经有序的数组我们向其中添加一个新数据后如何继续保持数据有序答案很简单从数组头部开始遍历找到新数据应当插入的位置将其插入即可。例如有序数组[1, 2, 7, 9]插入5时只需定位到2与7之间得到[1, 2, 5, 7, 9]。这是一个动态排序的过程持续向有序集合添加数据用上述插入法即可让集合一直保持有序。那么对于一组静态数据是否可以借鉴同样的思路完成整体排序这正是插入排序算法的由来。核心思想已排序区间与未排序区间插入排序的具体做法如下将数组划分为两个区间——已排序区间和未排序区间初始时已排序区间只包含数组的第一个元素单个元素天然有序其余元素全部位于未排序区间每次从未排序区间取出一个元素在已排序区间中找到合适的插入位置并插入保证已排序区间始终有序重复上述过程直到未排序区间为空整个数组有序算法结束。简单来说插入排序就是每轮取一个新元素通过插入操作把它并入已有序的前缀不断扩张有序前缀的长度。插入排序与冒泡排序的对比冒泡排序与插入排序同为 O(n²) 级别的经典排序算法但两者有序区的成长方向恰好相反冒泡排序经过每一轮排序处理后数组后端末尾的数是有序的——大元素像气泡一样逐步上浮到尾部插入排序经过每一轮排序处理后数组前端开头的数是有序的——新元素被逐个插入到有序前缀中。这一差异决定了插入排序在近乎有序的输入上往往表现更优见下文复杂度分析也是工程实践中常将插入排序用作快排等高级算法收尾步骤的原因。逐步执行演示以数组[10, 17, 50, 7, 30]为例观察插入排序每一轮的状态|左侧为已排序区间轮次取出元素操作数组状态初始——[10] \| [17, 50, 7, 30]i11717 10原地不动[10, 17] \| [50, 7, 30]i25050 17原地不动[10, 17, 50] \| [7, 30]i37与 50、17、10 依次比较插入头部[7, 10, 17, 50] \| [30]i430与 50 比较后插入 17 与 50 之间[7, 10, 17, 30, 50]可以看到每一轮结束后前端的有序区间长度都增加 1直至整个数组有序。复杂度与稳定性分析从算法结构可以直接推导出以下结论标准算法分析非仓库声称数据时间复杂度最好情况输入已有序每轮只需比较一次即完成插入时间复杂度O(n)最坏情况输入逆序第 i 轮需要移动 i 次总比较/移动次数约为 n²/2时间复杂度O(n²)平均情况时间复杂度O(n²)。空间复杂度所有实现均为原地排序仅使用若干临时变量空间复杂度O(1)。稳定性插入排序是稳定排序。当待插入元素与已排序区间中某个元素相等时将其插到该元素之后不会改变相等元素的相对次序。值得强调的是插入排序的最佳时间复杂度 O(n) 是其在数据基本有序场景下优于多数 O(n²) 算法如选择排序的关键——选择排序无论输入如何都需进行 O(n²) 次比较。多语言代码示例仓库在 basic/sorting/InsertionSort/ 目录下为每个语言同时提供了InsertionSort.*与Solution.*两份实现文件内容一致可直接运行验证。以下示例完整继承自原文档并标注了对应的仓库源码文件路径。Python3对应源码InsertionSort.py 与 Solution.pydef insertion_sort(array): for i in range(len(array)): cur_index i while array[cur_index - 1] array[cur_index] and cur_index - 1 0: array[cur_index], array[cur_index - 1] ( array[cur_index - 1], array[cur_index], ) cur_index - 1 return array array [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] print(insertion_sort(array))这段实现采用相邻交换式写法内层循环通过反复交换相邻元素把当前元素逐步搬运到已排序区间中的正确位置语义直观、易于理解。Java对应源码InsertionSort.java 与 Solution.javaimport java.util.Arrays; public class InsertionSort { private static void insertionSort(int[] nums) { for (int i 1, j, n nums.length; i n; i) { int num nums[i]; for (j i - 1; j 0 nums[j] num; --j) { nums[j 1] nums[j]; } nums[j 1] num; } } public static void main(String[] args) { int[] nums {1, 2, 7, 9, 5, 8}; insertionSort(nums); System.out.println(Arrays.toString(nums)); } }这是经典的平移插入式写法先用num保存当前元素随后把大于num的已排序元素统一向右平移一位nums[j 1] nums[j]最后将num放入腾出的空位nums[j 1]。相比相邻交换平移式写法减少了交换开销是插入排序最常见的工程实现。C对应源码InsertionSort.cpp 与 Solution.cpp#include iostream #include vector using namespace std; void printvec(const vectorint vec, const string strbegin , const string strend ) { cout strbegin endl; for (auto val : vec) { cout val \t; } cout endl; cout strend endl; } void insertsort(vectorint vec) { for (int i 1; i vec.size(); i) { int j i - 1; int num vec[i]; for (; j 0 vec[j] num; j--) { vec[j 1] vec[j]; } vec[j 1] num; } return; } int main() { vectorint vec {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; printvec(vec); insertsort(vec); printvec(vec, after insert sort); return (0); }该示例特意选用完全逆序的{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}作为输入用于展示插入排序在最坏情况下的执行过程并借助printvec输出排序前后的数组。Go对应源码InsertionSort.go 与 Solution.gopackage main import fmt func insertionSort(nums []int) { for i, n : 1, len(nums); i n; i { j, num : i-1, nums[i] for ; j 0 nums[j] num; j-- { nums[j1] nums[j] } nums[j1] num } } func main() { nums : []int{1, 2, 7, 9, 5, 8} insertionSort(nums) fmt.Println(nums) }Go 版本与 Java 版结构完全一致外层循环从第二个元素开始内层循环将大于num的元素右移最终在nums[j1]处落位。Rust对应源码InsertionSort.rs 与 Solution.rsfn insertion_sort(nums: mut Veci32) { let n nums.len(); for i in 1..n { let mut j i - 1; let temp nums[i]; while j (0 as usize) nums[j] temp { nums[j 1] nums[j]; j - 1; } nums[j 1] temp; } } fn main() { let mut nums vec![1, 2, 7, 9, 5, 8]; insertion_sort(mut nums); println!({:?}, nums); }Rust 版本以mut Veci32形式原地修改数组并通过j (0 as usize)处理usize下界判断避免索引下溢体现了 Rust 在索引边界上的严谨性。JavaScript对应源码InsertionSort.js 与 Solution.jsfunction insertionSort(inputArr) { let len inputArr.length; for (let i 1; i len - 1; i) { let temp inputArr[i]; let j i - 1; while (j 0 inputArr[j] temp) { inputArr[j 1] inputArr[j]; j--; } inputArr[j 1] temp; } return inputArr; } let arr [6, 3, 2, 1, 5]; console.log(insertionSort(arr));C#对应源码InsertionSort.cs 与 Solution.csusing System.Diagnostics; using static System.Console; namespace Pro; public class Program { public static void Main() { int[] test new int[] { 31, 12, 10, 5, 6, 7, 8, 10, 23, 34, 56, 43, 32, 21 }; InsertSortNums(test); foreach (var item in test) { WriteLine(item); } } public static void InsertSortNums(int[] nums) { for (int initial 1; initial nums.Length; initial) { for (int second_sort 0; second_sort initial; second_sort) { if (nums[second_sort] nums[initial]) { swap(ref nums[second_sort], ref nums[initial]); } } } } private static void swap(ref int compare_left, ref int compare_right) { int temp compare_left; compare_left compare_right; compare_right temp; } }C# 版本实现风格有所不同内层循环从已排序区间头部开始一旦发现某个元素大于当前待插入元素立即通过swap交换两者。虽然每次交换只前进一位、效率略低于平移式写法但代码更接近插入的语义可读性更强适合作为教学示例。注意该示例数组含重复元素10排序后仍能保持相对次序可作为验证插入排序稳定性的直观用例。两种实现风格的辨析综合上述七种语言实现可以归纳出插入排序的两类编码风格平移插入式Java / C / Go / Rust / JavaScript先暂存当前元素num将已排序区间中所有大于num的元素右移一位最后一次性把num写入空位。该方式移动次数与比较次数相当性能更优。相邻交换式Python / C#通过反复交换相邻元素把当前元素逐步挤到正确位置。该方式每一步都保持了数组其他元素的相对位置代码直观但交换操作比单纯的赋值更昂贵。从仓库源码结构看各语言的InsertionSort.*与Solution.*文件内容一致均以可直接运行的完整程序含main与示例数据形式提供便于读者逐个语言对照学习。优化思路在实际工程中插入排序常配合以下优化手段提前终止若内层循环中发现待插入元素已经大于等于已排序区间末尾元素则本轮无需任何移动直接进入下一轮。这是输入近乎有序时达到 O(n)的实现基础。二分插入排序由于已排序区间本身有序可以使用二分查找定位插入位置将比较次数从 O(n) 降为 O(log n)但元素平移次数仍为 O(n)因此总体时间复杂度不变仅常数因子改善。作为高级排序的收尾插入排序在小规模或近似有序数据上常数因子极小常被用作快速排序、希尔排序在递归到小数组时的收尾算法希尔排序本质上是插入排序的分组跳跃版本仓库中的 ShellSort 目录即是对应的多语言实现。适用场景小结插入排序适合以下场景数据规模较小如 n ≤ 几十输入数据基本有序此时时间复杂度逼近 O(n)需要稳定排序且要求原地、O(1) 额外空间作为其他排序算法的底层子过程。若需进一步对比学习仓库 basic/sorting/ 下还提供了冒泡排序BubbleSort、选择排序SelectionSort、归并排序MergeSort、快速排序QuickSort、堆排序HeapSort、希尔排序ShellSort、计数排序CountingSort等多语言实现可作为算法复杂度横向对比的参考资料基础算法总览可参见 basic/README.md。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode-Go 题解147. Insertion Sort List链表插入排序LeetCode Go 题解147. Insertion Sort List链表插入排序 导读 本文讲解 LeetCode 第 147 题「Inserti示例工程AlgoNote 数组插入排序Insertion Sort详解思想、步骤、代码与复杂度分析AlgoNote 数组插入排序Insertion Sort详解思想、步骤、代码与复杂度分析 导读 本文是《算法通关手册》AlgoNote 仓库「数组排序教程文档知识库LeetCode-Go 题解147. Insertion Sort List 链表的插入排序实现与源码解析LeetCode Go 题解147. Insertion Sort List 链表的插入排序实现与源码解析 导读 本文以 LeetCode 第 147 题「I示例工程上一篇KotlinMvp数据层设计构建可扩展的Model层架构下一篇OpenNews MCP核心功能解析新闻聚合、AI评级与交易信号全攻略创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 doocs/leetcode 插入排序（Insertion Sort）算法详解：动态有序插入思想与多语言实现
示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇技术指南以 doocs/leetcode 仓库中 basic/sorting/InsertionSort/README.md 为核心系统讲解插入排序Insertion Sort的算法思想、执行流程、复杂度分析并完整给出 Python、Java、C、Go、Rust、JavaScript、C# 七种语言的仓库级实现。读完本文你将理解如何动态地向有序集合插入数据并保持有序这一核心思想掌握插入排序与冒泡排序的本质区别并能直接运行仓库中现成的多语言示例代码。从一个问题说起动态地往有序数组插入数据先看一个经典场景一个已经有序的数组我们向其中添加一个新数据后如何继续保持数据有序答案很简单从数组头部开始遍历找到新数据应当插入的位置将其插入即可。例如有序数组[1, 2, 7, 9]插入5时只需定位到2与7之间得到[1, 2, 5, 7, 9]。这是一个动态排序的过程持续向有序集合添加数据用上述插入法即可让集合一直保持有序。那么对于一组静态数据是否可以借鉴同样的思路完成整体排序这正是插入排序算法的由来。核心思想已排序区间与未排序区间插入排序的具体做法如下将数组划分为两个区间——已排序区间和未排序区间初始时已排序区间只包含数组的第一个元素单个元素天然有序其余元素全部位于未排序区间每次从未排序区间取出一个元素在已排序区间中找到合适的插入位置并插入保证已排序区间始终有序重复上述过程直到未排序区间为空整个数组有序算法结束。简单来说插入排序就是每轮取一个新元素通过插入操作把它并入已有序的前缀不断扩张有序前缀的长度。插入排序与冒泡排序的对比冒泡排序与插入排序同为 O(n²) 级别的经典排序算法但两者有序区的成长方向恰好相反冒泡排序经过每一轮排序处理后数组后端末尾的数是有序的——大元素像气泡一样逐步上浮到尾部插入排序经过每一轮排序处理后数组前端开头的数是有序的——新元素被逐个插入到有序前缀中。这一差异决定了插入排序在近乎有序的输入上往往表现更优见下文复杂度分析也是工程实践中常将插入排序用作快排等高级算法收尾步骤的原因。逐步执行演示以数组[10, 17, 50, 7, 30]为例观察插入排序每一轮的状态|左侧为已排序区间轮次取出元素操作数组状态初始——[10] \| [17, 50, 7, 30]i11717 10原地不动[10, 17] \| [50, 7, 30]i25050 17原地不动[10, 17, 50] \| [7, 30]i37与 50、17、10 依次比较插入头部[7, 10, 17, 50] \| [30]i430与 50 比较后插入 17 与 50 之间[7, 10, 17, 30, 50]可以看到每一轮结束后前端的有序区间长度都增加 1直至整个数组有序。复杂度与稳定性分析从算法结构可以直接推导出以下结论标准算法分析非仓库声称数据时间复杂度最好情况输入已有序每轮只需比较一次即完成插入时间复杂度O(n)最坏情况输入逆序第 i 轮需要移动 i 次总比较/移动次数约为 n²/2时间复杂度O(n²)平均情况时间复杂度O(n²)。空间复杂度所有实现均为原地排序仅使用若干临时变量空间复杂度O(1)。稳定性插入排序是稳定排序。当待插入元素与已排序区间中某个元素相等时将其插到该元素之后不会改变相等元素的相对次序。值得强调的是插入排序的最佳时间复杂度 O(n) 是其在数据基本有序场景下优于多数 O(n²) 算法如选择排序的关键——选择排序无论输入如何都需进行 O(n²) 次比较。多语言代码示例仓库在 basic/sorting/InsertionSort/ 目录下为每个语言同时提供了InsertionSort.*与Solution.*两份实现文件内容一致可直接运行验证。以下示例完整继承自原文档并标注了对应的仓库源码文件路径。Python3对应源码InsertionSort.py 与 Solution.pydef insertion_sort(array): for i in range(len(array)): cur_index i while array[cur_index - 1] array[cur_index] and cur_index - 1 0: array[cur_index], array[cur_index - 1] ( array[cur_index - 1], array[cur_index], ) cur_index - 1 return array array [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] print(insertion_sort(array))这段实现采用相邻交换式写法内层循环通过反复交换相邻元素把当前元素逐步搬运到已排序区间中的正确位置语义直观、易于理解。Java对应源码InsertionSort.java 与 Solution.javaimport java.util.Arrays; public class InsertionSort { private static void insertionSort(int[] nums) { for (int i 1, j, n nums.length; i n; i) { int num nums[i]; for (j i - 1; j 0 nums[j] num; --j) { nums[j 1] nums[j]; } nums[j 1] num; } } public static void main(String[] args) { int[] nums {1, 2, 7, 9, 5, 8}; insertionSort(nums); System.out.println(Arrays.toString(nums)); } }这是经典的平移插入式写法先用num保存当前元素随后把大于num的已排序元素统一向右平移一位nums[j 1] nums[j]最后将num放入腾出的空位nums[j 1]。相比相邻交换平移式写法减少了交换开销是插入排序最常见的工程实现。C对应源码InsertionSort.cpp 与 Solution.cpp#include iostream #include vector using namespace std; void printvec(const vectorint vec, const string strbegin , const string strend ) { cout strbegin endl; for (auto val : vec) { cout val \t; } cout endl; cout strend endl; } void insertsort(vectorint vec) { for (int i 1; i vec.size(); i) { int j i - 1; int num vec[i]; for (; j 0 vec[j] num; j--) { vec[j 1] vec[j]; } vec[j 1] num; } return; } int main() { vectorint vec {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; printvec(vec); insertsort(vec); printvec(vec, after insert sort); return (0); }该示例特意选用完全逆序的{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}作为输入用于展示插入排序在最坏情况下的执行过程并借助printvec输出排序前后的数组。Go对应源码InsertionSort.go 与 Solution.gopackage main import fmt func insertionSort(nums []int) { for i, n : 1, len(nums); i n; i { j, num : i-1, nums[i] for ; j 0 nums[j] num; j-- { nums[j1] nums[j] } nums[j1] num } } func main() { nums : []int{1, 2, 7, 9, 5, 8} insertionSort(nums) fmt.Println(nums) }Go 版本与 Java 版结构完全一致外层循环从第二个元素开始内层循环将大于num的元素右移最终在nums[j1]处落位。Rust对应源码InsertionSort.rs 与 Solution.rsfn insertion_sort(nums: mut Veci32) { let n nums.len(); for i in 1..n { let mut j i - 1; let temp nums[i]; while j (0 as usize) nums[j] temp { nums[j 1] nums[j]; j - 1; } nums[j 1] temp; } } fn main() { let mut nums vec![1, 2, 7, 9, 5, 8]; insertion_sort(mut nums); println!({:?}, nums); }Rust 版本以mut Veci32形式原地修改数组并通过j (0 as usize)处理usize下界判断避免索引下溢体现了 Rust 在索引边界上的严谨性。JavaScript对应源码InsertionSort.js 与 Solution.jsfunction insertionSort(inputArr) { let len inputArr.length; for (let i 1; i len - 1; i) { let temp inputArr[i]; let j i - 1; while (j 0 inputArr[j] temp) { inputArr[j 1] inputArr[j]; j--; } inputArr[j 1] temp; } return inputArr; } let arr [6, 3, 2, 1, 5]; console.log(insertionSort(arr));C#对应源码InsertionSort.cs 与 Solution.csusing System.Diagnostics; using static System.Console; namespace Pro; public class Program { public static void Main() { int[] test new int[] { 31, 12, 10, 5, 6, 7, 8, 10, 23, 34, 56, 43, 32, 21 }; InsertSortNums(test); foreach (var item in test) { WriteLine(item); } } public static void InsertSortNums(int[] nums) { for (int initial 1; initial nums.Length; initial) { for (int second_sort 0; second_sort initial; second_sort) { if (nums[second_sort] nums[initial]) { swap(ref nums[second_sort], ref nums[initial]); } } } } private static void swap(ref int compare_left, ref int compare_right) { int temp compare_left; compare_left compare_right; compare_right temp; } }C# 版本实现风格有所不同内层循环从已排序区间头部开始一旦发现某个元素大于当前待插入元素立即通过swap交换两者。虽然每次交换只前进一位、效率略低于平移式写法但代码更接近插入的语义可读性更强适合作为教学示例。注意该示例数组含重复元素10排序后仍能保持相对次序可作为验证插入排序稳定性的直观用例。两种实现风格的辨析综合上述七种语言实现可以归纳出插入排序的两类编码风格平移插入式Java / C / Go / Rust / JavaScript先暂存当前元素num将已排序区间中所有大于num的元素右移一位最后一次性把num写入空位。该方式移动次数与比较次数相当性能更优。相邻交换式Python / C#通过反复交换相邻元素把当前元素逐步挤到正确位置。该方式每一步都保持了数组其他元素的相对位置代码直观但交换操作比单纯的赋值更昂贵。从仓库源码结构看各语言的InsertionSort.*与Solution.*文件内容一致均以可直接运行的完整程序含main与示例数据形式提供便于读者逐个语言对照学习。优化思路在实际工程中插入排序常配合以下优化手段提前终止若内层循环中发现待插入元素已经大于等于已排序区间末尾元素则本轮无需任何移动直接进入下一轮。这是输入近乎有序时达到 O(n)的实现基础。二分插入排序由于已排序区间本身有序可以使用二分查找定位插入位置将比较次数从 O(n) 降为 O(log n)但元素平移次数仍为 O(n)因此总体时间复杂度不变仅常数因子改善。作为高级排序的收尾插入排序在小规模或近似有序数据上常数因子极小常被用作快速排序、希尔排序在递归到小数组时的收尾算法希尔排序本质上是插入排序的分组跳跃版本仓库中的 ShellSort 目录即是对应的多语言实现。适用场景小结插入排序适合以下场景数据规模较小如 n ≤ 几十输入数据基本有序此时时间复杂度逼近 O(n)需要稳定排序且要求原地、O(1) 额外空间作为其他排序算法的底层子过程。若需进一步对比学习仓库 basic/sorting/ 下还提供了冒泡排序BubbleSort、选择排序SelectionSort、归并排序MergeSort、快速排序QuickSort、堆排序HeapSort、希尔排序ShellSort、计数排序CountingSort等多语言实现可作为算法复杂度横向对比的参考资料基础算法总览可参见 basic/README.md。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode-Go 题解147. Insertion Sort List链表插入排序LeetCode Go 题解147. Insertion Sort List链表插入排序 导读 本文讲解 LeetCode 第 147 题「Inserti示例工程AlgoNote 数组插入排序Insertion Sort详解思想、步骤、代码与复杂度分析AlgoNote 数组插入排序Insertion Sort详解思想、步骤、代码与复杂度分析 导读 本文是《算法通关手册》AlgoNote 仓库「数组排序教程文档知识库LeetCode-Go 题解147. Insertion Sort List 链表的插入排序实现与源码解析LeetCode Go 题解147. Insertion Sort List 链表的插入排序实现与源码解析 导读 本文以 LeetCode 第 147 题「I示例工程上一篇KotlinMvp数据层设计构建可扩展的Model层架构下一篇OpenNews MCP核心功能解析新闻聚合、AI评级与交易信号全攻略创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考