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

插入排序可能存在的问题.

数组 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