Java实现折半插入排序算法的示例代码

算法简介

折半插入排序（Binary Insertion Sort）是插入排序算法的一种变体，它通过使用折半查找来减少比较和移动的次数，从而提高算法的效率。算法的时间复杂度为O(n^2)。

示例代码

下面是Java实现折半插入排序算法的示例代码：

public static void binaryInsertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int left = 0;
        int right = i - 1;
        int num = arr[i];
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (num < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        if (left != i) {
            arr[left] = num;
        }
    }
}

示例说明

假设要对数组arr进行排序，排序的范围为[0, arr.length-1]。

1. 初始化i=1，将arr[1]插入到有序子序列arr[0]中。此时，有序子序列为[1]。

2. 将arr[2]插入到有序子序列arr[0, 1]中。首先，使用折半查找找到左边界。此时，有序子序列为[1, 2]。

3. 将arr[3]插入到有序子序列arr[0, 2]中。首先，使用折半查找找到左边界。此时，有序子序列为[1, 2, 3]。

4. 以此类推，直到整个数组有序。

另一个示例

下面是另一个示例，假设要对数组arr进行排序，排序的范围为[l, r]。

public static void binaryInsertionSort(int[] arr, int l, int r) {
    for (int i = l + 1; i <= r; i++) {
        int left = l;
        int right = i - 1;
        int num = arr[i];
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (num < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        if (left != i) {
            arr[left] = num;
        }
    }
}

这个示例中，排序的范围为[l, r]，因此需要使用两个参数来限定排序的范围。其他部分与前面的示例相同。

总结

折半插入排序算法是一种基于插入排序的优化算法，它通过使用折半查找来减少比较和移动的次数，从而提高了算法的效率。使用该算法可以在实际应用中对大量数据进行高效排序。