【21天算法挑战赛】查找算法——二分插入排序

​​​​💬💬作者有话想说：

💟作者简介：我目前是一个在校学生，想通过自己的学习努力让自己的技术、知识都慢慢提升，希望我们一起学习呀~💜💜💜
 
☂️兴趣领域：目前偏向于前端学习 💜💜💜
 
🎬> 活动地址：CSDN21天学习挑战赛
 
💜有话想说：写博客、记笔记并不是一种自我感动，把学到的东西记在脑子里才是最重要的，在这个过程中，不要浮躁，希望我们都可以越来越优秀！💜💜💜
 
🪀语言说明：代码实现我会用Python/C++~

​

一、二分插入排序

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

• 二分查找：二分查找
• 直接插入排序：直接插入排序

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 
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);
	}
 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

1.6.优缺点

优点：

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

缺点：

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