时间复杂度：O(n^3/2) （以2^k-1增量串为例） ；空间复杂度：O(1)； 稳定性：不稳定。
基本思想：先将整个待排序的序列按一定增量分割成为若干子序列分别进行直接插入排序，然后依次缩小增量再排序。当整个序列“基本有序”时（增量足够小时），再对全体记录进行一次直接插入排序。
下面分析一次完整希尔排序过程。 以n=10的数组，49 38 65 97 76 13 27 49. 55 4为例。
第一次:gap = 5 初始： 49 38 65 97 76 13 27 49. 55 4 A1 A2 B1 B2 C1 C2 D1 D2 E1 E2 第一次则分为了五组，(49,13),(38,27),(65,49.),(97,55),(76,4)，分别对每一组进行直接插入排序，则得到(13,49),(27,38),(49.,65),(97,55),(76,4)。下面类似。
第二次：gap = 3 第一趟结果： 13 27 49. 55 4 49 38 65 97 76 A1 A2 A3 A4 B1 B2 B3 C1 C2 C3
最终第三趟结果： 4 13 27 38 49. 49 55 65 76 97
从前两趟可以看出，数据小的记录不是一步一步的向前移动，而是跳跃式的向前移动。到了第二趟结束，整个序列也基本有序了，只要作记录的少量比较和移动即可完成排序。
下面列出希尔排序完整算法：
//基本与直接插入排序相同，只是增量为gap而不为1
void ShellInsert(int arr[], int gap, int n)
{
int i,j,temp;
for(i = gap; i
=0&&(temp < arr[j]); j-=gap)
{
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
}
//gap[]为增量序列，数组arr按gap[0...t-1]进行希尔排序
void ShellSort(int arr[],int n, int gap[], int t)
{
int k;
for(k = 0; k < t; k++)
{
ShellInsert(arr,gap[k],n);
}
}
这里的希尔排序用的增量序列为{5,3,1}，希尔排序的时间是所取“增量”序列的函数，这涉及一些数学上的难题。有兴趣的朋友可以参考维基百科对于希尔排序增量（步长串）的描述： http://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F