算法--排序算法-希尔排序

希尔排序可以说是一种改进的插入排序，也可以称为缩小增量排序

代码实现：交换法

package com.atguigu.test;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class ShellSort {

    public static void main(String[] args) {

        // 定义一个数组
        int [] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };

        // 希尔排序-交换方式
        shellSort(arr);
    }

    //  使用逐步推导的方式来编写希尔排序
    //  希尔排序时， 对有序序列在插入时采用交换法,
    //  思路(算法) ===> 代码
    public static void shellSort(int[] arr) {

        int temp = 0;
        int count = 0;
        //  根据前面的逐步分析，使用循环处理
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                //  遍历各组中所有的元素(共gap组，每组有个元素), 步长gap
                for (int j = i - gap; j >= 0; j -= gap) {
                    //  如果当前元素大于加上步长后的那个元素，说明交换
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            System.out.println("希尔排序第" + (++count) + "轮 =" + Arrays.toString(arr));
        }
    }
}

代码实现：移动法

package com.atguigu.test;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class ShellSort {

    public static void main(String[] args) {

        // 定义一个数组
        int [] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };


        // 希尔排序-移动方式
        shellSort2(arr);
    }

    // 对交换式的希尔排序进行优化->移位法
    public static void shellSort2(int[] arr) {

        int count = 0;
        //  增量gap, 并逐步的缩小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //  从第gap个元素，逐个对其所在的组进行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        // 移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    // 当退出while后，就给temp找到插入的位置
                    arr[j] = temp;
                }

            }
            System.out.println("希尔排序第" + (++count) + "轮 =" + Arrays.toString(arr));
        }
    }
}