Java经典排序算法之二分插入排序详解

什么是二分插入排序？

二分插入排序是插入排序的升级版，它采用二分查找来寻找插入位置，从而提高插入操作的效率。

与插入排序不同的是，插入排序是将待排序的元素插入到已排好序的序列中，找到正确的插入位置需要比较多的次数，时间效率较低。而二分插入排序是通过二分查找的方式来寻找插入的位置，可以减少比较次数，提高时间效率。

二分插入排序的实现原理

二分插入排序的实现过程如下：

1. 首先假设第一个元素已经是有序的。
2. 依次将后面的元素插入到前面已排好序的序列中。
3. 在每次插入时，采用二分查找来寻找插入位置。
4. 将该元素插入到正确的位置，并将已排序序列中的所有大于该元素的元素向后移动一个位置。

二分插入排序的代码实现

以下是Java语言实现二分插入排序的代码：

public static void binaryInsertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int temp = arr[i];
        int left = 0;
        int right = i - 1;
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (arr[mid] > temp) {
                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] = temp;
        }
    }
}

二分插入排序的时间复杂度

二分插入排序的时间复杂度为O(nlogn)。

二分查找的时间复杂度为O(logn)，插入操作时，需要将已排序序列中的所有大于该元素的元素向后移动一个位置，最坏情况下需要移动n/2次，时间复杂度为O(n)。因此，综合起来，时间复杂度为O(nlogn)。

示例说明

假设有一个无序数组arr，其元素为[3, 2, 1, 5, 4]，使用二分插入排序进行排序的过程如下：

1. 假设第一个元素3已经是有序的。
2. 将第二个元素2插入到前面已排好序的序列中。使用二分查找，插入位置为0，将2插入到该位置：[2, 3, 1, 5, 4]。
3. 将第三个元素1插入到前面已排好序的序列中。使用二分查找，插入位置为0，将1插入到该位置：[1, 2, 3, 5, 4]。
4. 将第四个元素5插入到前面已排好序的序列中。使用二分查找，插入位置为3，将5插入到该位置：[1, 2, 3, 5, 4]。
5. 将第五个元素4插入到前面已排好序的序列中。使用二分查找，插入位置为3，将4插入到该位置：[1, 2, 3, 4, 5]。

经过以上排序过程，最终得到的有序数组为[1, 2, 3, 4, 5]。