【21天算法学习】折半插入排序

作者简介：
🍀姓姜，字君竹。
🍁浅薄观点：科以载文，文以载道
🌱软件技术升计科，计划考研
🌾要有最朴素的生活和最遥远的梦想，即使明日，天寒地冻，路遥马亡​​​

1. 概念及介绍
     折半插入排序与直接插入排序算法原理相同。只是，在向已排序的数据中插入数据时，采用来折半查找（二分查找）。先取已经排序的序列的中间元素，与待插入的数据进行比较，如果中间元素的值大于待插入的数据，那么待插入的数据属于数组的前半部分，否则属于后半部分。依次类推，不断缩小范围，确定要插入的位置。
     折半插入排序相对稳定，相对于直接插入排序，减少了比较次数；但是相对直接插入排序，移动次数不变。

2. 时间空间复杂度
     对于折半插入排序来说，由于元素的串位次数没有发生改变，只是在查找位置是更加快速了，所以与直接插入排序处于同一量级，在数据量很大时，要优于直接插入排序。
     如果输入的元素刚好是反向有序的，那么每次都需要进行位置的查找，但是在查找的次数要少一些。所以时间复杂度为O(n²)；最好的情况就是与直接插入排序相同，如果元素已经是正向有序的，呢么最开始比较的时候就会认为是在适合的位置，不需要再进行位置的寻找和串位，因此时间复杂度为O(n)。正常情况下折半插入排序的时间复杂度为O(n²)。
     算符执行过程中直接在元集合上操作，只需要几个额外的变量记录关键信息，所以空间复杂度为常数级O(1)。

3. 图解
   

4. 代码实现

int main() {
	int a[] = { 1, 12, 35, 54, 13, 21, 34, 56, 78, 22, 11 };
	int i = 0;
	int sz = sizeof(a) / sizeof(a[0]);
	for (i = 1; i < sz; i++) {
		int tmp = a[i];
		int left = 0;
		int right = i - 1;
		int j = 0;
		while (left <= right) {
			int mid = (right - left) / 2 +left;
			if (a[mid] > tmp) {
				right = mid - 1;
			}
			else{
				left = mid + 1;
			}
		}
		for (j = i - 1; j >= right + 1; j--) {
			a[j + 1] = a[j];
		}
		a[right + 1] = tmp;
	}
	for (i = 0; i < sz; i++) {
		printf("%d ", a[i]);
	}

	return 0;
}
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

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。

​