排序算法——插入排序


title: 算法基础——排序算法
abbrlink: 2213989909
date: 2019-11-17 21:06:25
categories:

  • Algorithms
    tags:
  • 排序算法

排序

插入排序

  • 插入排序由N-1趟排序组成

代码

/** * 插入排序 * * @param <E> * @param a */
	public static <E extends Comparable<? super E>> void insertSort(E[] a) {
		int j;
		for (int p = 1; p < a.length; p++) {
			E tmp = a[p];
 // compareTo(T o)
// 比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象,则分别返回负整数、零或正整数。
			for (j = p; j > 0 && tmp.compareTo(a[j - 1]) < 0; j--) {
				a[j] = a[j - 1];

			}
			a[j] = tmp;
		}
	}

原理

对于p =1到 N-1趟,插入排序保证从位置 0 到位置 p上的元素为已排序状态。

对于p =1到 N-1趟,插入排序保证从位置 0 到位置 p上的元素为已排序状态。

策略我们将位置p上的元素左移,直到他在前面的p-1个元素中找到正确位置

在第13 -17行,实现了数据的移动而没有明显地使用交换。位置p上的元素存储在tmp,而所有更大的元素都向右移动一个位置,然后tmp放置在正确的位置上

分析

由于嵌套排序,所以每一个都花费N次迭代,因此插入排序为O(N2)

而输入数据已经预先排序,则时间为O(N),因为内层for循环检测判定不成立而终止。而实际上,平均情形为O(N2)

两个定理

  • N个互异数的数组的平均逆序数是N(N-1)/4
  • 通过交换相邻元素进行排序的任何算法的平均都需要Ω(N2)时间

希尔排序(缩减增量排序)

  • 通过比较相距一定间隔的元素工作
  • 各趟比较所用的距离随算法的进行而减少,直到只比较相邻元素的最后一趟排序为止。
public static <E extends Comparable<? super E>> void shellsort(E [] a) {
		int j;
		for(int gap = a.length/2;gap>0;gap/=2) {
			for(int i = gap;i<a.length;i++) {
				E tmp = a[i];
				for(j =i;j>=gap && tmp.compareTo(a[j-gap])<0;j-=gap) {
					a[j] = a[j-gap];
				}
				a[j] =tmp;
			}
		}
	}
全部评论

相关推荐

今天 13:16
湖南工学院 Java
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 10:39
一个证都没&nbsp;我能填什么
程序员小白条:别人有,你为什么没有,还是这个道理,社会就是比较,竞争,淘汰,你要安逸,那么就要做好淘汰的准备
点赞 评论 收藏
分享
07-07 12:25
门头沟学院 Java
程序员牛肉:你这个智邮公司做的就是那个乐山市税务系统的服务吗?
点赞 评论 收藏
分享
流浪的神仙:无恶意,算法一般好像都得9硕才能干算法太卷啦
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务