直接插入排序算法简单、容易实现,只需要一个 记录大小的辅助空间用于存放待插入的记录(在C语 言中,我们利用了数组中的0单元)和两个int型变量。 当待排序记录较少时,排序速度较快,但是,当待排 序的记录数量较大时,大量的比较和移动操作将使直 接插入排序算法的效率降低;然而,当待排序的数据 元素基本有序时,直接插入排序过程中的移动次数大 大减少,从而效率会有所提高。 插入排序是一种稳定的排序方法。 请单赤鼠标左键换页!
直接插入排序算法简单、容易实现，只需要一个 记录大小的辅助空间用于存放待插入的记录（在C语 言中，我们利用了数组中的0单元）和两个int型变量。 当待排序记录较少时，排序速度较快，但是，当待排 序的记录数量较大时，大量的比较和移动操作将使直 接插入排序算法的效率降低；然而，当待排序的数据 元素基本有序时，直接插入排序过程中的移动次数大 大减少，从而效率会有所提高。 插入排序是一种稳定的排序方法
822希尔排序 1.希尔排序的基本思想 希尔排序方法又称为缩小增量排序,其基本思想 是将待排序的记录划分成几组,从而减少参与直接插 入排序的数据量,当经过几次分组排序后,记录的排 列已经基本有序,这个时候再对所有的记录实施直接 插入排序。 请单鼠标左键换页!
8.2.2 希尔排序 1. 希尔排序的基本思想 希尔排序方法又称为缩小增量排序，其基本思想 是将待排序的记录划分成几组，从而减少参与直接插 入排序的数据量，当经过几次分组排序后，记录的排 列已经基本有序，这个时候再对所有的记录实施直接 插入排序
具体步骤可以描述如下:假设待排序的记录为n个 先取整数d<n,例如,取d=n/2(n2表示不大于n/2的 最大整数),将所有距离为d的记录构成一组,从而将 整个待排序记录序列分割成为d个子序列,如图8-2所 示,对每个分组分别进行直接插入排序,然后再缩小 间隔d,例如,取d=d/2,重复上述的分组,再对每个 分组分别进行直接插入排序,直到最后取d=1,即将所 有记录放在一组进行一次直接插入排序,最终将所有 记录重新排列成按关键字有序的序列 请单赤鼠标左键换页!
具体步骤可以描述如下：假设待排序的记录为n个， 先取整数d<n，例如，取d=n/2（n/2 表示不大于n/2的 最大整数），将所有距离为d的记录构成一组，从而将 整个待排序记录序列分割成为d个子序列，如图8-2所 示，对每个分组分别进行直接插入排序，然后再缩小 间隔d，例如，取d=d/2，重复上述的分组，再对每个 分组分别进行直接插入排序，直到最后取d=1，即将所 有记录放在一组进行一次直接插入排序，最终将所有 记录重新排列成按关键字有序的序列
3.希尔排序算法 (1)分别让每个记录参与相应分组中的排序 若分为d组,前d个记录就应该分别构成由一个记 录组成的有序段,从d+1个记录开始,逐一将每个记录 a[插入到相应组中的有序段中,其算法可以这样实现: for(i=d+l; i<=n; i++) 将a(插入到相应组的有序段中; 请单赤鼠标左键换页!
3. 希尔排序算法 (1) 分别让每个记录参与相应分组中的排序 若分为d组，前d个记录就应该分别构成由一个记 录组成的有序段，从d+1个记录开始，逐一将每个记录 a[i]插入到相应组中的有序段中，其算法可以这样实现： for (i=d+1; i<=n; i++) { 将a[i]插入到相应组的有序段中； }
(2)将a插入到相应组的有序段中的操作可以这 样实现: 将叫赋予a中,即a|0=ai; 让指向ai属组的有序序列中最后一个记录 ●搜索a[的插入位置 while(j>0 & alo key<alj. key) [+d=a[j: j=j-d 请单鼠标左键换页!
(2) 将a[i]插入到相应组的有序段中的操作可以这 样实现： ⚫ 将a[i]赋予a[0]中，即a[0]=a[i]; ⚫ 让j指向a[i]所属组的有序序列中最后一个记录 ⚫ 搜索a[i]的插入位置 while(j>0 && a[0].key<a[j].key) { a[j+d]=a[j]; j=j-d; }