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

各种排序算法及其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

?

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];}}}?

?