Shell（希尔）排序
对于直接插入排序而言，如果一个很小的数据单元位于很靠近右端的位置上，为了把这个数据单元移动到左边正确的位置上，中间所有的数据单元都需要向右移动一格。这个步骤对每一个数据项都执行了近n次复制。虽然不是所有的数据项都必须移动n个位置，但平均下来，每个数据项都会移动n/2格，总共是n*n/2次复制。因此，直接插入排序的执行效率是O（n^2）[注：这里是n的平方]。
Shell排序对直接插入排序进行了简单的改进：它通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项大跨度地移动，当这些数据项经过一趟排序之后。Shell排序算法减少数据项的间隔再进行排序，依次进行下去。这些进行排序的数据项之间的间隔被称为增量，习惯上用h来表示这个增量，并且满足以下公式 ：
h = 3*h+1反过来 h = （h-1）/3
当h值很大的时候，数据项每一趟排序需要移动元素的个数非常少，但数据项移动的距离非常长，这是非常有效率的。当h减少时，每一趟排序需要移动的元素个数增多，但此时数据项已经接近于它们排序后最终的位置，这对于插入排序可以更有效率。（直接使用增量为1的Shell排序就是直接插入排序）
Shell排序的实现
1 /** 2 * Shell(希尔)排序 3 * @param data 待排序数组 4 */ 5 public static void shellSort(int[] data){ 6 //先求增量 7 int h = 1; 8 //按 3*h+1 得到最大的增量 9 while(h <= data.length/3){ 10 h = 3*h+1; 11 } 12 while(h > 0){ 13 for(int i = h; i<data.length; i++){ 14 //i索引处的值已经比前面的所有值都大，表明已经有序，无序插入 15 //(i-h 索引之前的数据已经有序，i-h索引处的元素的值就是最大值) 16 if(data[i-h] > data[i]){ 17 //当数据整体后移时，保证data[i]处的元素不丢失 18 int temp = data[i]; 19 //最多后移多少个元素 20 int j = i-h; 21 //循环判断，只要前面的元素比data[i]大，则需要后移,注意这里是j-=h而不是j-- 22 for(;j>=0 && data[j] > temp; j-=h){ 23 data[j+h] = data[j]; 24 } 25 //最后将temp插入到合适的位置 26 data[j+h] = temp; 27 } 28 } 29 //依据增量公式，计算下一个增量 30 h = (h-1)/3; 31 } 32 }
测试代码
算法分析
（1）时间复杂度：O（n^3/2）~O（n^7/6）
（2）空间复杂度:：O（1）
（3）Shell排序是不稳定的
（4）只能用于顺序结构，不能用于链式结构
（5）记录总的比较次数和移动次数都比直接插入排序要少，n越大时，效果越明显。所以适合初始记录无序，n较大时的情况。