算法-插入法排序

2022-3-31 diaba 算法

package com.jiucaiyuan.net.algrithm.sort;

/**
 * <pre>
 * 插入法排序
 * i从0~N-1
 * 处理0~i位置上有序，检查i-1和i是否有序，如果没有，交换，再检查i-2和i-1是否有序
 * （效果就是当前i个元素往前找，找到合适自己的位置）
 * 排序结果是升序数组
 * 时间复杂度O(N^2)    空间复杂度O(1)
 *
 * 数据状况不同，时间复杂度不同
 * 最差的情况 7 6 5 4 3 2 1 时：时间复杂度O(N^2)    空间复杂度O(1)
 * 最好的情况 1 2 3 4 5 6 7 时：时间复杂度O(N)    空间复杂度O(1)
 * </pre>
 *
 * @Author jiucaiyuan  2022/3/25 21:48
 * @mail services@jiucaiyuan.net
 */

public class InsertSort {

    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //0位置时是有序的，所以直接从1位置开始处理
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
                swap(arr, j - 1, j);
            }
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 8, 3, 5, 7, 2, 7, 8, 12, 4};
        insertionSort(arr);
        print(arr);
    }

    private static void print(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int a : arr) {
            System.out.print(a + "\t");
        }
        System.out.println();
    }
}

« 算法-堆排序 | 算法-冒泡法排序»

发表评论：