希尔排序（Shell’s Sort）又称“缩小增量排序”，它也是一种属插入排序类的方法，但在时间效率上较几种排序方法有较大的改进。
基本思想： 先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，在对全体记录进行一次直接插入排序
例如，待排序的一组记录的初始排列 49 38 65 97 76 13 27 49，其排序过程如下图所示：
由此可见希尔排序一个特点是：子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。
具体算法：
public class TestTureOrFalse { public static void main(String[] args) { int arr[] = {9,5,8,7,4,6,3,2,1}; sort(arr,arr.length); for (int i=0 ; i<arr.length ;i++) System.out.print(arr[i]+" "); System.out.println(); } public static void sort(int[] arr, int length) { int m = length/2; while (m>=1){ shellsort(arr,length,m); m = m/2; } } //对数组进行间隔为m的插入排序 public static void shellsort(int[] arr, int length, int m) { for (int i=m ; i<length ;i++){ if (arr[i]<arr[i-m]){ int j ; int temp =arr[i]; for (j=i-m ;j>=0&&arr[j]>temp; j-=m){ arr[j+m] = arr[j]; } arr[j+m] = temp ; } //输出每次排序的结果 sout(arr, length, i); } } public static void sout(int arr[],int n,int i){ System.out.print("角标"+i+": "); for (int j=0 ; j<arr.length ;j++) System.out.print(arr[j]+" "); System.out.println(); } }或者将增量和插入弄到一个方法里面：
#include <stdio.h> #include <stdlib.h> //输出每次排序结果 void sout(int num[] ,int n ,int i) { printf(" %d : ",i); int j ; for (j=0 ; j<n ; j++) printf("%d ",num[j]); printf("\n"); } void shellSort2(int num[] , int n ) { int i ,d; for (d=n/2 ; d>=1 ;d/=2) { for (i=d ; i<n ;i++) { if (num[i]<num[i-d]) { int temp = num[i]; int j ; for (j=i-d ; num[j]>temp&&j>=0 ; j-=d) { num[j+d] = num[j]; } num[j+d] = temp ; } sout(num,n,i); } } } int main(void) { int a[9] = {9,5,8,7,4,6,3,2,1}; int i; //time(a,8); shellSort2(a,9); for (i=0 ; i<9 ; i++) { printf("%d ",a[i]); } return 0; }增量因子序列可以有各种取法，有取奇数的，也有取质数的，取增量序列时应该注意：增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1.
