插入排序

插入排序算法思想

将第N个数插入到有序的[0...N-1]里，因为[0...N-1]已经有序，从第N个元素开始依次相互比较，发现后者比前者大就交换。

插入排序算法实现

 public static void main(String[] args) {
        int[] arr = {-2, 1, 33, 4, 5, 0, 0, -1, 45, 908, 3};

        int[] insertSort = insertSort(arr);
        for (int i : insertSort) {
            System.out.print(i + "  ");
        }
        System.out.println();
        int[] insertSortByChange = insertSortByChange(arr);
        for (int i : insertSortByChange) {
            System.out.print(i + "  ");
        }
    }

    /**
     * 插入排序
     *
     * @param arr
     * @return
     */
    private static int[] insertSort(int[] arr) {
        if (arr.length == 0) return null;
        if (arr.length == 1) return arr;
        int N = arr.length;
        for (int i = 1; i < N; i++) {
            int j;
            //这个是我的实现思路：主要是用第i个和前面i-1个比较发现比自己大的就把该元素向右移动一个位置，
            // 直到没有比自己大就跳出，然后把自己放入当前位置+1里
            int temp = arr[i];
            for (j = i - 1; j >= 0; j--) {
                if (arr[j] > temp) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = temp;


        }
        return arr;
    }

    /**
     * 通过交换的方式 推荐使用
     *
     * @param arr
     * @return
     */
    private static int[] insertSortByChange(int[] arr) {
        if (arr.length == 0) return null;
        if (arr.length == 1) return arr;
        int N = arr.length;
        for (int i = 1; i < N; i++) {
            int j;
            // 算法关键：第i个和前面i-1个比较，发现比自己大就交换，
            // i-1和i-2比较发现比自己大就交换.........否则就退出
            for (j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    break;
                }

            }

        }
        return arr;
    }

算法复杂度

1. 平均时间算法复杂度为O(N^2)
2. 最坏时间复杂度为O(N^2)
3. 最好时间复杂度为O(N)
4. 空间复杂度为O(1) 不需要额外空间

算法稳定性

1.这个算法是稳定的，不会因为移动影响两个相同元素的位置

想看更多完整版请点击：插入排序