六年级做网站的软件,广告设计与制作专业就业岗位,wordpress用户修改文章,网站开发发展趋势描述
插入排序是一种简单直观的排序算法。它的基本思想是将一个待排序的数据序列分为已排序和未排序两部分#xff0c;每次从未排序序列中取出一个元素#xff0c;然后将它插入到已排序序列的适当位置#xff0c;直到所有元素都插入完毕#xff0c;即完成排序。
实现思路…描述
插入排序是一种简单直观的排序算法。它的基本思想是将一个待排序的数据序列分为已排序和未排序两部分每次从未排序序列中取出一个元素然后将它插入到已排序序列的适当位置直到所有元素都插入完毕即完成排序。
实现思路
从第一个元素开始将其视为已排序序列。取出未排序序列的第一个元素并将它与已排序序列的元素逐个比较。如果找到一个已排序序列的元素大于待插入元素将该元素后移一位。重复步骤3直到找到一个已排序序列的元素小于或等于待插入元素。将待插入元素插入到这个位置。重复步骤2-5直到未排序序列中的所有元素都被插入到已排序序列中。
图解 代码
#include iostream
#include vectorusing namespace std;void insertionSort(vectorint arr) {int n arr.size();for (int i 1; i n; i) {int key arr[i];int j i - 1;while (j 0 arr[j] key) {arr[j 1] arr[j];j--;}arr[j 1] key;}
}int main() {vectorint arr {9, 5, 7, 1, 3};insertionSort(arr);cout 插入排序 : endl;for (int num : arr) {cout num ;}cout endl;return 0;
}输出结果
时间复杂度
根据循环次数插入排序的平均时间复杂度为O(n2)最好情况下为O(n)最坏情况下为O(n2)。
空间复杂度
插入排序的空间复杂度为O(1)。
技巧
在内层循环中可以通过将待插入元素与已排序序列的最后一个元素进行比较而不是逐个比较已排序序列的元素以提高效率。可以使用二分查找来在已排序序列中找到待插入元素的插入位置以进一步提高效率。
结论
坚持自己的梦想即使没有翅膀也能飞翔。
