男和男做那个视频网站,南宁公司网站建设方案,营销型网站费用,wordpress 建站教程 下载文章目录 1. 概念2. 思路3. 代码实现 1. 概念 希尔排序也是一种插入排序#xff0c;它是简单插入排序经过改进之后的一个更高效的版本#xff0c;也称为缩小增量排序。希尔排序在数组中采用跳跃式分组的策略#xff0c;通过某个增量将数组元素划分为若干组#xff0c;然后分… 文章目录 1. 概念2. 思路3. 代码实现 1. 概念 希尔排序也是一种插入排序它是简单插入排序经过改进之后的一个更高效的版本也称为缩小增量排序。希尔排序在数组中采用跳跃式分组的策略通过某个增量将数组元素划分为若干组然后分组进行插入排序随后逐步缩小增量继续按组进行插入排序操作直至增量为1。 推荐一个B站六分钟的视频PPT动画做的非常好清晰明了。 2. 思路
① 希尔排序采用跳跃式的分组方式什么是跳跃式也就是说同一组内的成员在原序列中实际上是互相隔着一段距离的它们被迫抽出来组成一队内部采用插入排序比较大小。它们互相隔着的距离是相等的这个距离我们称它为增量增量怎么确定一般来说初始增量值为序列长度的一半接下来我们根据增量值计算分组如下图增量为5所以索引0跟索引5一组索引1跟索引6一组 …以此类推序列被分成了五组 ② 分了组之后组员内部要进行插入排序的但是这里的插入排序步长其实并不是1我们知道原本的插入排序是从右往左一步一步地比较大小并插入的但是希尔排序是跳跃式分组的虽然说你们被分到了同一个队伍里但是不要忘记了你们本身的索引并不相连索引还是原来位置的索引所以在这里插入排序的时候每一步的长度应该是增量的大小除了步长不一样外其它思路都不变
③ 在第一轮排序完成之后发现整体上序列的顺序有了一个大体的趋势小的基本在左边大的基本在右边但这才是第一步还不算排好序
④ 再开始下一轮排序每一轮开始时的增量值都应是上一轮增量值的一半。原理还不变外部分组内部插入排序什么时候不再分组不再排序增量值一直减半总有一天它会减为1到1的时候就是全体序列进行最基本的插入排序了没错这是最后一步所以终止条件就是增量值开始小于1这时候的序列已经完全有序。
3. 代码实现
import java.util.Arrays;public class Test {public static void main(String[] args) {int[] arr {2, 9, 3, 11, 7, 8, 4, 1, 6};int[] newArr sort(arr);System.out.println(Arrays.toString(newArr));}public static int[] sort(int[] arr) {//控制增量值初始值为序列长度的一半每次减半步长为0时停止for (int step arr.length / 2; step 0; step / 2) {//控制待插入元素的位置初始值为增量值for (int i step; i arr.length; i) {//待插入元素int insertVal arr[i];//待比较元素初始位置int index i - step;//控制待比较元素的位置初始值为待插入元素的位置减去增量值即indexwhile (index 0 insertVal arr[index]) {//当前待比较元素向后移一位这里的一位就是step长度arr[index step] arr[index];//指针向左挪动一位继续跟下一个元素作比较index - step;}//退出循环后后将待插入元素插入到index的下一位arr[index step] insertVal;}}return arr;}
}
