文档章节

选择排序,插入排序,希尔排序的java实现

Amui
 Amui
发布于 2015/10/08 19:36
字数 1120
阅读 23
收藏 1

选择排序:

简单的选择排序思想:

首先,找到数组中最小(/最大)的那个元素,将它与数组中的第一个(/最后一个)元素交换位置,再次,在剩下的元素中找最小(/大)的元素,将其与数组的第二个(/倒数第二个)元素交换位置。如此往复。

其算法复杂度为O(n^2)

有两个鲜明特点:

1.运行时间与数据的状态无关。一个有序的数组或键值全部相等的数组和一个元素随机排列的数组所用的排序时间一样长。为了找出最小(大)的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。(缺点)

2.数据移动是最少的。每次交换都只会改变两个数组元素的值,因此选择排序用了N次交换。(交换次数和数组的大小是线性关系)

 

public class Selection {
	public static void sort(Comparable[] a){
		int index;
		for(int i = 1; i <= a.length; i++){
			index = 0;
			for(int j = 1; j <= a.length - i; j++){
				if(less(a[index],a[j])){
					index = j;
				}
			}
			exch(a, index, a.length-i);
		}

		/* 或者以下实现
		int N = a.length;
		for(int i = 0; i < N; i++){
			int min = i;
			for(int j = i + 1; j < N; j++){
				if(less(a[j],a[min])) min = j;
			}
			exch(a, i, min);
		}
		*/
	}
	private static boolean less(Comparable v, Comparable w){
		return v.compareTo(w) < 0;
	}
	private static void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
}

 

 

 

插入排序:

插入排序的思想:

类似人们整理手中的扑克牌,将每一张牌插入到其他已经有序的牌中的适当位置。

类似选择排序,当前索引左边的所有元素都是有序的,但它们最终位置还不确定,为了给更小的元素腾出空间,它们可能会被移动。当索引到达数组的右端时,数组排序就完成了。

插入排序对于几种典型的部分有序的数组是十分高效的:

1.数组中每个元素距离它的最终位置都不远

2.一个有序的大数组接一个小数组

3.数组中只有几个元素的位置不正确

总之,插入排序对于部分有序的数组十分高效,也很适合小规模数组。

 

public class Insertion {
	public static void sort(Comparable[] a){
		//将a[] 按升序排列
		int N = a.length;
		for(int i = 1; i < N; i++){
			for(int j = i; j > 0; j--){
                if(less(a[j], a[j - 1]){
                    exch(a, j, j - 1);
                } else {
                    break;
                }
			}
		}
	}
	
	private static boolean less(Comparable v, Comparable w){
		return v.compareTo(w) < 0;
	}
	private static void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
}

 

 

 

希尔排序:

对于大规模乱序数组插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一端。希尔排序为了加快速度简单地改进了插入排序,交换不相邻的元素以对数组的局部进行排序,并最终用插入排序将局部有序的数组排序。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的,这样的数组被称为h有序数组

在进行排序时,如果h很大,就能将元素移动到很远的地方,为实现更小的h有序创造方便。用这种方式,对于任意以1结尾的h序列,我们都能够将数组排序。这就是希尔排序。

排序之初,各个子数组都很短,排序之后子数组都是部分有序的,这两种情况都很适合插入排序。子数组部分有序的程度取决于递增序列的选择。

希尔排序比插入排序和选择排序要快得多。

 

public class Shell {
	public static void sort(Comparable[] a){
		//将a[] 升序排列
		int N = a.length;
		int h = 1;
		while(h < N/3){
			h = 3 * h + 1; //1, 4, 13, 40, 121, ...
		}
		while(h >= 1){
			//将数组变为h有序
			for(int i = h; i < N; i++){
				//将a[i]插入到a[i-h],a[i-2*h],a[i-3*h]...之中
				for(int j = i; j >= h&& less(a[j],a[j-h]); j -= h){
					exch(a, j, j-h);
				}
			}
			h = h/3;
		}
	}
	
	private static boolean less(Comparable v, Comparable w){
		return v.compareTo(w) < 0;
	}
	private static void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
}

 

记录一篇写得超级棒的关于经典排序算法的博客:

https://www.cnblogs.com/onepixel/articles/7674659.html

 

© 著作权归作者所有

Amui
粉丝 5
博文 78
码字总数 40874
作品 0
广州
程序员
私信 提问
推荐十大经典排序算法,再也不用担心面试了!

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:...

Java面经
07/15
134
0
java排序之快速排序、归并排序、基数排序

前两篇说了Java排序中的冒泡、选择、插入、希尔等排序算法,今天就探讨一下剩下的三种常用排序。 快速排序: 当要求时间最快时,就可以用快速排序算法。 选择第一个数为p,小于p的数放在左边...

野小疯
2018/06/05
50
0
java 通配符的应用— java 排序算法

这几天无聊,又重新学起java的排序算法,为DualPivotQuickSort做准备。为了更好地适应各种情况,我们选择使用通用类型T和通配符的上下界来实现,同时这次谈的是对数组对象的排序。如果你对j...

天地一MADAO_
2014/03/02
117
0
程序员必知的8大排序(java实现)

8种排序之间的关系:  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好...

小帅帅丶
2015/01/09
364
7
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
1K
5

没有更多内容

加载失败,请刷新页面

加载更多

JS其他类型值转化为Boolean类型规则

本文转载于:专业的前端网站➤JS其他类型值转化为Boolean类型规则 由于最近在笔试的时候,发现好多关于其他类型转化为Boolean类型的题目,因此总结一下! 一、String类型转化为Boolean 1.转化...

前端老手
33分钟前
4
0
EurekaClient自动装配及启动流程解析

在上篇文章中,我们简单介绍了EurekaServer自动装配及启动流程解析,本篇文章则继续研究EurekaClient的相关代码 老规矩,先看spring.factories文件,其中引入了一个配置类EurekaDiscoveryClie...

Java学习录
38分钟前
6
0
析构函数是否必须为虚函数?为何?

p517 在C++中,基类指针可以指向一个派生类的对象。如果基类的析构函数不是虚函数,当需要delete这个指向派生类的基类指针时,就只会调用基类的析构函数,而派生类的析构函数无法被调用。容易...

天王盖地虎626
39分钟前
5
0
【TencentOS tiny】深度源码分析(7)——事件

引言 大家在裸机编程中很可能经常用到flag这种变量,用来标志一下某个事件的发生,然后在循环中判断这些标志是否发生,如果是等待多个事件的话,还可能会if((xxx_flag)&&(xxx_flag))这样子做...

杰杰1号
42分钟前
8
0
聊聊nacos client的ServerHttpAgent

序 本文主要研究一下nacos client的ServerHttpAgent HttpAgent nacos-1.1.3/client/src/main/java/com/alibaba/nacos/client/config/http/HttpAgent.java public interface HttpAgent { ......

go4it
49分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部