本文共 1636 字，大约阅读时间需要 5 分钟。

0. 前言

本系列文章将介绍一些常用的排序算法。排序是一个非常常见的应用场景，也是开发岗位面试必问的一道面试题，有人说，如果一个企业招聘开发人员的题目中没有排序算法题，那说明这个企业不是一个“正规”的企业，哈哈，虽然有点戏谑，但是也从侧面证明了排序算法的重要性。

本文将介绍的是常见排序算法中的希尔排序。

5  希尔排序

5.1  基本思想

希尔排序是对插入排序的一个改进，希尔排序首先把待排数列按照一定增量进行分割，比如{3,1,5,9,6,5,0,2,4,12}数列，我们首先设置增量为n/2=5，因此有了分块后5个子块，即{3,5},{1,0},{5,2},{9,4},{6,12}，将每个子块进行插入排序（即第i位与第i+5位进行比较交换），初步排序结果为{3,0,2,4,6,5,1,5,9,12}。希尔排序再将增量逐渐减小，进行5/2=2的分块，即{3,2,6,1,9},{0,4,5,5,12}，同理插入排序得{1,0,2,4,3,5,6,5,9,12}，最终进行2/2=1分块，即对上数列直接进行插入排序得到最终序列{0,1,2,3,4,5,5,6,9,12}。

5.2  代码实现

/**@author Calvin*@blog  http://blog.csdn.net/seu_calvin/article/details/56879397*@date 2017/02/24*/public class Order {	private int[] array; 	public Order(int[] array){            this.array = array;	}	    public void sort() {       if(array!=null && array.length>0){    	    //增量递减    	   	for(int k = array.length/2; k>0; k/=2){    	   		for(int i = k; i
   
    =k; j-=k){        	   			if(array[j-k] > array[j]){        	   				int temp = array[j-k];        	   				array[j-k] = array[j];        	   				array[j] = temp;        	   			}    	   			}    	   		}    	   	}       }    }         public void print() {          for(int i = 0; i < array.length; i++)     	  System.out.println(array[i]);    }            public static void main(String[] args) {          int[] array = new int[]{3,1,5,9,6,5,0,2,4,12};         Order order = new Order(array);         order.sort();        order.print();    }    }
   

5.3  性能特点

希尔排序是对插入排序的优化，希尔排序由于增量初始值以及增量每次如何递减的方式不一定，因此时间复杂度也不确定。如果每次都除2，则最坏的情况和直接插入排序的时间复杂度一样是O(n*n)，但是一般认为希尔排序的复杂度为O(n^1.3)，空间复杂度为O(1)，希尔排序是不稳定的算法，因为同样的值若不在一个组内，可能后面的值会被移动到前面。

希尔排序需要选择合适的增量序列，这是比较复杂的，因此希尔排序重在优化思路，现实中比较少用。