希尔排序

浏览数：64 / 时间：2015年06月08日

希尔排序算法

　　一、基本思想：分组增量插入方法，先取定一个小于 n 的整数 d₁ 作为第一个增量，把表的全部记录分成 d₁ 个组，所有间距为 d₁ 的倍数的记录放置在同一个组，再在各组内进行直接插入排序，依次类推，直至所取的增量 d_i=1，即将所有的记录都放置在同一个组中进行直接插入排序为止。

　　技术分享

　　二、C 语言代码：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 //取 d_i = n/2, d_i+1 = d_i/2
 5 void shellSort(SqList R[], int n)
 6 {
 7     int i; 
 8     int j; 
 9     int gap; 
10     SqList tmp; 
11     gap = n/2; //为增量设置初值 
12     
13     //对所有相隔 gap 位置的所有元素组采用直接插入排序 
14     while (gap > 0) { 
15         for (i = gap; i < n; i++) { 
16             tmp = R[i]; 
17             j = i - gap; 
18             while (j >= 0 && tmp.key < R[j].key) { 
19                 R[j+gap] = R[j]; 
20                 j = j - gap; 
21             } 
22             R[j+gap] = tmp; 
23         } 
24         gap = gap/2; //减少增量 
25     } 
26 }