希尔排序

package com.company;

public class ShellSort {
    /**
     * 希尔排序其实是插入排序的变种
     * 在这里姑且先用非递归排序实现
     * 此算法
     * 只不过它有步长的设定
     * 即，根据步长来对整个数组进行分组
     * 不过每个分组中的元素都是间距相同
     * 的两个元素
     * 然后对每组进行排序
     * 其实也是分而治之算法的体现
     * @param sourceArray
     */
    static public void shellSort0(int[] sourceArray) {
        int arrayLength = sourceArray.length;
        //一开始的步长。
        int stepWidth = arrayLength;
        //因为最后的步长肯定会变成1的
        //这也就意味着最后一次排序的进行了
        while (stepWidth > 1) {
            //姑且把步长设置为原来步长的1/2吧
            stepWidth /= 2;
            //打印
            System.out.println("步长为" + stepWidth);
            //我之所以这样写是因为我觉得
            //1、步长会越来越小
            //2、所有步长相邻的元素都可以从开始
            //被遍历到。
            //但是这样写会使整个实现变得很长
            for (int counter = 0;counter < stepWidth;counter++) {
                //现在开始进行一小趟的排序
                //通过插入排序法对每个元素进行排序
                //需要被插入的index
                int stepIndex = 1;
                //这个元素的index不能超出数组范围
                while (counter + stepIndex * stepWidth < arrayLength) {
                    int insertIndex = counter + stepIndex * stepWidth;
                    //先保存这个待插入的元素值
                    int tempElement = sourceArray[insertIndex];
                    //元素该插入的位置。
                    int targetIndex = counter;
                    for (int counter0 = counter;counter0 < counter + stepIndex * stepWidth;counter0+=stepWidth) {
                        if (tempElement > sourceArray[counter0]) {
                            targetIndex = counter0;
                            //移动元素
                            for (int counter1 = insertIndex;counter1 > targetIndex;counter1-=stepWidth)
                                sourceArray[counter1] = sourceArray[counter1 - stepWidth];
                            //插入元素
                            sourceArray[targetIndex] = tempElement;
                            break;
                        } else continue;
                    }
                    //打印每一分组的元素状况。
                    for (int element:sourceArray) {
                        System.out.print(element + " ");
                    }
                    System.out.println("第" + stepIndex + "次交换结束了");
                    stepIndex++;
                }
                //打印每一趟的元素状况。
                for (int element:sourceArray) {
                    System.out.print(element + " ");
                }
                System.out.println("第" + (counter + 1) + "趟结束了\n");
            }
        }
    }

    /**
     * 上面的方法写得过于冗长
     * 本方法是参照了网上的版本
     * 把代码写得精简了一些
     * @param sourceArray
     */
    static public void shellSort1(int[] sourceArray) {
        int arrayLength = sourceArray.length;
        //上面那个while循环完全可以写成for循环
        for (int stepWidth = arrayLength / 2;stepWidth >= 1;stepWidth /= 2){
            //因为上面的方法比较长，所以此处需要改写。
            //毕竟插入排序算法是从第2个元素开始的
            //其实就相当于步长为1了
            //而现在是步长是大于了
            //那么就是说可以从1*stepWidth开始
            //下面这样写是把插入和遍历整个数组的思想结合起来了
            //这种写法的宏观着眼点是针对每个元素采取不同的方式来处理
            //我上面的着眼点是一个个单独的相邻步长的元素
            //我上面的写法总是直接切入没拐弯
            for (int counter = stepWidth;counter < arrayLength;counter++) {
                //这个还是保存需要被插入的元素值
                int tempElement = sourceArray[counter];
                //这样就把下标变成从0开始了
                int counter0 = counter - stepWidth;
                //它是从后往前遍历，只要不满足这个条件就代表找到位置了
                //而我是从前往后正向遍历——很麻烦！
                //从后往前写给人的感觉思路非常清晰
                //并且这样遍历到每个元素，它之前的元素
                //都已经是排好序的了
                while (counter0 >= 0 && tempElement > sourceArray[counter0]) {
                    sourceArray[counter0 + stepWidth] = sourceArray[counter0];
                    counter0 -= stepWidth;
                }
                sourceArray[counter0 + stepWidth] = tempElement;
            }
            //打印每一趟的元素状况。
            for (int element:sourceArray) {
                System.out.print(element + " ");
            }
            System.out.println("步长 " + stepWidth + " 的趟结束了\n");
        }
    }
}