插入排序

最近在全面学习数据结构，常用算法记录：插入排序，基本思想是将待排序的记录按其关键字的大小逐个插入到一个有序序列（通常为左半部分），直到所有记录插入完成，是一种**稳定**排序。 空间复杂度：$O(1)$ 平均时间复杂度：$O(n^2)$ ```cpp #include using namespace std; //直接插入排序（含哨兵）优点：不用判断j>=0，哨兵即为循环结束标志 void insertSort_1(int arr[], int n); //直接插入排序（不含哨兵） void insertSort_2(int arr[], int n); //折半（二分）插入排序 对直接插入排序的优化 void insertSort_3(int arr[], int n); int main() { int arr[] = {-1, 5, 7, 12, 6, 2, 0, 8, 15, 1, 11}, arr_2[] = {-1, 5, 7, 12, 6, 2, 0, 8, 15, 1, 11}, arr_normal[] = {5, 7, 12, 6, 2, 0, 8, 15, 1, 11}; int length = (int)(sizeof(arr) / sizeof(int)); //数组长度 insertSort_1(arr, length); insertSort_2(arr_normal, length - 1); for (int i = 1; i = 0 && temp arr[0]) high = mid - 1; //查找左半部分 else low = high + 1; //查找右半部分，同时当arr[mid]==arr[0]时，继续在mid右方查找插入位置，保证算法稳定性 } for (j = i - 1; j >= high + 1; j--) //循环大于哨兵的所有元素，均往后移动一位 arr[j + 1] = arr[j]; //往后移，为待插入元素腾出空位 arr[high + 1] = arr[0]; //待插入元素插入 } } ```