数据结构排序之插入排序

3/8/2017来源:ASP.NET技巧人气:294

package sort; /* 最简单的排序算法之一是插入排序(insertion sort).插入排序由N-1躺排序组成。对于 p = 1到N -1 趟,插入排序保证从位置0到位置p上的元素为已排序状态。插入排序利用了这样的 事实:已知位置0到位置p - 1 上的元素处于排过序的状态。 例子: 原始数组:34 8 64 51 32 21 移动的位置 p = 1趟之后:8 34 64 51 32 21 1 p = 2趟之后:8 34 64 51 32 21 0 p = 3趟之后:8 34 51 64 32 21 1 p = 3趟之后:8 32 34 51 64 21 3 p = 3趟之后:8 21 32 34 51 64 4 在地p趟,我们将位置p上的元素向左移动,知道他们在前p + 1 个元素中的正确位置被找到的地方。 运行时间: 由于每次嵌套循环的每一个都花费N次迭代, 因此插入排序为0(N2),而且这个界是精确的 假如已经事先排好序的话,那么运行时间就是0(N)为线性时间,因为第二个for循环并没有生效 */ public class Insert_sort { public static<AnyType extends Comparable<? super AnyType>> void insertionSort(AnyType[] a){ int j; for(int p = 1; p < a.length; p++){ AnyType tmp = a[p]; for(j = p; j > 0 && tmp.compareTo(a[j - 1]) < 0; j--) a[j] = a[j - 1]; //元素都要往后挪 a[j] = tmp; } } public static void main(String[] args) { Integer[] a = new Integer[]{34, 8, 64, 51, 32, 21}; insertionSort(a); for(int number : a) System.out.PRint(number + ","); } }