您现在的位置是:首页 >学无止境 >排序算法---插入排序网站首页学无止境
排序算法---插入排序
简介排序算法---插入排序
插入排序是一种简单的排序算法,一般又称为直接插入排序。插入排序的思想与选择排序有些相似,即在原数组上将数组分为两个部分:已排列好的有序数组和待排列数组,选择排序强调的是“选择”,而插入排序强调的是”插入“(类似生活中,整理扑克牌动作)。下面我们将详细的介绍一下插入排序的思想和具体代码实现。
算法思想
插入排序的思想大致如下所示:
- 从第一个元素开始,默认为该元素就是已排好的有序数组(因为只有一个元素的数组,本身就可以认为其是有序的)。
- 取出下一个元素(待排列数组中的第一个元素),在已经排好的有序数组中从后往前进行比较,找到其应该插入的位置,将其“插入“对应位置。(具体的实现过程如下:取出的目标元素从已排好的有序数组的最后一位开始扫描,依次与其进行比较,如果大于目标元素,则交换两者的位置,当遇到小于或等于则停止)
- 重复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;
}
复杂度
- 空间复杂度:插入排序在排序过程中不涉及额外的其它空间,因此空间复杂度为 O ( 1 ) O(1) O(1)。
- 时间复杂度:在完全有序的情况下,插入时每个目标元素都要与已排好的有序数组的末尾元素比较一次,所以时间复杂度为 O ( n ) O(n) O(n);对于完全逆序的情况下,插入时目标元素要与已排好的有序数组的每一个元素都要比较一次,因此时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。