插入排序（C语言）

文章目录

• 插入排序
• • 定义
  • 直接插入排序
  • • 代码实现
  • 折半插入排序
  • 2-路插入排序
  • 希尔排序
  • • 代码实现

插入排序

定义

插入排序是一种简单直观的稳定排序算法，其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中

类似于我们打扑克牌时整理手牌的过程。

直接插入排序

直接插入排序：将待排序的数组，分成两个序列，前面的序列保持有序，依次选择后面的元素，往前面插入。（就地排序、稳定排序） 根据数据量进行一个划分，C++的STL当数据少了就用插入排序（<=8个）

代码实现

#include<stdio.h>
#include<stdlib.h>
int n,a[105];
//直接插入排序：就地排序 稳定排序 内部排序 O(n^2)
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}

int t,j;
for(int i=1;i<n;i++)//枚举趟数
{
//有序区是[1,i]. 乱序区[i+1,n]
//把a[i+1]插入到有序区中
t=a[i+1];
//边找位置边移动
for(j=i;j>=1;j—)
{
if(a[j]>t)
{
a[j+1]=a[j];
}
else
{
break;
}
}
a[j+1]=t;

}
/*
for(int i=1;i<n;i++)//枚举趟数
{//有序区是[1,i]. 乱序区[i+1,n]
//把a[i+1]插入到有序区中
t=a[i+1];
//有序区中倒着枚举找到第一个小于等于t位置 j

for(j=i;j>=1;j–)
{
if(a[j]<=t)
{
break;
}
}
//j+1 就是t应该中的位置
for(int k=i;k>=j+1;k–)
{
a[k+1]=a[k];
}
a[j+1]=t;

}
*/
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
printf("\\n");

}

折半插入排序

而在查找表中数据本身有序的前提下，可以使用折半查找来代替顺序查找，这种排序的算法就是折半插入排序算法。

2-路插入排序

2-路插入排序是折半插入排序的改进，通过在环形数组中同时从两端进行插入，减少元素移动次数，从而提高排序效率。

希尔排序

又称“缩小增量排序”，也是插入排序的一种，但是同前面几种排序算法比较来看，希尔排序在时间效率上有很大的改进。

它的核心思想是通过允许间隔较远的元素进行交换，使数组快速达到“基本有序”的状态，从而减少后续插入排序的工作量。

代码实现

j 是内层循环的控制变量，用于：

#include<stdio.h>
#include<stdlib.h>
int n,a[105];
//希尔排序：就地排序 不稳定排序 内部排序 普通情况下时间复杂度小于n^2 最坏情况下是n^2
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int k=0;//趟数
for(int d=n/2;d>=1;d=d/2)//枚举增量（分组的组数）
{
k++;
for(int i=1+d;i<=n;i++)
{
//i就是某一组的要排序的一个数
//i所在的这一组的有序区：i-d i-2d i-3d…
int t=a[i];
int j;
for(j=i–d;j>0;j-=d)
{
if(a[j]>t)
{
a[j+d]=a[j];
}
else
{
break;
}
}
a[j+d]=t;

}
printf("第%d趟的排序结果: ",k);
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
printf("\\n");
}

}