2 qq 34252077 qq_34252077 于 2016.05.03 22:36 提问

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

#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》

1个回答

caozhy
caozhy   Ds   Rxr 2016.05.03 23:20

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

qq_34252077
qq_34252077 如果是只是交换p q 的话为什么不用swap呢?
一年多之前 回复
qq_34252077
qq_34252077 用rotate实现排序的过程困惑,比如当 t 指向的位置超出范围的时候,我模拟不出过程,谢谢!
一年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!