欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

笨办法学数据结构 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时,整个文件恰被分成一组,算法便终止

希尔排序法的示意图

笨办法学数据结构  java实现希尔排序

代码演示


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));
		}
	}
}

代码演示结果:

笨办法学数据结构  java实现希尔排序

本文地址:https://blog.csdn.net/weixin_45829957/article/details/107672191