频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
排序算法(Java语言)——插入排序
2015-08-21 08:24:46         来源:Zachary's Blog  
收藏   我要投稿

最简单的排序算法之一是插入排序(insertion sort)。插入排序由N-1趟排序组成。对于p=1到N-1趟,插入排序保证从位置0到p上的元素为已排序状态。插入排序利用了这样的事实:已知位置0到位置p-1上的元素为已排序状态。

由于嵌套循环的每一个都花费N次迭代,因此插入排序为O(N^2),而且这个界是精确的,因为以反序的输入可以达到该界。精确计算指出,循环中元素的比较次数对于p的每个值最多是p+1次。对所有的p求和得到次数为2+3+4+5+...=O(N^2)。另一方面,如果输入数据已预先排序,那么运行时间为O(N),因为内层for循环的检测总是立即排定不成立而终止。事实上,如果输入几乎被排序,那么插入排序将运行得很快。

以下为相关代码实现:

 

import java.util.Random;

public class InsertionSort {
	public static > void insertSort(
			AnyType[] array) {
		int j;
		for (int p = 1; p < array.length; p++) {
			AnyType tmp = array[p];
			for (j = p; j > 0 && tmp.compareTo(array[j - 1]) < 0; j--) {
				array[j] = array[j - 1];
			}
			array[j] = tmp;
		}
	}

	public static void main(String[] args) {
		Random random = new Random();
		Integer[] list = new Integer[20];
		for (int i = 0; i < 20; i++) {
			list[i] = random.nextInt(20);
			System.out.print(list[i] + " ");
		}
		insertSort(list);
		System.out.println("\nAfter sorting:");
		for (Integer integer : list) {
			System.out.print(integer + " ");
		}
	}
}

执行结果:

 

5 9 4 3 3 13 16 14 14 9 4 15 7 2 10 18 12 14 6 10
After sorting:
2 3 3 4 4 5 6 7 9 9 10 10 12 13 14 14 14 15 16 18

版权声明:本文为博主原创文章,未经博主允许不得转载。

点击复制链接 与好友分享!回本站首页
相关TAG标签 算法 语言
上一篇:设计模式之观察者模式
下一篇:struts2-ajax-页面的自动刷新
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站