排序是将一串数据按照其某个或者某些关键字的大小进行递增或递减排列的操作我，通常指的排序是升序，排序方式是原地排序下面介绍下希尔排序希尔排序原理：指定一个值gap，将待排序区间分成gap个组，每个组相邻元素的下标差值是gap。将每个组元素进行排序减小gap的值，重复进行排序直到gap等于1当gap等于1的时候，数组变成有序数组实质：希尔排序是对直接插入排序的优化当gap>1时都是进行序排序，当gap=1时，数组已接近有序希尔排序是一个不稳定的排序实现方式

public void shellSort(int[] array) { int gap = array.length; while(gap > 1) { insertSortGap(array, gap); //gap的缩小方式决定了性能提升的程度 gap = gap / 3 + 1; } insertSortGap(array, 1); } private void insertSortGap(int[] array, int gap) { for(int i = 0; i < array.length; i++) { int tmp = array[i]; int j = i - gap; for(;j > 0 && array[j] > tmp; j -= gap) { array[j + gap] = array[j]; } array[j + gap] = tmp; } }性能分析时间复杂度最好情况：数组有序时时间复杂度是O(N)最快情况：时间复杂度是O(N^2)，很难构造出实例平均情况：时间复杂度是O(N^1.3)空间复杂度：O(1)稳定性：不稳定