当前位置:首页 > 编程教程 > Java编程 > 希尔排序之插入排序法(Java实现)

希尔排序之插入排序法(Java实现)

2017-07-17 19:08:08[Java编程]点击数:作者:warmwine的博客来源: 网络
随机为您推荐的文章:Java面试相关题目 (第一节)

一、cookie 和session 的区别: 1、cookie数据存放在客户的浏览器上,session数据放在服务器上。 2、cookie不是很安全,别人可以分析存放在本地的COOKIE并进行COOKIE欺骗考虑到

希尔排序法(Shell Sort)属于插入类排序,又称为缩小增量排序。它对直接插入排序有了很大的改进,是直接插入排序的增强版。

希尔排序的基本思想是:

把线性表按步长gap分组,共有gap个组。

每组线性表中有arr.length/gap个元素,每个元素相邻gap。接下来对每组线性表采用直接插入排序方法进行排序。

随着步长逐渐减小,所分成的组包含的元素越来越多,当步长的值减小到 1 时,整个数据合成为一组,构成一组有序记录,则完成排序。


下图是本人对希尔排序思想所做的图示:

希尔排序之插入排序法(Java实现)

步长gap的选择决定着希尔排序的最终效率。只要最终步长为1任何步长序列都可以工作(且步长要小于数组长度)。算法最开始以一定的步长进行排序。随着步长gap的逐渐减小,继续以一定步长进行排序,最终算法以步长为1进行排序。当步长为1时,算法变为插入排序,这就保证了数据一定会被排序。

希尔排序的时间复杂度,与步长的关系如下图:

希尔排序之插入排序法(Java实现)

java代码如下:

public class ShellSort {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		int arr[] = {4,9,2,3,5,10,8,6,1};
		shellsort(arr);
		for(int a : arr)
			System.out.print(a+" ");
	}
	
	public static void shellsort(int arr[]){
		//逐渐缩小步长。此处gap以每次除以2进行减少
		for(int gap = arr.length/2 ; gap >=1 ; gap /= 2){ //gap为步长
			//直接排序法
			for(int i = gap ; i < arr.length ; i++){
				int temp = arr[i];
				while( i-gap >= 0 && arr[i-gap] > temp){
					arr[i] = arr[i-gap];
					i = i-gap;
				}
				arr[i] = temp;
			}
		}
	}
}

以上就是希尔排序之插入排序法(Java实现)的全文介绍,希望对您学习和使用java编程有所帮助.

这些内容可能对你也有帮助

更多Java编程可查看Java编程列表页。

TAGS: 希尔   Java