插入排序算法从难到易实现

/*
编写一个程序，将一个整型数组中的数据从大到小排列，要求使用直接插入排序
*/
#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;
}

#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;
}