文档章节

插入排序和希尔排序

sitaluoduoxi
 sitaluoduoxi
发布于 2016/07/26 22:14
字数 654
阅读 0
收藏 0

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,

插入排序的基本思想是:每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

 

public static void sortInsert(int[] datas){
		
		int N = datas.length;
		for (int i = 1; i < N; i++) {
			int j = i;
			if(datas[j] < datas[j-1]){
				int temp = datas[j];
				while( j > 0 && temp < datas[j-1]){
					datas[j] = datas[j-1];
					j --;
				}
				datas[j] = temp;
			}
			printArr(datas);
			System.out.println();
		}
		
	}

 

 

 

当输入数据已经排好序时,运行时间为O(n);内能的循环检测判断条件总是不成立;

当输入全部逆序时,datas[j] = datas[j-1] 执行的次数为 1+2+3....+n^2 = O(n^2)

 

希尔排序:

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,
当增量减至1时,整个文件恰被分成一组,算法便终止。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:
插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。
但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。

基本思想:
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。
先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量=1( < …<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

 

public static void sortSheel(int[] datas){
		int N = datas.length;
		for (int gap = N /2; gap > 0;  gap /= 2) {
			for(int i = gap; i< N; i++){
				int temp = datas[i];
				int j = i;
				for( ; j >= gap &&  temp < datas[j - gap]; j -= gap){
					datas[j] = datas[j-gap];
				}
				datas[j] = temp;
			}
			printArr(datas);
			System.out.println();
		}
	}

测试结果:

 

60,78,2,7,5,87,34,46,23,123,32,53,45,9,99,88,65,[原数组]
23,78,2,7,5,9,34,46,60,123,32,53,45,87,99,88,65,[gap=8后结果]
5,9,2,7,23,78,32,46,45,87,34,53,60,123,99,88,65,[gap=4后结果]
2,7,5,9,23,46,32,53,34,78,45,87,60,88,65,123,99,[gap=2后结果]
2,5,7,9,23,32,34,45,46,53,60,65,78,87,88,99,123,[gap=1后结果]


 

 

© 著作权归作者所有

sitaluoduoxi
粉丝 0
博文 33
码字总数 24992
作品 0
广州
后端工程师
私信 提问
Java数据结构与算法(六)-希尔排序

一、希尔排序的产生 希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名...

FantJ
2017/12/21
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Bash 和 Python 编程语言优缺点分析

Bash 和 Python 是大多数自动化工程师最喜欢的编程语言。它们都各有优缺点,有时很难选择应该使用哪一个。所以,最诚实的答案是:这取决于任务、范围、背景和任务的复杂性。 让我们来比较一下...

xiangyunyan
30分钟前
4
0
Kubernetes从懵圈到熟练:读懂这一篇,集群节点不下线

排查完全陌生的问题,完全不熟悉的系统组件,是售后工程师的一大工作乐趣,当然也是挑战。今天借这篇文章,跟大家分析一例这样的问题。排查过程中,需要理解一些自己完全陌生的组件,比如sys...

阿里云云栖社区
35分钟前
10
0
解决exe4打包出现的问题

https://blog.csdn.net/gem_yaorao/article/details/48626155

南桥北木
51分钟前
1
0
SpringBoot高级篇JdbcTemplate之数据更新与删除

前面介绍了JdbcTemplate的插入数据和查询数据,占用CURD中的两项,本文则将主要介绍数据更新和删除。从基本使用上来看,姿势和前面的没啥两样 <!-- more --> I. 环境准备 环境依然借助前面一...

小灰灰Blog
今天
3
0
Filecoin 编译问题

https://github.com/filecoin-project/go-filecoin/issues/2503 Error go run ./build build command from root I've faced on this error Building go-filecoin...git log -n 1 --forma......

怎当她临去时秋波那一转
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部