基础算法:希尔排序

标签: 算法  排序  希尔排序

希尔排序,也称递减增量排序算法,1959年Shell发明。是插入排序的一种高速而稳定的改进版本。

希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

1、基本思想

(1)设待排序元素序列有n个元素,首先取一个整数increment(小于n)作为间隔将全部元素分为increment个子序列,所有距离为increment的元素放在同一个子序列中,在每一个子序列中分别实行直接插入排序。然后缩小间隔increment,重复上述子序列划分和排序工作。直到最后取increment=1,将所有元素放在同一个子序列中排序为止。 
(2)由于开始时,increment的取值较大,每个子序列中的元素较少,排序速度较快,到排序后期increment取值逐渐变小,子序列中元素个数逐渐增多,但由于前面工作的基础,大多数元素已经基本有序,所以排序速度仍然很快。 

2、算法描述

1>下面给出一个数据列: 
 

这里写图片描述

2>第一趟取increment的方法是:n/3向下取整+1=3(关于increment的取法之后会有介绍)。将整个数据列划分为间隔为3的3个子序列,然后对每一个子序列执行直接插入排序,相当于对整个序列执行了部分排序调整。图解如下: 
 

这里写图片描述

3>第二趟将间隔increment= increment/3向下取整+1=2,将整个元素序列划分为2个间隔为2的子序列,分别进行排序。图解如下: 

è¿éåå¾çæè¿°


 
4>第3趟把间隔缩小为increment= increment/3向下取整+1=1,当增量为1的时候,实际上就是把整个数列作为一个子序列进行插入排序,图解如下: 
 

è¿éåå¾çæè¿°


5>直到increment=1时,就是对整个数列做最后一次调整,因为前面的序列调整已经使得整个序列部分有序,所以最后一次调整也变得十分轻松,这也是希尔排序性能优越的体现。 

3、代码实现

/**
	 * 希尔排序(Wiki官方版)
	 *
	 * 1\. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;(注意此算法的gap取值) 
	 * 2\. 按增量序列个数k,对序列进行k趟排序;
	 * 3\. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。
	 * 		仅增量因子为1时,整个序列作为一个表来处理,表长度即为整个序列的长度。
	 * 
	 * @param arr
	 *            待排序数组
	 */
	public static void shell_sort(int[] arr) {
		int gap = 1, i, j, len = arr.length;
		int temp;
		System.out.println(len / 3);
		while (gap < len / 3) {
			gap = gap * 3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121,
		}
		// ...
		for (; gap > 0; gap /= 3) {
			for (i = gap; i < len; i++) {
				temp = arr[i];
				for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
					arr[j + gap] = arr[j];
				}
				arr[j + gap] = temp;
			}
		}
	}

以下是希尔排序复杂度:

平均时间复杂度 最好情况 最坏情况 空间复杂度
O(nlog2 n) O(nlog2 n) O(nlog2 n) O(1)
原文链接:加载失败,请重新获取