【算法】排序04——代码简约而不简单的希尔排序（含代码实现）
1、希尔排序的效能简介
希尔排序是插入排序的改进型，也因此，它的空间复杂度是O（1）。不过有趣的是，希尔排序的平均时间复杂度计与其增量有关，算起来较为复杂，dalao们的研究认为是O[n^(1.3 ~ 2)]之间。
其实相比于快排、归并、堆排这些平均之间复杂度为O [ nlog(n) ]的线性对数阶排序，希尔排序并不占优势（因为希排有亚二次时间界），但作为第一批突破第二次时间屏障的算法之一的存在，我jio得还是要重温一下经典（其实是面试爱考ORZ）。
2、本文中的一些定义
2.1——有序区与无序区
在本文中，对于一个任意一个无序的的序列：
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ]
我们把这个序列从逻辑上分为有序区和无序区，并默认在开始排序前，第一个元素为有序区，其余为无序区。
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ] （绿色为有序区，红色为无序区）
在我们对其逐渐有序化的时候，依次从无序区中取出其第一个元素并插入有序区：
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ] （有序区会增加，无序区会减少，同时无序区第一个元素前的元素必然在有序区）
2.2——按增量（gap）划分多个序列
一个序列可以按增量（gap）在逻辑上划分为gap个序列（关于的gap的取值，第一次取序列长度一半，之后再取用gap前要除2）：
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ] gap = 9/2 = 4 ，即在逻辑上分成4组小序列，同一小序列内的、逻辑上相邻的元素，在序列中的小标差为gap：
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ] 比如红色小序列应该是[ 5, 7, 3 ],它们在原序列中的小标为0、4、8，相差为gap
3、希尔排序的流程
第一步，在逻辑上按gap将序列划分为gap个小序列。（第一次时取增量（gap）为序列长度的一半）
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ]
第二步，一个指针从序列的无序区（由各个小序列的无序区组成）由左向右遍历，遍历到的元素，将其插入对应小序列的有序区”
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ] 指针最开始指向序列无序区第一个即7，7在第一个小序列里，把它插入第一个小序列的有序区，
如， [ 5, 6, 9, 8, 7, 4, 1, 2, 3 ] 指针+1指向无序区新的第一个元素4，4在第二个小序列里， 把它插入第二个小序列的有序区，
如， [ 5, 4, 9, 8, 7, 6, 1, 2, 3 ] 注意，这里是插入到第二个小序列的有序区，所以4、6换位，然后指针+1。。。。操作同上
第三步，gap/=2后若小于1就结束了，否则回调第一步。
4、代码
1 import java.util.Arrays; 2 public class Main { 3 public static void shellSort(int[] arr) { 4 int temp; 5 //控制增量（gap），增量将不断/2直到小于1。（序列会在逻辑上按gap划分为gap个小序列） 6 for (int gap = arr.length/2; gap >0; gap/=2) { 7 //遍历无序区（最开始>=gap的下标都属于无序区） 8 //变量p_in_unorder始终指向当前序列的无序区的第一个元素的下标 9 for (int p_in_unorder = gap; p_in_unorder < arr.length; p_in_unorder++) { 10 /* 11 *p_in_order是小序列有序区内的下标指针 12 *p_in_unorder - gap 是当前小序列有序区的最后一个 13 *把当前无序区第一个元素插入对应小序列有序区 14 */ 15 for (int p_in_order = p_in_unorder-gap ; p_in_order >= 0 ; p_in_order-=gap) { 16 if(arr[p_in_order]>arr[p_in_order+gap]){ 17 temp = arr[p_in_order]; 18 arr[p_in_order] = arr[p_in_order+gap]; 19 arr[p_in_order+gap] = temp; 20 } 21 } 22 } 23 } 24 } 25 26 public static void main(String[] args) { 27 int[] arr = new int[]{5,6,9,8,7,4,1,2,3}; 28 shellSort(arr); 29 System.out.println(Arrays.toString(arr)); 30 } 31 }
最后，如果小伙伴觉得这篇博文对你有帮助的话，就点个推荐吧
