2.0 哈希排序 7个常用排序之一

2.哈希排序 ->: 哈希排序 就是分组的插入排序,因为插入排序是 越有序速度越快,所以先分 n 组进行排序,等n组数据都是排成有序时,然后再将 n 组数据 合在一起进行排序,这样速度可以快上很多.  

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        //首先创建一个随机数组
        int[] arr = {5, 2, 1, 3, 6, 0, 4, 8, 9, 7,};
        //new一个Main 对象出来,这样才能借引用,使用对象里的方法
        Main main = new Main();
        //借引用 使用引用所指向对象里的方法
        main.Hill_sorting(arr);
        //Arrays.toString() 是Array类中的一个方法,作用是返回一个包含数组元素的字符串，这些元素被放置在括号内，并用逗号分开
        System.out.println(Arrays.toString(arr));
    }

    public void Hill_sorting(int[] arr) {//哈希排序
        // arr.length 的意思是arr数组的元素个数, 元素个数 / 2 是将这个数组分组,如果10个元素就分成5组,每组两个元素.
        int group = arr.length / 2;
        //只要组数大于等于 1 就进行排序
        while (group >= 1) {
            // 如果 i >= 数组的元素个数 - 组数 那么 i + group 就会越界
            for (int i = 0; i < arr.length - group; i++) {
                int tmp = arr[i + group];
                int a = i;
                //插入排序
                while (a >= 0 && arr[a] > tmp) {
                    arr[i + group] = arr[a];
                    a -= group;
                }
                arr[a+group] = tmp;
            }
            //上面循环结束 说明 一组分组排序已经结束,但是要进行多组 分组循环才能保证 数组尽量是有序的(插入排序越有序 速度越快),所以除以2 在进行分组循环
            group /= 2;
        }
    }
}