难实现：
代码语言：javascript复制/*
编写一个程序，将一个整型数组中的数据从大到小排列，要求使用直接插入排序
*/
#include <iostream>
using namespace std;
void insertSort(int data[],int len)
{
int i,j,tmp;
for(i=1;i<len;i )
{
tmp=data[i];
j=i-1;
while(j>=0 && tmp>data[j])//从大到小排序
{
data[j 1]=data[j];//循环右移，直到找到data[i]应该放置的位置
j--;
}
data[j 1]=tmp;//将元素tmp插入指定位置
}
}
int main()
{
int data[9]={0,3,1,2,4,6,6,10,5};
insertSort( data,9);
for(int i=0;i<9;i )
cout<<data[i]<<endl;
return 0;
}易实现：
代码语言：javascript复制#include <algorithm>
#include <cassert>
#include <functional>
#include <iterator>
#include <iostream>
using namespace std;
//std::upper_bound 找到当前元素应该在的位置
//std::rotate 将当前元素放到正确的位置
template <class Fd, class Compare=std::less<Fd>>
void insertion_sort(Fd first, Fd last, Compare cmp=Compare{})
{
for (auto it=first;it!=last;it )
{
auto const insertion=std::upper_bound(first,it,*it,cmp);
std::rotate(insertion,it,std::next(it));
assert(std::is_sorted(first,std::next(it),cmp));
}
}
int main()
{
std::vector<int> data={0,3,1,2,4,6,6,10,5};
insertion_sort(data.begin(),data.end(),std::less<int>());
for(int i=0;i<data.size();i )
cout<<data[i]<<endl;
return 0;
}博主：菜鸟程序员
初衷：学习资料，程序设计，视觉算法，求职经验，工作心得
