问题描述

C++编程问题：不懂如何用rotate实现插入排序求指教。源代码如下

#ifndef _INSERTIONSORT_H
#define _INSERTIONSORT_H
#include
using namespace std;
template
void insertionSort(const Iterator &a, const Iterator &b){
int i,j,n=distance(a,b);
Iterator p,q,t;
for(j=1,q=p=a,p++,t=p;j
i=j-1;
while((i>=0)&&(*q>p))
q--,i--;
q++;//q璺熻釜a[i+1]
t++;//t璺熻釜a[j+1]
rotate(q,p,t);
}
}
//template
//void insertionSort(const Iterator &a, const Iterator &b){
// typedef typename iterator_traits::value_type T;
// int i,j,n=distance(a,b);
// T key;
// Iterator p,q,t;
// for(j=1,q=p=a,p++,t=p;j
// key=*p;//key鈫恆[j]
// i=j-1;
// while((i>=0)&&(*q>key)){
// *t=*q;//a[i+1]鈫恆[i]
// i--,t--,q--;
// }
// *t=key;//a[i+1]鈫恔ey
// }
//}
template
void insertionSort(const Iterator &a, const Iterator &b){
int i,j,n=distance(a,b);
Iterator p,q,t;
for(j=1,q=p=a,p++,t=p;j
i=j-1;
while((i>=0)&&Comparator()(*q,*p))
q--,i--;
q++;//q璺熻釜a[i+1]
t++;//t璺熻釜a[j+1]
rotate(q,p,t);
}
}
#endif / _INSERTIONSORT_H */
测试代码：

#include
#include
#include
#include
#include
#include
using namespace std;
#include "../Utility/partition.h"
#include "../Utility/merge.h"
#include "insertionsort.h"
int main(int argc, char** argv){
// int a[]={1,2,5,8,9,0,3,4,6,7},i;
int a[]={9,8,5,2,1,7,6,4,3,0},i;
string b[]={"AoMen","BeiJing","ShangHai","ChongQing","TianJin","XiangGang"};
// double c[]={0.5,3.7,6.3,8.5,9.2,1.7,2.3,4.1,5.9,7.4};
double c[]={9.2,8.5,6.3,3.7,0.5,7.4,5.9,4.1,2.3,1.7};
vector vb=vector(b,b+6);
list lc=list(c,c+10);
// insertionSort >(a,a+10);
merge >(a,a+5,a+10);
// inplace_merge(a,a+5,a+10,greater());
copy(a,a+10, ostream_iterator(cout, " "));
cout<
merge(vb.begin(),vb.begin()+3,vb.end());
// inplace_merge(vb.begin(),vb.begin()+3,vb.end());
// insertionSort::iterator,less >(vb.begin(),vb.end());
copy(vb.begin(),vb.end(), ostream_iterator(cout, " "));
cout<
list::iterator m=lc.begin();
advance(m,5);
merge::iterator,greater >(lc.begin(),m,lc.end());
// inplace_merge(lc.begin(),m,lc.end(),greater());
// insertionSort::iterator,less >(lc.begin(),lc.end());
copy(lc.begin(),lc.end(), ostream_iterator(cout, " "));
cout<<endl;
return (EXIT_SUCCESS);
}
参考于《算法设计、分析与实现C、C++和Java》

解决方案

rotate(q,p,t);只是用来交换p q，还是插入排序，有什么不懂？