（2.7）简单插入排序

本文主要是介绍（2.7）简单插入排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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次数，逆序需要比较$n^2$次数。所以又是顺序，又是有序，比较次数肯定越少

4.插入排序的本质

• 比较和交换(确定位置后，将其拷贝过去，将其看成是交换操作)
• 序列中逆序的个数决定交换次数，所以平均逆序数量为 C(n,2)/2（随便取两个元素，然后取平均）,所以T(n)=$O(n^2)$
• 简单插入排序复杂度由什么决定?
  逆序个数
• 如何改进简单插入排序复杂度?
  （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)

这篇关于（2.7）简单插入排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---