（2.7）简单插入排序

文章目录

• ​​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  {
    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  {
    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)

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net