排序算法之希尔排序java实现

知识准备

---

基础概念

希尔排序：在直接插入排序的基础上进行的优化，直接插入排序在n值小的时候效率比较高，在n很大的时候如果待排序序列基本有序，效率依然很高，时间效率可以提升为O(n)。希尔排序也称之为缩小增量排序。 1.先选取一个小于n的整数d（步长），然后按照步长d将待排序序列分为d组，从第一个记录开始间隔为d的为一个组。然后对各组内进行直接插入排序，一趟过后，间隔为d的序列有序，随着有序性的改善，减少步长d重复进行 。直到d=1使得间隔为1的记录有序，也就达到了整体有序

步骤分解

1.我们有序列 18、 24、 12 、15 、1 、27、 17 、19。我们以步长为序列长度除以2作为第一次的步长。以后每次都在原有的步长基础上除以2取整。直到步长为1后进行直接插入排序为止。

如上图所示，我们把序列根据步长8/2=4，将序列分成四组分别为： [1，18]、[24，27]、[12，17]、[15,19]。 然后对各组进行直接插入排序得到最后的结果：

1、24、12、15、18、27、17、19

2.继续缩减步长，在上一步的结果序列1、24、12、15、18、27、17、19基础上使得步长为上一步步长除以2，即步长为4/2=2重复第一步如下图所示。

根据步长分为两组，[1,12,17,18]、[15,19,24,27]然后分别执行直接插入排序获得结果：

1、15、12、19、17、24、18、27

3.我们已经看到序列逐步成为有序的过程，知道最后步长为1，如当前实例。执行到第三步步长为2/2=1，所以进行最后一步的直接插入排序，序列就是有序序列了。

得到最终序列：

1、12、15、17、18、19、24、27

代码实现

/** * 希尔排序 * * @param num */ public static void ShellSort(int num[]) { int temp; //默认步长为数组长度除以2 int step = num.length; while (true) { step = step / 2; //确定分组数 for (int i = 0; i < step; i++) { //对分组数据进行直接插入排序 for ( int j = i + step; j < num.length; j = j + step) { temp=num[j]; int k; for( k=j-step;k>=0;k=k-step){ if(num[k]>temp){ num[k+step]=num[k]; }else{ break; } } num[k+step]=temp; } } if (step == 1) { break; } } }

注：网络上有些希尔排序写的稍微有点问题,把希尔排序里面的直接插入写成了冒泡了。