希尔排序(Shell Sort)

约定不等于承诺〃 2023-07-25 05:26 13阅读 0赞

是插入排序经过改进之后的高效版本，也称缩小增量排序。

1959 年提出，是突破时间复杂度 O(n2) 的第一批算法之一。

缩小增量排序的最优增量选择是一个数学难题，一般采用希尔建议的增量，具体如下。

**思路与步骤：**

*  首次选择的增量(即步长，下同) step = 数组长度 / 2 取整；缩小增量 step ，每次减半，直到为 1 结束缩小；逐渐缩小的增量组成一个序列：\[n/2, n/2/2, ... 1\]
 *  对数组进行 序列里增量的个数 趟排序
 *  每趟排序，把增量作为间隔，将数组分割成若干子数组，分别对各子数组进行插入排序
 *  当增量等于 1 时，排序整个数组后，排序完成

**代码：**

package constxiong.interview.algorithm;
    
    /**
     *  希尔排序
     * @author ConstXiong
     * @date 2020-04-11 11:58:58
     */
    public class ShellSort {
    	
    	public static void main(String[] args) {
    		int [] array = {33, 22, 1, 4, 25, 88, 71, 4};
    		shellSort(array);
    	}
    	
    	/**
    	 * 希尔排序
    	 * @param array
    	 */
    	private static void shellSort(int[] array) {
    		print(array);
    		int length = array.length;
    		int step = length / 2; //步长，默认取数组长度一半
    		int temp; 
    		while (step > 0) {
    			for (int i = step; i < length; i++) { //从步长值为下标，开始遍历
    				temp = array[i]; //当前值
    				int preIndex = i - step; //步长间隔上一个值的下标
    				//在步长间隔的的数组中，找到需要插入的位置，挪动右边的数
    				while (preIndex >= 0 && array[preIndex] > temp) { 
    					array[preIndex + step] = array[preIndex];
    					preIndex -= step;
    				}
    				//把当前值插入到在步长间隔的的数组中找到的位置
    				array[preIndex + step] = temp;
    			}
    			step /= 2;
    			print(array);
    		}
    	}
    
    	/**
    	 * 打印数组
    	 * @param array
    	 */
    	private static void print(int[] array) {
    		for(int i : array) {
    			System.out.print(i + " ");
    		}
    		System.out.println();
    	}
    
    }

打印：

33 22 1 4 25 88 71 4 
    25 22 1 4 33 88 71 4 
    1 4 25 4 33 22 71 88 
    1 4 4 22 25 33 71 88

**特征：**

*  空间复杂度为 O(1)，是原地排序算法
 *  最好、最坏、平均情况时间复杂度，都是 O(nlog2 n)
 *  非稳定排序。因为进行了增量间隔分组排序，可能导致相等的值先后顺序变换

--------------------

### 【Java面试题与答案】整理推荐 ###

*  [基础与语法][Link 1]
 *  [集合][Link 2]
 *  [网络编程][Link 3]
 *  [并发编程][Link 4]
 *  [Web][]
 *  [安全][Link 5]
 *  [设计模式][Link 6]
 *  [框架][Link 7]
 *  [算法与数据结构][Link 8]
 *  [异常][Link 9]
 *  [文件解析与生成][Link 10]
 *  [Linux][]
 *  [MySQL][]
 *  [Oracle][]
 *  [Redis][]
 *  [Dubbo][]

[Link 1]: https://www.javanav.com/interview/93b0069472fd479393006c0e73043fc4.html
[Link 2]: https://www.javanav.com/interview/4147d95e693945e7a50345fd33ec817e.html
[Link 3]: https://www.javanav.com/interview/68a57ffc78de4133bb890bdd502ac418.html
[Link 4]: https://www.javanav.com/interview/36a24fa3258e45c89873f474ce914912.html
[Web]: https://www.javanav.com/interview/4e27cb63adb440c6825a159d35cf4010.html
[Link 5]: https://www.javanav.com/interview/03affb2ce3f04fda8853f714e5764906.html
[Link 6]: https://www.javanav.com/interview/07a32a9ff17a4006a53550ce658cafed.html
[Link 7]: https://www.javanav.com/interview/5c466456e9b54ab0a749b5948e51f1d3.html
[Link 8]: https://www.javanav.com/interview/943f917041ee4f05add24539f5b861b2.html
[Link 9]: https://www.javanav.com/interview/d3f058cfc05d4c6dadd821b622e84d36.html
[Link 10]: https://www.javanav.com/interview/67a50996c28f418e83b109ea42fc3eff.html
[Linux]: https://www.javanav.com/interview/00cccb81729540d1923bd0a0ef49533a.html
[MySQL]: https://www.javanav.com/interview/d311e78502a845f1a4bb307bd6aec2b3.html
[Oracle]: https://www.javanav.com/interview/5f29e9677edf4a16be3dce30d257c9ab.html
[Redis]: https://www.javanav.com/interview/066c62b3af4d4827b2243a822c3084a9.html
[Dubbo]: https://www.javanav.com/interview/9a3e7a7740324757abaab953f7ebc455.html