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(N²)

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

两个定理

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

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

• 通过比较相距一定间隔的元素工作
• 各趟比较所用的距离随算法的进行而减少，直到只比较相邻元素的最后一趟排序为止。

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;
			}
		}
	}