public class InsertionSort {
    
    /**
     * 插入排序（基础版本，使用交换实现插入）
     */
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                j--;
            }
        }
    }
    
    /**
     * 插入排序（优化版本，使用移动代替交换）
     */
    public static void sortOptimized(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // 将大于 key 的元素向后移动
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 插入到正确位置
            arr[j + 1] = key;
        }
    }
    
    /**
     * 插入排序（泛型版本）
     */
    public static <T extends Comparable<T>> void sortGeneric(T[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            T key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j].compareTo(key) > 0) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    
    /**
     * 插入排序（带二分查找优化）
     * 使用二分查找减少比较次数，但移动次数不变
     */
    public static void sortBinary(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            // 使用二分查找找到插入位置
            int left = 0, right = i;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (arr[mid] <= key) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            // 移动元素
            for (int j = i; j > left; j--) {
                arr[j] = arr[j - 1];
            }
            arr[left] = key;
        }
    }
}