C语言数据结构系列插入排序篇C语言数据结构系列十九插入排序与希尔排序一、前言二、插入排序2.1 思想2.2 代码实现三、希尔排序3.1 思想3.2 代码实现四、复杂度对比五、下篇预告C语言数据结构系列十九插入排序与希尔排序本篇目标掌握插入排序和希尔排序摘要本文介绍两种经典的排序算法——插入排序与希尔排序。插入排序通过将新元素插入到已排序序列的正确位置完成排序思想类似打扑克牌希尔排序则是插入排序的改进版通过分组、逐步缩小间隔的方式提升效率。文章包含两种算法的 C 语言实现、思想讲解及复杂度对比适合初学者快速掌握。一、前言哈喽小伙伴们今天我们来学习插入排序和它的改进版希尔排序二、插入排序2.1 思想 像打扑克牌每次摸到新牌插入到手牌的正确位置2.2 代码实现voidinsertionSort(intarr[],intn){for(inti1;in;i){intkeyarr[i];intji-1;while(j0arr[j]key){arr[j1]arr[j];j--;}arr[j1]key;}}三、希尔排序3.1 思想分组插入排序逐步缩小间隔最后进行一次插入排序3.2 代码实现voidshellSort(intarr[],intn){for(intgapn/2;gap0;gap/2){for(intigap;in;i){inttemparr[i];intj;for(ji;jgaparr[j-gap]temp;j-gap){arr[j]arr[j-gap];}arr[j]temp;}}}四、复杂度对比算法最好最坏平均稳定性插入O(n)O(n²)O(n²)✅希尔O(nlogn)O(n²)O(n^1.3)❌五、下篇预告下一篇我们将学习快速排序——最常用的排序算法 插入排序在数据基本有序时效率很高