算法:高级排序1-希尔排序

高级排序1-希尔排序

思路

• 1.在插入排序的基础下只用增量减量的方式
• 2.最后一步减量后序列为1,执行普通的插入排序

ShellSort.java 具体实现

public class ShellSort {

	public static int array[] = { 4, 21, 2, 4, 6, 88, 9, 11, 2, 45, 7, 8, 12, 22, 33, 44, 1, 2, 33, 44, 55, 7, 11, 12, 10 };

	public static void main(String[] args) {
		int out, in, temp;

		int h = 1;
		while (h <= array.length / 3) {	//1
			h = h * 3 + 1;
		}

		while (h > 0) {	//2
			for (out = h; out < array.length; out++) {
				temp = array[out];
				in = out;
				while (in > h - 1 && array[in - h] > temp) {	//3
					array[in] = array[in - h];
					in -= h;	//4
				}
				array[in] = temp;	//5
			}
			h = (h - 1) / 3;	//6
		}
		
	}

}

输出： 1 2 2 2 4 4 6 7 7 8 9 10 11 11 12 12 21 22 33 33 44 44 45 55 88

说明

• 1.增量{1,4,13,40,121,364,1093…}
• 2.减量一直到等于1为止
• 3.找到自己的之前增量的位置比较大小
• 4.减量
• 5.插入该位置
• 6.减量{…1093,364,121,40,13,4,1}

注:该内容为Java数据结构和算法读后学习感悟

其他相关文章

递归-归并排序

高级排序2-快速排序

划分排序

简单排序3-插入排序

简单排序2-选择排序

简单排序1-冒泡排序

赏

谢谢你的激励

微信