java-插入排序及其时间复杂度

java-插入排序及其时间复杂度

 

插入排序接口

package com.test14;

public class Insert {
    public static void insert(Comparable[] c) {
        for (int i = 0; i < c.length; i++) {
            for (int j = i; j > 0; j--) {
                if (getMax(c[j - 1], c[j])) {
                    exch(c, j - 1, j);
                } else {
                    break;
                }
            }
        }
    }

    public static Boolean getMax(Comparable c1, Comparable c2) {
        return c1.compareTo(c2) > 0;
    }

    public static void exch(Comparable[] c, int i, int j) {
        Comparable temp;
        temp = c[i];
        c[i] = c[j];
        c[j] = temp;
    }


}

测试类

package com.test14;

import java.util.Arrays;

//掺入排序
public class Test {
    public static void main(String[] args) {
        Integer[] arr={5, 6, 1, 9, 3, 1, 6, 5, 19};
        System.out.println(Arrays.toString(arr));
        Insert.insert(arr);
        System.out.println(Arrays.toString(arr));

    }
}

时间复杂度  O(n^2)