这篇文章主要介绍“C++插入排序怎么实现”，在日常操作中，相信很多人在C++插入排序怎么实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++插入排序怎么实现”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
3.插入排序
最好的情况下 本来就是1 2 3 4 5 比较次数为n-1 次移动次数为 0
最坏的情况下 本来就是 5 4 3 2 1 比较次数为2+3+4+...+n=(n+2)(n-1)/2, 移动次数为(n+4)(n-1)/2
时间复杂度也为O(n^2)
计算
安全
数据库
网络和加速
企业服务
#include <iostream>
using namespace std;
void InsertSort(int *a, int n)
{
for(int i=1;i<n;i++)
{
if(a[i]<a[i-1])
{
int j = i-1;
int temp = a[i]; //把待排序元素赋给temp，temp在while循环中并不改变，这样方便比较，并且它是要插入的元素
while((j>=0)&&(temp<a[j])) //while循环的作用是将比当前元素大的元素都往后移动一个位置
{
a[j+1]=a[j];
j--; // 顺序比较和移动,依次将元素后移动一个位置
}
a[j+1] = temp; //元素后移后要插入的位置就空出了，找到该位置插入
}
}
}
void InsertSort(int *a, int n)
{
for(int i=1; i<n;i++)
{
if(a[i]<a[i-1])
{
int temp = a[i];
int j=i-1;
for(;j>=0 && temp<a[j];j--)
{
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
}
int main()
{
int a[6] = {1,5,3,4,6,2};
BubbleSort(a,6);
for(int i=0;i<6;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}到此，关于“C++插入排序怎么实现”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/4511602/blog/4826742
