当前位置：首页 > news >正文

插入排序（C++）

news 来源：原创 2024/4/20 20:40:54

算法思想：插入排序的工作原理是通过构建有序序列，对于未排序的数据，在已排序的序列中从后向前扫描，找到相应的位置并插入。插入排序在实现上，通常采用in-place排序，因而在从后向前扫描的过程中，需要反复把已排序的元素逐步向后挪位，为最新的元素提供插入空间。

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。

当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

平均时间复杂度： O(n * n)
最好情况： O(n)
最坏情况：O(n * n)
排序方式：原地排序
稳定性：稳定
空间复杂度： O(1)

算法步骤：

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

代码实现：

#include <iostream>
#include <vector>
using namespace std;void printVector(vector<int>& nums, int len, int i)
{cout << "step" << i << ": ";for (auto num : nums){cout << num << " ";}cout << endl;
}void insertionSort(vector<int>& nums, int len)
{for (int i = 1; i < len; ++i){if (nums[i] < nums[i - 1]) //若第i个元素小于第i-1个元素，移动有序表后插入{int j = i - 1;int x = nums[i]; //待排序元素while (j >= 0 && x < nums[j])   //要保证j>=0，因为nums[j]要合法{nums[j + 1] = nums[j];--j;  //元素后移}nums[j + 1] = x; //插入到正确位置}//若第i个元素大于i-1元素，直接插入printVector(nums, len, i); //打印每趟排序的结果}
}int main()
{vector<int> nums = { 8,7,1,4,2,3,6,9,5, };int len = nums.size();insertionSort(nums, len);system("pause"); //按任意键继续return 0;
}

相关文章：