<>希尔排序

又叫“缩小增量排序”,插入排序的一种更高效的改进版本

<>基本原理

1、选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组
2、对分好组的每一组数据完成插入排序
3、减小增长量,直到减小到1,重复第二步操作

<>增长量

确定增长量的规则如下

求出增长量的最大值,先设最开始 h=1,有如下规则:
int h = 1; while(h<数组的长度/2){ h = 2h+1; }
接下来再根据规则减小增长量h
h = h/2;
增长量是用来控制分组的

<>图解

假设有数组:{9,1,2,5,7,4,8,6,3,5}
长度为10,所以初始的增长量由上面的方式可以求得为h=7,再一步步缩小增长量,来进行分组

当h = 7时

当h = 3时
当h=1时

<>具体代码
//主要思想:先分组,再进行排序 public class ShellSort { public static void main(String[] args
) { //定义一个数组 int arr[] = {9,1,2,5,7,4,8,6,3,5}; //定义h来表示增长量 int h = 1; while(h<
arr.length){ h = 2*h+1; } while(h>=1){ //根据h进行分组,找到待交换的元素 for(int i = h; i<arr.
length; i++){ for(int j = i; j>=h; j-=h){ //比较并交换位置 if(arr[j-h]>arr[j]){ int
temp; temp = arr[j-h]; arr[j-h] = arr[j]; arr[j] = temp; }else{
//直到将这一轮中最小的数移动到最前面时时退出循环 break; } } } //缩小h的值,改变增长量 h = h/2;
//System.out.println(h + "\n"); //这串代码可以看到增长量的变化 } for(int array : arr){ System.
out.print(array + " "); } } }
可能写的有点混乱,但大致意思就这样了,个人理解,具体请结合代码,步步调试,很好理解的,有误望指出,一起进步呀

技术
©2019-2020 Toolsou All rights reserved,
C语言——qsort函数CSS实现溢出显示省略号网络层协议——ICMP协议C语言小游戏-俄罗斯方块Qt入门教程【基础控件篇】QCalendarWidget日历控件用python来控制wifi连接vue中input框只能输入数字Python内置函数C语言数据结构-顺序表删除重复V2.0.0abaqus质量缩放系数取值_ABAQUS的质量缩放