[数据结构与算法]Java数据结构与算法Day17--希尔排序(多次插入)

希尔排序?

经过测试,希尔排序对于8w长度的数组,需要的时间为毫秒级.具体的实现主要也是利用插入排序

我们把一个数组分为arr.lenth / 2?组?

如上图所示,我们把[8,3],[9,5],[1,4],[7,6],[2,0]分别视为五个数组,分别进行插入排序,不过这次的插入排序,同组的数中间隔了group_num(划分成的组数,也就是5)个.所以在for循环条件中++变成了+=group_number

?如上图,将得到的结果进行第二次分组,然后进行插入排序

如上图,第三次分组时,group_num已经变为1,即这是最后一次分组,且这次的分组就是整个数组,但是经过前两次的插入排序,我们现在已经得到了一个接近有序的数组?

?在这种情况下,整个数组进行插入排序所消耗的资源就会大大下降,同时稳定性得到了提高

整体代码

import java.util.Arrays;
import java.util.Random;


public class ShellSort {
    public static void main(String[] args) {
//        int[] arr = new int[]{8,9,1,7,2,3,5,4,6,0};
//        shell_simple(arr);
//        System.out.println(Arrays.toString(arr));
        int[] arr1 = new int[80000];
        Random random = new Random();
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = random.nextInt(80000);
        }
        int[] arr2 = arr1.clone();
        long start = System.currentTimeMillis();
        shell(arr1);
        long end = System.currentTimeMillis();
        System.out.println("用时:"+(end - start));
        System.out.println(Arrays.toString(arr1));
    }
    //所谓希尔排序,就是先分组,再进行插入排序
    public static void shell(int[] arr) {
        //第一次group是数组的1/2,后面每次1/2
        int num_tmp;
        int index_tmp;
        for (int group = arr.length / 2; group > 0; group /= 2) {
            for (int i = 0; i < group; i++) {
                for (int j = i + group; j < arr.length; j += group) {
                    //在这个for循环中,遍历了所有的属于同组的,现在来做插入排序
                    //如果前一个大于后一个
                    num_tmp = arr[j];
                    index_tmp = j;
                    while (index_tmp >= group && arr[index_tmp - group] > num_tmp) {
                        arr[index_tmp] = arr[index_tmp - group];
                        index_tmp -= group;
                    }
                    //跳出时,表示找到了自己的位置
                    arr[index_tmp] = num_tmp;
                }
            }
        }

    }
}