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();
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);
}

1个回答

caozhy      2016.05.03 23:20

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

qq_34252077 如果是只是交换p q 的话为什么不用swap呢？

qq_34252077 用rotate实现排序的过程困惑，比如当 t 指向的位置超出范围的时候，我模拟不出过程，谢谢！

C语言实现直接插入排序，冒泡排序以及二分查找(巩固理解记忆)
C语言实现直接插入排序，冒泡排序以及二分查找(巩固理解记忆)

#include void Insert(int *a,int n)//把数组a的第n个数插入前n-1个数中，注意前n-1个数已经是排好序的了 { int i=n-1; int key=a[n]; while((i>=0)&&(key<a[i])) { a[i+1]=a[i]; i--;
C语言实现直接插入排序，冒泡排序，选择排序，希尔排序，快排
直接插入算法，每次将未排序的第一个元素插入到前半部分以及排好序的元素中。关键是要在已排好的部分进行移位操作。//直接插入排序算法 void InsertSort(int a[],int n) { for (int i = 1; i &amp;lt; n; i++) { if (a[i] &amp;lt; a[i - 1]) { int j = i - 1; int tmp = a[i]...

MIT算法导论-插入排序与归并排序及时间复杂度计算