网站备案密码有什么用,自助商城,07年做网站,网站使用费用目录
一、引言
二、希尔排序原理
三、代码分析
1. 代码整体结构
2. main方法
3. sort方法#xff08;希尔排序核心逻辑#xff09;
四、测试结果 一、引言 在排序算法的大家族中#xff0c;希尔排序是一种改进的插入排序算法#xff0c;它通过将原始数据分成多个子序…目录
一、引言
二、希尔排序原理
三、代码分析
1. 代码整体结构
2. main方法
3. sort方法希尔排序核心逻辑
四、测试结果 一、引言 在排序算法的大家族中希尔排序是一种改进的插入排序算法它通过将原始数据分成多个子序列进行预排序然后逐渐缩小子序列的间隔最终对整个序列进行常规的插入排序从而在一定程度上提高了排序的效率。在这篇博客中我们将深入解析一段用 Java 实现希尔排序的代码帮助大家透彻理解希尔排序的原理以及代码的具体实现细节。
二、希尔排序原理 希尔排序的基本思想基于插入排序但它引入了一个间隔序列也称为增量序列的概念使得排序过程不再是逐个元素地进行比较和插入而是先对相隔一定间隔的元素进行比较和插入操作随着排序的进行间隔逐渐缩小直到最后间隔为 1此时就相当于进行了一次普通的插入排序。 具体来说希尔排序的步骤如下 首先选择一个合适的间隔序列常见的如希尔本人提出的序列n/2, n/4, n/8, …, 1其中n为数组长度。在每一轮排序中根据当前的间隔将数组分成多个子序列。对于每个子序列按照插入排序的方式进行排序即比较子序列中相邻元素这里的相邻是指间隔为当前所选间隔的元素如果顺序不对则进行交换。完成一轮排序后缩小间隔再次按照上述步骤对新的子序列进行排序直到间隔缩小到 1此时整个数组就完成了排序。
三、代码分析
1. 代码整体结构 以下是我们要详细分析的 Java 希尔排序代码
package 排序;import java.util.Arrays;public class SheelSort {public static void main(String[] args) {int[] arr {5, 7, 4, 2, 0, 3, 1, 6};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for (int grp arr.length / 2; grp 0; grp grp / 2) {for (int i grp; i arr.length; i) {//arr[j]arr[ jgrp]比较for (int j i - grp; j 0; j j - grp) {if (arr[j] arr[j 1]) {int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;} else {break;}}}}}
}2. main方法 在 main 方法中首先定义了一个整数数组 arr并初始化其值为 {5, 7, 4, 2, 0, 3, 1, 6}。这就是我们要进行排序的原始数组。 int[] arr {5, 7, 4, 2, 0, 3, 1, 6};然后调用了 sort 方法并将数组 arr 作为参数传递给它目的是对这个数组进行排序操作。 sort(arr);最后在排序完成后使用 Arrays.toString 方法将排序后的数组以字符串的形式输出到控制台以便直观地查看排序的结果。 System.out.println(Arrays.toString(arr));3. sort方法希尔排序核心逻辑 sort 方法实现了希尔排序的核心逻辑下面我们来详细剖析其内部的操作。 外层循环控制间隔变化 通过 for (int grp arr.length / 2; grp 0; grp grp / 2) 这个外层循环控制着间隔的变化。初始时间隔 grp 被设置为数组长度的一半然后在每一轮循环后间隔会减半直到间隔变为 1。这样就实现了按照逐渐缩小的间隔对数组进行多次预排序的过程。 中层循环遍历子序列 对于每一个确定的间隔 grp通过 for (int i grp; i arr.length; i) 这个中层循环从间隔位置开始遍历整个数组。也就是说对于每一轮间隔为 grp 的排序我们要对以 grp 为间隔划分出来的各个子序列进行排序操作。 内层循环子序列内排序 在中层循环遍历到每个位置 i 时通过内层循环 for (int j i - grp; j 0; j j - grp) 对当前子序列中的元素进行排序。这里的内层循环实现了类似于插入排序的操作只不过比较的是间隔为 grp 的相邻元素。如果发现 arr[j] arr[j 1]这里要注意因为是按照间隔 grp 来比较元素所以 arr[j 1] 实际上是与 arr[j] 间隔为 grp 的下一个元素就通过一个临时变量 temp 来进行交换操作使得子序列中的元素按照插入排序的方式逐渐有序。如果发现当前元素与其间隔为 grp 的下一个元素顺序正确即 arr[j] arr[j 1]则通过 break 语句跳出内层循环不再继续比较该子序列中更前面的元素。 for (int j i - grp; j 0; j j - grp) {if (arr[j] arr[j 1]) {int temp ();arr[j] arr[j 1];arr[j 1] temp;} else {break;}
}四、测试结果 当我们运行上述代码时对于给定的初始数组 {5, 7, 4, 2, 0, 3, 1, 6}经过希尔排序后控制台会输出排序后的数组其结果应该是 {0, 1, 2, 3, 4, 5, 6, 7}。
