查找算法——二分插入排序

一、二分插入排序

学这个之前，我们要知道二分查找和直接插入排序!

1.1.二分插入排序简介

• 二分插入排序也叫作折半插入排序，其实就是直接插入排序的一直改进，运用了二分的思想。
• 所谓二分插入排序，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。这样在数据量很大的时候，算法的效率就会很高！

1.2.二分插入排序思路

💡💡思路：

1. 分为有序区和无序区
2. 最初有序区没有元素，我们可以从无序区拿出元素放入，放入的元素已经有序
3. 接下来先与有序区最后一个元素进行比较，如果大于最后一个元素，则可以直接归入有序区，如果小于最后一个元素，则对有序区进行二分的运用
4. 有序区分为left，right，mid，mid= left +（right-left)/2
5. 无序区的第一个元素与有序区的mid中间值进行比较，如果大于mid，则插在mid右边
6. 如果小于，则对mid值左边区间再进行依次的二分，直到确定插入位置

1.3.时间复杂度

💡💡

• 最好的情况：最好的情况下，列表元素已按关键字从小到大有序排列，每次只需要与前面有序元素的最后一个元素比较1次，移动2次元素，总的比较次数为n-1，元素移动次数为2(n-1)，算法复杂度为O(n)
• 最坏的情况：坏情况下每一行代码都被执行，即全部反向有序，最坏时间复杂度为O(n^2)
• 综合以上，直接插入排序的时间复杂度为O(n^2)

1.4.空间复杂度

💡💡：

算法执行过程中仅需要几个额外的变量，所以空间复杂度为O(1)

1.5.代码实现

C++代码：

#include <iostream>
using namespace std;

void Array(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i++)
        printf("%4d", arr[i]);
    printf("\n");
}
int main()
{
    int arr[] = {5,9,23,6,9,18,2,66};
    int temp, i, j, low, high, mid, n;
    n = sizeof(arr) / sizeof(arr[0]);
    Array(arr, n);
    printf("折半插入排序:\n");
    for (i = 1; i < n; i++)
    {
        temp = arr[i];
        for (low = 0, high = i - 1; high >= low;)
        {
            // 防止溢出
            mid = left +(low - high) / 2;
            if (temp < arr[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (j = i - 1; j >= low; j--)
            a[j + 1] = a[j];
        arr[low] = temp;
        Array(arr, n);
    }
 
}

Python代码：

def InsertSort(arr):
    for i in range(1, len(arr)):
        tmp = arr[i]
        low = 0
        high = i - 1
        # 将范围折半再查找
        while low <= high:
            mid = int(low + (high - low) / 2)
            if tmp > arr[mid]:
                low = mid + 1
            else:
                high = m - 1
        # arr[high]的元素比tmp小
        j = i - 1
        while j >= high + 1:
            arr[j + 1] = arr[j]
            j -= 1
        # 将tmp放在arr[high]之后
        arr[high + 1] = tmp
 
if __name__ == "__main__":
    arr = [5,9,23,6,9,18,2,66]
    InsertSort(arr)
    print(arr)

1.6.优缺点

优点：

折半插入排序在无序集情况下优于直接排序

缺点：

在近似有序集下，折半插入排序比较次数较多。