|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
假设含n个记录的文件内容为｛R1，R2，…，Rn｝，其相应的关键字为｛k1，k2，…，kn｝。经过排序确定一种排列｛Rj1，Rj2，…，Rjn｝，使得它们的关键字满足如下递增（或递减）关系：kj1≤kj2≤…≤kjn（或kj1≥kj2≥…≥kjn）。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
希尔排序又称“缩小增量排序”，是对直接插入排序方法的改进。
|
|
|
|
希尔排序的基本思想是：先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。具体做法是：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1组，将所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d2（d2<d1），重复上述的分组和直接插入排序过程，依此类推，直至所取的增量di=1（di<di-1<…d2<d1），即所有记录放在同一组进行直接插入排序为止。
|
|
|
|
增量序列为5，3，1时，希尔插入排序过程如下图所示。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
直接插入排序是一种简单的排序方法，具体做法是：在插入第i个记录时，R1，R2，…，Ri-1己经排好序，这时将记录Ri的关键字ki依次与关键字ki-1，ki-2，…，k1进行比较，从而找到Ri应该插入的位置，插入位置及其后的记录依次向后移动。
|
|
|
|
|
|
|
直接插入排序法在最好情况下（待排序列已按关键码有序），每趟排序只需作1次比较且不需要移动元素，因此n个元素排序时的总比较次数为n-1次，总移动次数为0次。在最坏情况下（元素已经逆序排列），进行第i趟排序时，待插入的记录需要同前面的i个记录都进行1次比较，因此，总比较次数为 。排序过程中，第i趟排序时移动记录的次数为i+1（包括移进、移出temp），总移动次数为 。
|
|
|
|
由此，直接插入排序是一种稳定的排序方法，其时间复杂度为O（n2）。排序过程中仅需要一个元素的辅助空间，空间复杂度为O（1）。
|
|
|
|
|
|
|
|
|
|
|
|
|
