栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数据结构学习(韩顺平)之希尔排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构学习(韩顺平)之希尔排序

package com.atguigu.sort;

import java.util.Arrays;


public class ShellSort {
    public static void main(String[] args) {
        int[] arr = new int[]{8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("排序前" + Arrays.toString(arr));

        shellSort(arr);
        System.out.println("交换式排序后" + Arrays.toString(arr));
        
        shellSort2(arr);
        System.out.println("移位排序后" + Arrays.toString(arr));

    }

    public static void shellSort(int[] arr) {

        //希尔排序时,对有序序列插入时采用交换法
        int temp;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {//分成了gap组,i从gap开始是为了方便内层的for循环
                //这里从gap到arr.length的循环非常巧妙,避免了数组引用出界
                //遍历每一组的元素
                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;
                    }

                }
            }


        }

//方式一:正确
//        //希尔排序的第一轮:其中5是组数
//        int temp;
//        for (int i = 5; i < arr.length; i++) {//分成了5组,i从5开始是为了方便内层的for循环
//            //遍历每一组的元素
//            for (int j = i - 5; j >= 0; j -= 5) {//相当于每一组中从后向前遍历
//                if (arr[j] > arr[j + 5]) {//此时的arr[j]是同一组中的最后一个元素
//                    temp = arr[j];
//                    arr[j] = arr[j + 5];
//                    arr[j + 5] = temp;
//                }
//
//            }
//        }
//        System.out.println("第一轮排序后" + Arrays.toString(arr));
//
//        for (int i = 2; i < arr.length; i++) {
//            //遍历每一组的元素
//            for (int j = i - 2; j >= 0; j -= 2 ){//相当于每一组中从后向前遍历
//                if (arr[j] > arr[j + 2]) {//此时内部组的排序相当于是小冒泡
//                    temp = arr[j];
//                    arr[j] = arr[j + 2];
//                    arr[j + 2] = temp;
//                }
//
//            }
//        }
//        System.out.println("第二轮排序后" + Arrays.toString(arr));


//        //方式2:错误
// 第一轮还可以,但是后边第二轮开始就无法对一组的数进行排序。
//        int temp;
//        for (int i = 0; i < arr.length-5; i++) {
//            for (int j = i; j + 5 < arr.length; j += 5) {
//                if (arr[j] > arr[j + 5]) {
//                    temp = arr[j];
//                    arr[j] = arr[j + 5];
//                    arr[j + 5] = temp;
//                }
//            }
//        }
//        System.out.println("希尔排序一轮后" + Arrays.toString(arr));
//
//        for (int i = 0; i < arr.length-5; i++) {
//            for (int j = i; j + 2 < arr.length; j += 2) {
//                if (arr[j] > arr[j + 2]) {
//                    temp = arr[j];
//                    arr[j] = arr[j + 2];
//                    arr[j + 2] = temp;
//                }
//            }
//        }
//        System.out.println("希尔排序二轮后" + Arrays.toString(arr));


    }

    //对交换式希尔排序进行优化->移位法
    public static void shellSort2(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //从第gap个元素,逐个对其所在的组进行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int insertIndex = i;
                int insertVal = arr[insertIndex];
                while (insertIndex - gap >= 0 && insertVal < arr[insertIndex - gap]) {
                    arr[insertIndex] = arr[insertIndex-gap];
                    insertIndex-=gap;
                }
                //当退出while循环后就给insertVal找到了插入的位置
                arr[insertIndex]=insertVal;
            }
        }


    }
}

希尔排序其实就是对插入排序加入了gap分组的条件,分不同的组进行插入排序。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/949016.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号