各种排序算法及其java程序实现（4） -- 希尔排序(Shell Sort)

希尔排序(Shell Sort)

 

插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

 

希尔排序基本思想：

　　先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序 ；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。 　　

      该方法实质上是一种分组插入方法。

　　给定实例的shell排序的排序过程

　　假设待排序文件有10个记录，其关键字分别是：

　　49，38，65，97，76，13，27，49，55，04。

　　增量序列的取值依次为：

　　5，3，1

 

缩小增量法

　　属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序

　　排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止

　　初始：d=5

　　49 38 65 97 76 13 27 49* 55 04

　　49 13

　　|-------------------|

　　38 27

　　|-------------------|

　　65 49*

　　|-------------------|

　　97 55

　　|-------------------|

　　76 04

　　|-------------------|

　　一趟结果

　　13 27 49* 55 04 49 38 65 97 76

　　d=3

　　13 27 49* 55 04 49 38 65 97 76

　　13 55 38 76

　　|------------|------------|------------|

　　27 04 65

　　|------------|------------|

　　49* 49 97

　　|------------|------------|

      二趟结果

　　13 04 49* 38 27 49 55 65 97 76

　　d=1

　　13 04 49* 38 27 49 55 65 97 76

　　|----|----|----|----|----|----|----|----|----|

　　三趟结果

　　04 13 27 38 49* 49 55 65 76 97

 

算法分析：

不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度为 O(N*(logN)2)， 没有快速排序算法快 O(N*(logN))，因此中等大小规模表现良好，对规模非常大的数据排序不是 最优选择。但是比O(N2）复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏 的情况下执行的效率会非常差。 专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快， 再改成快速排序这样更高级的排序算法. 本质上讲，希尔排序算法的一种改进，减少了其复制的次数，速度要快很多。 原因是，当N值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。 当N值减小时每一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。

 

稳定性：

稳定性 ：

排序前一个序列中,如果出现N个与关键字相同的数据,那么排序后仍然按照原先序列的排列顺序排列,就说这个算法是稳定的,反之就是不稳定的。通俗地讲就是 能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。

 

希尔分析 ：

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元 素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

 

Java 代码实现：

 

package test.suanfa;

/**
 * 插入排序----希尔排序：我们选择步长为：15,7,3,1 我们选择步长公式为：2^k-1,2^(k-1)-1,……,15,7,3,1
 * (2^4-1,2^3-1,2^2-1,2^1-1) 注意所有排序都是从小到大排。
 * 
 * @author TSW
 */
public class ShellSort {
	
	/**
	 * 测试   
	 * @param args
	 */
	public static void main(String[] args) {      
		Integer[] intgArr = { 5, 9, 1, 4, 8, 2, 6, 3, 7, 0 };
		ShellSort shellSort = new ShellSort();
		shellSort.sort(intgArr, 0, intgArr.length - 1);
		for (Integer intObj : intgArr) {
			System.out.print(intObj + " ");
		}
	}      

	/**
	 * 排序算法的实现，对数组中指定的元素进行排序  
	 * @param array 待排序的数组   
	 * @param from 从哪里开始排序   
	 * @param end 排到哪里   
	 */
	public void sort(Integer[] array, int from, int end) {

		// 初始步长，实质为每轮的分组数

		int step = initialStep(end - from + 1);

		// 第一层循环是对排序轮次进行循环。(step + 1) / 2 - 1 为下一轮步长值

		for (; step >= 1; step = (step + 1) / 2 - 1) {

			// 对每轮里的每个分组进行循环

			for (int groupIndex = 0; groupIndex < step; groupIndex++) {

				// 对每组进行直接插入排序

				insertSort(array, groupIndex, step, end);

			}

		}

	}

	/**
	 * 直接插入排序实现
	 * @param array 待排序数组   
	 * @param groupIndex 对每轮的哪一组进行排序  
	 * @param step 步长   
	 * @param end 整个数组要排哪个元素止   
	 */
	public void insertSort(Integer[] array, int groupIndex, int step, int end) {

		int startIndex = groupIndex;// 从哪里开始排序

		int endIndex = startIndex;// 排到哪里

		/*
		 * 
		 * 排到哪里需要计算得到，从开始排序元素开始，以step步长，可求得下元素是否在数组范围内，
		 * 
		 * 如果在数组范围内，则继续循环，直到索引超现数组范围
		 */

		while ((endIndex + step) <= end) {

			endIndex += step;

		}

		// i为每小组里的第二个元素开始

		for (int i = groupIndex + step; i <= end; i += step) {

			for (int j = groupIndex; j < i; j += step) {

				Integer insertedElem = array[i];

				// 从有序数组中最一个元素开始查找第一个大于待插入的元素

				if ((array[j].compareTo(insertedElem)) >= 0) {

					// 找到插入点后，从插入点开始向后所有元素后移一位

					move(array, j, i - step, step);

					array[j] = insertedElem;

					break;

				}

			}

		}

	}

	/**
	 * 根据数组长度求初始步长   
	 * 
	 * 我们选择步长的公式为：2^k-1,2^(k-1)-1,...,15,7,3,1 ，其中2^k 减一即为该步长序列，k 为排序轮次    
	 * 
	 * 初始步长：step = 2^k-1    
	 * 初始步长约束条件：step < len - 1 初始步长的值要小于数组长度还要减一的值
	 * （因 为第一轮分组时尽量不要分为一组，除非数组本身的长度就小于等于4） 
	 * 
	 * 由上面两个关系试可以得知：2^k - 1 < len - 1 关系式，其中k为轮次，如果把2^k 表 达式   
	 * 转换成step 表达式，则2^k-1 可使用(step + 1)*2-1 替换（因为step+1 相当于第k-1  
	 * 轮的步长，所以在step+1 基础上乘以2 就相当于2^k 了），即步长与数组长度的关系不等式为
	 * (step + 1)*2 - 1 < len -1   
	 * 
	 * @param len 数组长度   
	 * @return
	 */
	public static int initialStep(int len) {

		/*
		 * 
		 * 初始值设置为步长公式中的最小步长，从最小步长推导出最长初始步长值，即按照以下公式来推:
		 * 
		 * 1,3,7,15,...,2^(k-1)-1,2^k-1
		 * 
		 * 如果数组长度小于等于4时，步长为1，即长度小于等于4的数组不用分组，此时直接退化为直接插入排序
		 */

		int step = 1;

		// 试探下一个步长是否满足条件，如果满足条件，则步长置为下一步长

		while ((step + 1) * 2 - 1 < len - 1) {

			step = (step + 1) * 2 - 1;

		}

		System.out.println("初始步长: " + step);

		return step;

	}

	/**
	 * 以指定的步长将数组元素后移，步长指定每个元素间的间隔 
	 * @param array 待排序数组   
	 * @param startIndex 从哪里开始移   
	 * @param endIndex 到哪个元素止   
	 * @param step 步长   
	 */
	protected final void move(Integer[] array, int startIndex, int endIndex, int step) {
		for (int i = endIndex; i >= startIndex; i -= step) {
			array[i + step] = array[i];
		}
	}

}