插入排序
Little_YangYang Lv1

1. 直接插入排序

综述

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

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

Ref:

分析

稳定性

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

时间复杂度

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

空间复杂度

O(1)

C++代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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++代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
}
}
  • 本文标题:插入排序
  • 本文作者:Little_YangYang
  • 创建时间:2021-10-31 23:09:25
  • 本文链接:https://www.endlcode.com/2021/10/31/插入排序/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!