1. 直接插入排序

综述

插入排序将遍历当前容器，将当前值插入到前方合适的位置，形成左侧一定有序，右侧可能无序的状态。

在寻找左方位置的时候，会将比当前遍历值大的不断向右移动。

Ref：

分析

稳定性

直接插入排序是稳定的排序算法

时间复杂度

最优：当前是有序的状态：O(n)
最差：当前是逆序的状态：O(n^2)

空间复杂度

O(1)

C++代码实现

void insertSort(vector<int>& nums) {
	int n = nums.size();
	for (int i = 1; i < n; i++) { // 从下标1开始遍历该容器
		int key = nums[i], j = i - 1; // 声明临时变量j为当前数值左值
		while (j >= 0 && nums[j] > key) { // 寻找比当前数值小的位置，在寻找中不停左移左方元素
			nums[j + 1] = nums[j];
			j = j - 1;
		}
		nums[j + 1] = key; // 找到位置，插入
	}
}

int main() {
	vector<int> nums = { 1,3,2,5,1,5,6 }; // 测试
	insertSort(nums);
	for (int n:nums) {
		cout << n << endl;
	}
	return 0;
}

2. 折半插入排序

综述

相比较直接插入排序，折半插入排序仅减少了比较的次数，依然需要不断移动数据，故时间复杂度仍为O(n^2)

C++代码实现

void insertBiSort(vector<int>& nums) {
	int n = nums.size();
	for (int i = 1; i < n; i++) {
		int key = nums[i], low = 0, high = i - 1;
		// bi search
		while (low<=high) {
			int mid = (low + high) / 2;
			if (nums[mid] > key) {
				high = mid - 1;
			}
			else {
				low = mid + 1;
			}
		}
		for (int j = i-1; j >=high+1 ; j--) {
			nums[j + 1] = nums[j];
		}
		nums[high + 1] = key;
	}
}