19-插入排序与希尔排序

C语言数据结构系列（十九）：插入排序与希尔排序

🎯本篇目标：掌握插入排序和希尔排序！
📝摘要：本文介绍两种经典的排序算法——插入排序与希尔排序。插入排序通过将新元素插入到已排序序列的正确位置完成排序，思想类似打扑克牌；希尔排序则是插入排序的改进版，通过分组、逐步缩小间隔的方式提升效率。文章包含两种算法的 C 语言实现、思想讲解及复杂度对比，适合初学者快速掌握。

一、前言

哈喽小伙伴们！👋

今天我们来学习插入排序和它的改进版希尔排序！

二、插入排序

2.1 思想

💡 像打扑克牌，每次摸到新牌，插入到手牌的正确位置

2.2 代码实现

voidinsertionSort(intarr[],intn){for(inti=1;i<n;i++){intkey=arr[i];intj=i-1;while(j>=0&&arr[j]>key){arr[j+1]=arr[j];j--;}arr[j+1]=key;}}

三、希尔排序

3.1 思想

💡分组插入排序，逐步缩小间隔，最后进行一次插入排序

3.2 代码实现

voidshellSort(intarr[],intn){for(intgap=n/2;gap>0;gap/=2){for(inti=gap;i<n;i++){inttemp=arr[i];intj;for(j=i;j>=gap&&arr[j-gap]>temp;j-=gap){arr[j]=arr[j-gap];}arr[j]=temp;}}}

四、复杂度对比

五、下篇预告

下一篇我们将学习快速排序——最常用的排序算法！

💡 插入排序在数据基本有序时效率很高！👍