即不停的在值之间插入新的值,最终完成排序,可以与输入有所互动,例如一个排序好的数组所需时间比无序的快的多
平均情况下插入排序需要N平方/4比较 N平方/4交换,最坏情况 N平方/2比较和N平方/2交换,最好时候,我们只需要N-1次比较和0次交换,非常适合于部分有序数组:数组中每一个元素距离最终位置都不远,一个有序大数组接着一个小数组,数组中只有部分元素不正确
代码如下
|
package InsertSort;
/** * * @author Heaven * 插入排序就是在我们一边第一层进行基础遍历 * 然后第二层之中,我们将第一层的i和之前已经排序的进行比较,然后插进去之前排序好的 */ public class InsertSort { public static void sort(Comparable[] a) {//进行排序的方法 int N =a.length; for (int i = 1; i < N; i++) {//进行第一段排序 for (int j = i ;j >0 && less(a[j], a[j-1]); j–) { exch(a, j, j-1);//进行循环排序 } } } public static boolean less(Comparable a,Comparable a2) {//对元素进行比较 return a.compareTo(a2) < 0; } private static void exch(Comparable[] a,int i,int j) {//进行交换 Object n =a[i]; a[i] = a[j]; a[j] = (Comparable<Object>) n; } private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { System.out.println(a[i]+” “); }//进行输出 } public static boolean isSorted(Comparable[] a) {//测试是否排序 for (int i = 1; i < a.length; i++) { if (less(a[i],a[i-1])) { return false; } } return true; } } |