9.2 插入排序

南山隐士 2022年07月31日 39 0

结合实例理解插入排序的基本思想和步骤,能针对给定的输入实例写出直接插入排序的排序过程,能够计算出为寻找插入位置需比较的次数。

1.直接插入排序

(1)直接插入排序的基本思想

直接插入排序(Straight Insertion Sort)算法是一种常用且简单直观的方法。它的基本思想是:设有n个数据的待排序序列,假设前面1到i-1个数据已经有序,是长度为i-1的有序序列,将第i个数据逐次与第i-1个数据、第i-2个数据……进行比较,直到找到第i个数据的插入位置,并插入得到一个新的长度为i的有序数列。这一过程称为一趟插入,对第i个元素的插入称为第i趟插入。

(2)直接插入排序的步骤

首先令i=1,取第一个元素,得到长度为1的序列,再令i=2,完成对第二个数据的第二趟插入,得到长度为2的有序序列,以下逐次令i=3,4,…,直到完成对第n个元素的第n趟插入,得到长度为n的有序序列。

例如一组待排序的数据记录的关键字为:47,83,41,53,68,经5趟插入完成排序的过程如下:

取第一个元素 47

第二趟    47 83

第三趟    41 47 83

第四趟    41 47 53 83

第五趟    41 47 53 68 83

(3)直接插入排序的算法实现

【算法9-1】 直接插入排序算法

void disort(NODE a[],int n)

/对存放在a[0],a[1],...a[n-1]中,长度为n的序列进行排序/

{

int i,j;

NODE temp;

for(i=1;i

{

temp=a[i];      /*把a[i]暂时保存*/

j=i-1;        /*从a[i]前边的第一个元素开始比较*/

while(j>=0&&temp.key

{

  a[j+1]=a[j];  /*边比较边后移*/

  j-- ;       /*向前边再取一个元素比较*/

}

a[j+1]=temp;    /*第i号元素插入到位*/

}

}

(4)直接插入排序的算法分析

最好情况:待排序记录已有序

例:1 2 3 4 5 … n,每个元素的插入进行一次比较,所以进行了(n-1)次比较。

最坏情况:待排序记录已反向有序,第 i 个元素的插入进行(i-1)次比较

例:5 4 3 2 1,,时间复杂度为O(n2)。

想一想:直接插入排序使用监视哨的作用是什么?

解题分析:

减少比较次数,提高查找效率。

2.折半插入排序

(1)折半插入排序的基本思想

折半插入排序(Binary Insertion Sort)是直接插入排序的改进。在直接插入排序中,在寻找插入位置时,对已排好序的子序列从后向前通过顺序比较查找插入位置,当n很小时是较实用的方法。当n较大时,数据间的比较次数较多,效率不高。折半插入排序法在寻找插入位置的方法上进行了改进。其基本思想是对已排好序的有序子表,利用折半查找法寻找插入位置,以减少每一趟插入过程中数据间的比较次数。

(2)折半插入排序的步骤

设待排序的序列已存放在数组元素a[1]- a[n]中,以a[0]作为辅助工作单元。以下要把a[i]插入到已经有序的序列a[1]- a[i-1]之中,一趟折半插入排序的步骤如下:

1.设定折半查找的区间

a[0]= a[i]; /保存a[i]/

s=1;j= i-1; /设定折半查找的区间的起、止下标/

2.利用折半查找法求插入位置

当s<=j do

{

 m←∟(s+j)/2」;               /*求区间中点坐标*/

 如果a[0]

 j=m-1;                     /*取前半区间*/

 否则s=m+1;                  /*取后半区间*/

}

3.将所找到的插入位置的元素及其后面的元素逐次后移一个位置

4.将a[0]插入

(3)折半插入排序的算法实现

【算法9-2】 折半插入排序算法

/对存放在a[1],a[2],…,a[n]中的序列进行折半插入排序/

void binsort(NODE a[],int n)

{

int x,i,j,s,k,m;

for(i=2;i<=n;i++)

{

a[0]=a[i];           /*保存待插入的第i号记录*/

x=a[i].key;          /*待插入记录的关键字*/

s=1;               /*区间的起始下标*/

j=i-1 ;             /*区间的终点下标*/

while(s<=j)           /*当始点下标大于终点下标时结束循环*/

{

  m=(s+j)/2;

  if(x

    j=m-1 ;          /*取前半区间*/

  else

    s=m+1;           /*取后半区间*/

}

for(k=i-1;k>=j+1;k--)

  a[k+1]=a[k];       /*记录逐次后移,为插入记录留出空间*/

a[j+1]=a[0];           /*把第i个记录插入*/

}

}

例如:一组记录序列的关键字为1,3,5,7,8,4。前面5个有序,现要把第6个关键字插入,插入过程如下:

图 一趟折半插入过程

折半插入排序改进了直接插入排序算法中查找插入位置的方法,减少了关键字间的比较次数,但记录的移动次数并没有得到改善。在数据量较大时,所用时间能有所减少,但时间复杂度为O(n2)。按上述方法,折半插入排序算法是稳定的。

想一想:直接插入排序与折半插入排序有何联系?

解题分析:

折半插入排序是直接插入排序的改进,直接插入排序是指每次将一个元素插入到已经排好序的序列中,直到结束为止。排序效率较低。

Last Updated: 2022/07/31 23:25:50
9.3 交换排序 9.1 排序的基本概念