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呢?
大约 2 年之前 回复
qq_34252077
qq_34252077 用rotate实现排序的过程困惑,比如当 t 指向的位置超出范围的时候,我模拟不出过程,谢谢!
大约 2 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
算式计算器C++实现代码(顺序栈结构 增加了一些功能 求指教)
转自http://blog.sina.com.cn/s/blog_72e53c4c0100qw5n.html 数据结构课上学习栈结构的时候 根据老师的实验要求用VC++6.0平台写了这段代码除了加减乘除乘方,稍微自己加了一些好玩的小功能,比如计算阶乘"!",三角函数,比如正弦 "sin",对数"log"与"ln",常量pi(圆周率),自然对数底数"e"也加进去了,算是初步模仿中学用的科学计算器吧
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]...
插入排序递归法
很久没写博客了,今晚学习算法的东西,有个练习要用递归法来做插入排序,花了10多分钟弄出来了。         对我来说,迭代相对于递归更好理解,一直没有递归的思想,今天完全凭自己做出来了,别的不说,起码加深了对递归的理解。 /** * 插入发现递归版 * @param a */ public void insertSortRecursive(int[] a) { i
MIT算法导论-插入排序与归并排序及时间复杂度计算
前言 一、插入排序的场景 1.1 插入排序简介 根据《算法导论》中的描述,插入排序可以由“扑克抓牌”来解释,当我们抓牌的时候会进行排序,抓到的第一张牌,放置在第一的位置,后续抓到的牌与之前的牌进行比较后,插入到相应位置。 那么插入排序的需求可以描述为: 输入:n个数 输出:对输入序列的一个排序,使得a1' ≤ a2' ≤ … ≤ an' (亦可以降序排列)
八大排序之二分法插入排序
二分法插入排序,就是锁定左右区间在区间内一步一步缩小,从而找到合适的位置 就是将小区间排序,然后一步一步堆叠起来就可以了 核心的找位置是这样的 要是中间的数大于索要比较的数,就将最高限改为中间位置的前一个 要是中间数小于所要比较的数,就将最低位改为中间位置后一个, 后面的反复以往就可以 直到,最高位等于最低位,说明找到了要插入的位置 下面直接上代码 #include int a[1
基于单链表的直接插入排序算法和代码实现
在链表上对直接插入排序算法的思想描述如下: 在带头结点的单链表L 中,如果将已有元素进行升序(或降序)排列,可先将原单链表L 暂时断成两条短链L1和L2,新链L1的头结点用原链L 的头结点(head),并且链L1中仅放
数据结构之---C语言实现直接插入排序
数据结构之---C语言实现直接插入排序
排序算法之折半插入排序
折半插入排序    在直接插入排序的基础上做的改进,直接插入排序在寻找插入位置时是从后到前依次比较,直到找到插入位置。而折半插入排序在寻找插入位置时,先与有序序列中的中间位置R[mid]进行比较,如果比中间位置上的记录大,则在R[mid+1…N]中寻找,继续与右区间的中间记录进行比较;如果比中间位置上的记录小,则在R[0…mid-1]中寻找,继续与左区间中的数据进行比较。int BinaryInse