（3）排序算法——插入排序之希尔排序

发表于   |   分类于   |   阅读次数

1、基本思想：

希尔排序实质上是一种分组插入排序的排序算法，是简单直接插入算法的改进版，也被称为增量排序。

一般情况下，我们会按照数组的下标进行增量分组，每组使用直接插入排序的方法进行排序。随着增量的减小，每组所包含的元素越来越少，当增量减值1时，整个数组恰好被分为一组，算法便执行完成。

通常我们使用数组的一半作为起始增量（但不是最好的增量选择方式），但是增量最终值一定是1，这样才能保证数组有序。

当刚开始希尔排序时，元素很无序时，增量最大，每组插入排序的个数很少，速度很快；当元素基本有序了，增量很小，插入排序对有序的序列排序效率很高。依照这种规律来提高希尔排序的速度。

2、算法描述

假设有数组arr[n]，降序排列

  1. 将数组分为n/2个数字序列，第1个数和第n/2+1个数据为一对，……
  2. 一次循环对这n/2个序列排序，使每个序列都有序。
  3. 然后将n个元素的数组分为n/4个序列，再次对每个序列进行排序。
  4. 不断重复以上过程，直到序列减少成一个，再进行排序就完了。

3、Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 希尔排序
 * 
 * @author lizhen
 */
public class ShellSort {
	public void shellSort(int[] array) {
		// 降序排序
		for (int k = array.length / 2; k >= 1; k = k / 2) {
			int j;
			for (int i = k; i < array.length; i = i + 1) {
				int currentNum = array[i];
				for (j = i; j >=k&&currentNum > array[j-k]; j = j - k) 
					array[j] = array[j-k];
				array[j] = currentNum;
			}
		}
	}
}

第一个for循环，遍历增量k。起始于array.length/2, 始截止于1，变化为不断的除以2。

第二个for循环，对每一个分组进行排序遍历。i=k意思是第一个分组的第二个元素开始取，要遍历整个数组，所以i<array.length，i++是因为要循环所有的分组，并不是一个分组完再循环另一个分组，所有的分组数据是循环进行的。

第三个for循环，拿着每个分组未排序的元素插入到已排好序的进行排序。

4、效率分析