笨办法学数据结构 java实现希尔排序
程序员文章站
2022-04-16 16:29:42
插入排序可能存在的问题. 数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是:{2,3,4,5,6,6}{2,3,4,5,5,6}{2,3,4,4,5,6}{2,3,3,4,5,6}{2,2,3,4,5,6}{1,2,3,4,5,6}结论: 当需要插入的数是较小的数时,后移的次数明显增多,对效率有影响.插入排序的问题可以用希尔排序解决希尔排序法介绍希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔...
插入排序可能存在的问题.
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是:
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时,后移的次数明显增多,对效率有影响.
插入排序的问题可以用希尔排序解决
希尔排序法介绍
希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。
希尔排序法基本思想
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止
希尔排序法的示意图
代码演示
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int arry[]= new int[8];
for(int i=0;i<8;i++) {
arry[i]=(int) (Math.random()*8000000);
}
sort(arry);
System.out.println("----------排序后结果----------");
System.out.println(Arrays.toString(arry));
}
public static void sort(int arry[]) {
int pre=0;
int val=0,count=0;
for(int gap=arry.length/2;gap>0;gap/=2) {
for(int i=gap;i < arry.length; i++) {
pre=i-gap;
val=arry[i];
while(pre>=0&&arry[pre]>val) {
arry[pre+gap]=arry[pre];
pre-=gap;
}
arry[pre+gap]=val;
}
System.out.println("第"+(++count)+"次排序结果="+Arrays.toString(arry));
}
}
}
代码演示结果:
本文地址:https://blog.csdn.net/weixin_45829957/article/details/107672191
上一篇: java中的封装
下一篇: 电商数仓——项目需求及架构设计