1.插入排序

最简单的排序算法之一是插入排序（insertion sort)。插入排序由N-1趟〈 pass）排序组成。对于p=1到N-1趟，插入排序保证从位置0到位置p上的元素为已排序状态。插入排序利用了这样的事实:位置0到位置p-1上的元素是已经排过序的。下面表格显示了一个简单的数组在每一趟插入排序后的情况。

初始状态	34	8	64	51	32	21	移到位置
p=1	8	34	64	51	32	21	1
p=2	8	34	64	51	32	21	0
p=3	8	34	51	64	32	21	1
p=4	8	32	34	51	64	21	3
p=5	8	21	32	34	51	64	4

template<typename Comparable>
void insertsort(vector<Comparable>ves)
{
    for(int i=1;i<ves.size()-1;i++)
    {
        Comparable tmp=ves[i];
        for(int j=i;j>0&&tmp<ves[j-1];j--)
        ves[j]=ves[j-1];
        a[j]=tmp;
        

    }
}

2.插入排序实现STL sort

在STL中，排序例程不采用由具有可比性的项所组成的数组作为单一的参数，而是接收一对迭代器来代表在某范围内的起始和终止标志。一个双参数排序例程使用一对迭代器，并假设所有的项都可以排序。而一个三参数排序例程有一个函数对象作为第三个参数。

(1)我们必须编写一个双参数排序和一个三参数排序的例程。假定双参数排序调用三参数排序，同时使用less<object> ( )作为第三个参数。

(2)数组访问必须转换成迭代器访问。

(3）原始代码需要创建tmp，在新代码中它将具有类型object。

第一个观点最容易实现，因为模板类型参数(例如，泛型)对双参数排序来说都是iterator:然而，object不是一个泛型参数。我们可以通过编写一个辅助例程来解决这个问题。这个辅助例程将object作为另一个模板类型参数。

emplate<typename Iterator>
void insertsort(Iterator&begin,Iterator&end)
{
    if(end!=begin)
    insertsort(begin,end,*begin);
}
template<typename Iterator,typename Object>
void insertHelp(Iterator begin,Iterator end,
               Object& obj)
               {
                 insertsort(begin,end,less<Object>());
               }

这里的小窍门是在双参数排序中，*begin具有类型object，并且辅助例程具有所需要的第二个泛型的参数。现在双参数排序写完了，下面可以写三参数排序。但是，需要声明tmp为object类型，三参数排序只具有1terator和Comparator是泛型类型。因此我们不得不再次使用相同的技巧来得到一个四参数例程，将一个object类型的项作为第四个参数，仅仅是为添加一个辅助

emplate<typename Iterator,typename Comparable,typename Obj>
void insertsort(const Iterator&begin,const Iterator&end,
Comparable&lessThan)
{
    if(begin!=end)
    insertsort(begin,end,lessThan,*begin);
    
}
template<typename Iterator,typename Comparable,typename Object>
void insertsort(const Iterator&begin,const Iterator&end,Comparable
lessThan,const Object&obj)
{
    Iterator j;
    for( auto i=begin+1;j<end;j++)
    {
        obj tmp=*i;
        for(j=p;j!=begin&&lessThan(tmp,*(j-1));j--)
        *j=*(j-1);
        *j=tmp;
    }

}

希尔排序

背景：

谢尔排序〈Shellsort）的名称源于它的发明者Donald Shell，该算法是冲破二次时间屏障的第一批算法之一，不过，直到它最初被发现的若干年后才证明了它的亚二次时间界。正如上节所提到的，它通过比较相距-一定间隔的元素来工作;各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后-趟排序为止。由于这个原因，谢尔排序有时也叫作缩减增量排序( diminishing increment sort)。

谢尔排序使用一个序列 $^h{1} ^h{2}... ^h{n}$ 叫作增量序列（increment sequence)。只要 $^h{1}$ = 1，任何增量序列都是可行的，不过，有些增量序列比另外一些增量序列更好（后面我们将讨论这个问题)。在使用增量h的一趟排序之后，对于每一个i我们有a[i]≤a[i + h](这里该不等式是有意义的):所有相隔h的元素都被排序。此时称文件是h排序的(he-sorted)。例如，下面显示了几趟排序后数组的情况。谢尔排序的一个重要性质(我们只叙述而不证明)是，一个 $^h{k}$ 排序的文件(此后将是 $^h{k-1}$ ;排序的）保持它的 $^h{k}$ 排序性。事实上，假如情况不是这样的话，那么该算法也就没什么意义了，因为前面各趟排序的成果会被后面各趟排序给打乱。

初始状态	81	94	11	96	12	35	17	95	28	58	41	75	15
5排序之后	35	12	11	28	12	41	75	15	96	58	81	94	95
3排序之后	28	12	11	35	15	41	58	17	94	75	81	96	95
1排序之后	11	12	15	17	28	35	41	58	75	81	94	95	96

增量序列的一个流行（但是不好）的选择是使用Shell建议的序列: $^h{i}$ =[N/2]和 $^h{k}$ =[h/2].下包含一个使用该序列实现谢尔排序的方法。后面我们将看到，存在一些递增的序列，它们对该算法的运行时间给出了重要的改进;即使是一个小的改变都可能剧烈地影响算法的性能

void shellsort(vector<Comparable>ves)
{
    for(int gap=ves.size()/2;i<a.size();gap/=2)
    {
        for(int i=gap;i<ves.size();i++)
        {
            Comparable tmp=ves[i];
            for(int j=i;j>=gap&&tmp<ves[j-gap];j-=gap)
            ves[j]=ves[j-gap];
            ves[j]=tmp;
        }
    }
}

最佳增量为 Hibbzard增量

$9*4^{i}-9*2^i+1$