插入排序是一种简单的排序算法，一般又称为直接插入排序。插入排序的思想与选择排序有些相似，即在原数组上将数组分为两个部分：已排列好的有序数组和待排列数组，选择排序强调的是“选择”，而插入排序强调的是”插入“（类似生活中，整理扑克牌动作）。下面我们将详细的介绍一下插入排序的思想和具体代码实现。
算法思想
插入排序的思想大致如下所示：
- 从第一个元素开始，默认为该元素就是已排好的有序数组（因为只有一个元素的数组，本身就可以认为其是有序的）。
- 取出下一个元素（待排列数组中的第一个元素），在已经排好的有序数组中从后往前进行比较，找到其应该插入的位置，将其“插入“对应位置。（具体的实现过程如下：取出的目标元素从已排好的有序数组的最后一位开始扫描，依次与其进行比较，如果大于目标元素，则交换两者的位置，当遇到小于或等于则停止）
- 重复2的步骤，直到待排列数组为空。
代码实现
#include <algorithm>
#include <iostream>
#include <vector>
template <typename T>
std::vector<T> insertionSort(std::vector<T> arr) {
for (int i = 1; i < arr.size(); ++i) { // 默认第一个元素即为已排好数组
// 写法1
/*for (int j = i; j > 0; --j) {
if (arr[j] < arr[j - 1])
std::swap(arr[j], arr[j - 1]);
else
break;
}*/
// 写法2
/*for (int j = i; j > 0 && arr[j] < arr[j - 1]; --j)
std::swap(arr[j], arr[j - 1]);*/
// 写法3
T t = arr[i];
int j;
for (j = i; j > 0 && arr[j - 1] > t; --j) arr[j] = arr[j - 1];
arr[j] = t;
}
return arr;
}
int main() {
std::vector<int> arr = {3, 5, 2, 1, 4};
std::vector<int> sorted = insertionSort(arr);
for (int num : sorted) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
复杂度
-
空间复杂度：插入排序在排序过程中不涉及额外的其它空间，因此空间复杂度为
。
-
时间复杂度：在完全有序的情况下，插入时每个目标元素都要与已排好的有序数组的末尾元素比较一次，所以时间复杂度为
；对于完全逆序的情况下，插入时目标元素要与已排好的有序数组的每一个元素都要比较一次，因此时间复杂度为
。
