package sort;

/**
 * InsertionSortDemo.java
 * ------------------------------------------------------
 * 插入排序
 *
 * 统一视角：分治策略
 * - 分：将数组划分为已排序部分和未排序部分；
 * - 治：遍历未排序部分，解决单元素归位问题，增大已排序区间；
 *
 * 或者，更具体点：
 * - 分：划分固定比例 1 : (n-1)，即 [已排序 | 未排序]；
 * - 治：先解决单元素归位问题，再扩大已排序区间；
 * - 性能：由于划分始终是线性 1 : n-1，路径深度为 n，故复杂度为 O(n^2)；
 *
 *
 * 核心逻辑：
 * - 分：将数组划分为已排序部分和未排序部分；
 * - 治：遍历未排序部分，将未排序部分的首元素插入到已排序部分的正确位置
 *
 * ------------------------------------------------------------------------------------
 * 状态变化追踪
 *
 * 初始
 * - 已排序部分：[0, 0]
 * - 未排序部分：[1, n-1]
 *
 * 第1轮(i=1)
 *
 * 操作：遍历未排序部分[1, n-1]，将未排序部分的首元素插入到已排序部分的正确位置
 *
 * 结果
 * - 已排序部分：[0, 1]
 * - 未排序部分：[2, n-1]
 *
 * 第2轮(i=2)
 *
 * 操作：遍历未排序部分[2, n-1]，将未排序部分的首元素插入到已排序部分的正确位置
 *
 * 结果
 * - 已排序部分：[0, 2]
 * - 未排序部分：[3, n-1]
 *
 * 第k轮(i=k)
 *
 * 操作：遍历未排序部分[k, n-1]，将未排序部分的首元素插入到已排序部分的正确位置
 *
 * 结果
 * - 已排序部分：[0, k]
 * - 未排序部分：[k+1, n-1]
 *
 * 第n-1轮(i=n-1)
 *
 * 操作：遍历未排序部分[n-1, n-1]，将未排序部分的首元素插入到已排序部分的正确位置
 *
 * 结果
 * - 已排序部分：[0, n-1]
 * - 未排序部分：[n, n-1]，空集
 *
 * 算法结束后
 *
 * 结果
 * - 已排序区间：[0, n-1]
 * - 未排序区间：[n, n-1]，空集
 *
 * -------------------------------------------------------------------------------------------
 * 性质
 * - 稳定性？
 * - 原地性？
 * - 自适应性？
 * - 在线性？
 *
 *
 */
public class InsertionSortDemo {

    /**
     * 插入排序基础版
     * @param arr
     * ----------------------------------------------------------
     * 核心逻辑：取出未排序区间的首个元素，将其插入到已排序区间的正确位置
     *
     * 请思考：
     * - 外层循环为什么执行`n-1`轮？
     * - 内层循环为什么是从右向左遍历？
     * - 优化的方向有哪些？
     *
     * ----------------------------------------------------------
     */
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = key;
        }
    }

    /**
     * 插入排序低效版-基于交换
     * @param arr
     * ---------------------------------------------------
     * 核心逻辑：取未排序区间的首个元素，将其插入到已排序区间的正确位置
     *
     * 反复交换相邻元素，将当前元素移动到正确位置(每次移位需要3次赋值)
     */
    public static void insertionSortSwapBased(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                // Adjacent swap: 3 assignments per swap
                int tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;
                j--;
            }
        }
    }

    /**
     * 插入排序优化版-基于移位
     * @param arr
     * ------------------------------------------------------
     * 核心逻辑：取未排序区间的首个元素，将其插入到已排序区间的正确位置
     *
     * 先缓存待插入元素key，然后将比key大的元素统一向右移动一位，最后将key写入到正确位置
     */
    public static void insertionSortShiftBased(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {               // Start from second element
            int key = arr[i];                       // Element to be inserted
            int j = i - 1;                          // Start of sorted portion

            // Shift elements to the right until correct position found
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];                // One assignment per moved element
                j--;
            }

            arr[j + 1] = key;                       // Single final write of key
        }
    }


    /**
     * 插入排序优化版-二分查找来定位插入位置
     * @param arr
     */
    public static void insertionSortBinarySearch(int[] arr) {
        int n = arr.length;

        for (int i = 1; i < n; i++) {
            int key = arr[i];

            // Binary search to find insertion position within [0, i-1]
            int insertPos = binarySearch(arr, 0, i - 1, key);

            // Shift elements from insertPos to i-1 one position right
            for (int j = i; j > insertPos; j--) {
                arr[j] = arr[j - 1];
            }

            arr[insertPos] = key;
        }
    }

    private static int binarySearch(int[] arr, int low, int high, int key) {
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;  // Insertion position
    }


    public static void insertionSortIterative(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = key;
        }
    }

    public static void insertionSortRecursion(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        insertionSortRecursion(arr, 1);
    }

    private static void insertionSortRecursion(int[] arr, int start) {
        int n = arr.length;
        if (start >= n-1) {
            return;
        }
        int key = arr[start];
        int j = start - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;

        insertionSortRecursion(arr, start+1);

    }


}