数据结构希尔排序

淡淡的烟草味﹌ 2022-06-06 04:39 198阅读 0赞

##     ##

### Ⅰ）算法思想 ###

希尔排序的算法思想：先将待排序列分割成若干个“较稀疏的”子序列，分别进行直接插入排序。经上述粗略调整，整个记录中的序列已经基本有序，最后再对全部序列进行一次直接插入排序

1) 选定记录间的距离为d1在整个待排序记录序列中将所有间隔为d1的记录分成一组，进行组内直接插入排序；

2) 取记录间的距离为d2(d2<d1)，在整个待排序记录序列中，将所有间隔为d2的记录分成一组，进行组内直接插入排序；

3) 重复步骤2，直至记录间的距离d=1，此时整个只有一个子序列，对该序列进行直接插入排序，完成整个排序过程。

## **Ⅱ）源代码** ##

#include<stdio.h>   typedef struct {
           int key; }RecordType;   void ShellInsert(RecordType r[], int length, int delta)  //Shell插入，其中delta 为增量 {
           int i, j;     for ( i = 1 + delta; i <= length; i++)     {
               if (r[i].key < r[i - delta].key)         {
                   r[0] = r[i];          //备份r[i](不做监视哨)             for ( j = i - delta; j > 0 && r[j].key >r[0].key; j-=delta)             {
                       r[j + delta] = r[j];             }             r[j + delta] = r[0];         }     } }   void ShellSort(RecordType r[], int length, int delta[], int n)//希尔排序,delta为增量数组，n为增量数组长度 {
           for (int i = 0; i < n; i++)     {
               ShellInsert(r, length, delta[i]);     } }   int main(void) {
           RecordType a[] = { 0, 9, 7, 3, 8, 5, 4, 1,2, 6, 0 };     int length = sizeof(a) / sizeof(a[0])-1;     int d[] = { 5, 2, 1 };              //d为增量数组     ShellSort(a, length, d, 3);     for (int i = 1; i <= length; i++)    //输出结果     {
               printf("%d\t", a[i]);     }         printf("\n");     return 0; }

## **Ⅲ）增量的选取** ##

关于增量d的选取，最初希尔（shell）提出取d=n/2 向下取整，再取d=n/2 向下取整，直到d=1为止。该思路的缺点是，奇数位置的元素在最后一步才会与偶数位置的元素进行比较，使得希尔排序效率降低。因此后来Knuth 提出d=d/3 向下取整结果加1。此外，还有多种取法，但均没有给出最最优性证明。在上面的程序中对0-9 10个数字进行排序，使用的是希尔提出的增量选取方法，取的增量值分别为5,2,1 。