文章目录
- 1.插入排序的思想
- 2.插入排序的三步曲
- 3.直接插入排序
- 4.插入排序的本质
1.插入排序的思想
- 基本思想： 将无序子序列中的一个或几个记录“插入”到有序子序列中，从而增加有序子序列的长度。
2.插入排序的三步曲
- 不同的定位方法导致不同的插入算法
（1）直接插入排序（基于顺序查找定位）
（2）折半插入排序（基于折半查找定位）
（3）希尔排序（基于逐趟缩小增量）
3.直接插入排序
- 排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序
- eg：插入排序理解的精华主要是在后面
- 算法描述
typedef struct
{
int key;
float info;
}JD;
//元素个数n，待排序的记录的首地址
void strausort(JD r[], int n)//对长度为n的序列排序
{
int i,j;
for (i=2;i<=n;i++)//将第1个位置当作有序序列，i表示待排序的数组下标
{
r[0]=r[i];//第0个位置作为岗哨
j=i-1;//有序序列的下标的最后一个元素位置
/*
j指针指向的关键字比岗哨关键字要大，就将j指针所指的关键字向后移动
*/
while (r[j].key > r[0].key)
{
r[j+1]=r[j];
j--;
}
r[j+1]=r[0];
}
}
//若不采用岗哨写法
void strausort(JD r[], int n)
{
int i,j;
for (i=2;i<=n;i++)
{
t=r[i];
j=i-1;//下标的最后一个元素位置
while (r[j].key > r[0].key && j>=1)
{
r[j+1]=r[j];
j--;
}
r[j+1]=r[0];
}
}
- 算法时间复杂度
（1）空间复杂度
空间复杂度： S(n)=O(1)
（2）时间复杂度 - eg：顺序比较n-1次数，逆序需要比较
次数。所以又是顺序，又是有序，比较次数肯定越少
4.插入排序的本质
- 比较和交换(确定位置后，将其拷贝过去，将其看成是交换操作)
- 序列中逆序的个数决定交换次数，所以平均逆序数量为 C(n,2)/2（随便取两个元素，然后取平均）,所以T(n)=
- 简单插入排序复杂度由什么决定?
逆序个数 - 如何改进简单插入排序复杂度?
（1）分组，比如C(n,2)/2>2C((n/2),2)/2 (就算乘以2，也比前面小)
（2）3,2,1有3组逆序对(3,1)（3,2） (2,1)需要交换3次。但相隔较远的3,1交换一次后1,2,3就没有逆序对了。
相隔较远的数据分到一组，每组使用简单插入排序后，这样整体上，小数据在前，大的在后
（3）对所有数据排序后，基本有序的插入排序算法复杂度接近O(n)