同样是一道面试题，函数参数类型是deque。deque是双端队列属于动态数组类型，没有sort成员函数，只有借助其他算法或者支持排序的容器，拷贝回deque。（练习而已，时间空间复杂度不考虑了）

一、直接调std::sort，参数分别为起始迭代器，结尾迭代器（指向末元素的后面一个）：

#include <iostream>
#include <deque>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

template<typename T>
void sort_stdalg(deque<T>& dq)
{
	std::sort(dq.begin(),dq.end());
}

二、std::map默认按照键值排序（当然也有无序map），将deque元素作为key一个个弹到map中（删除原deque元素），完了后从map拷回到deque。注意deque的back()、pop_back()、push_back()，map的insert(pair<T,T>(*,*))的使用：

template<typename T>
void sort_map(deque<T>& dq)
{
	map<T,int> mpp;
	int capa=dq.size();
	for(int i=0;i<capa;++i){
		auto dqcur=dq.back();
		dq.pop_back();
		mpp.insert(pair<T,int>(dqcur,0));
	}
	for(auto it=mpp.begin();it!=mpp.end();++it){
		dq.push_back(it->first);
	}
}

三、冒泡排序。

冒泡思想是底部开始遍历元素，根据轻者上浮重者下沉原则进行两两交换（相邻元素重复比较，即a1和a2、a2和a3、a3和a4），直到遍历到头元素结束。经此一役后，最轻气泡已经在头元素，在进行下一轮的从底部开始遍历元素时要注意，结束条件是是头部第二个元素。以此类推直到两个loop走完，排序结束：

template<typename T>
void sort_bubble(deque<T>& dq)
{
	int exchg=0;
	int capa=dq.size();
	T arrtmp[capa];
	for(int i=0;i<capa;++i){
		T dqcur=dq.back();
		dq.pop_back();
		arrtmp[i]=dqcur;
	}
	T i,j,tmp;
	for(i=0;i<capa;++i){
		exchg=0;
		for(j=capa-1;j>=i;--j){
			if(arrtmp[j]<arrtmp[j-1]){
				tmp=arrtmp[j];
				arrtmp[j]=arrtmp[j-1];
				arrtmp[j-1]=tmp;
				exchg=1;
			}
		}
		if(exchg!=1)
			break;
	}
	for(int i=0;i<capa;++i){
		dq.push_back(arrtmp[i]);	
	}

}

另外注意到如果第i次排序已经排完了，它还是会进行下一次扫描。这里记了个exchg表示当前排序已经交换过元素。如果本轮排序没有交换过，说明元素已经有序，下次排序也就没有必要了。

测试：

int main(int argc, char* argv[])
{
	std::deque<int> dq1{4,2,6,1,9,8};
	printarr(dq1);
	sort_stdalg(dq1);
	printarr(dq1);

	std::deque<string> dq2{"Bb","Aa","pP","Ee"};
	printarr(dq2);
	sort_map(dq2);
	printarr(dq2);
	
	std::deque<int> dq3{8,6,9,2,3,7};
	printarr(dq3);
	sort_bubble(dq3);
	printarr(dq3);
	
	return 0;
}

结果：