c++排序算法与模板和STL

* 冒泡排序
一轮比较所有相邻数据对,如果顺序不合适就交换,本轮只要发生过交换就再来一轮.

#include <iostream>
using namespace std;
#include <ctime>

typedef int T ;
void sort(T a[], int n)
{
        bool bSwap = false;
        do{
                bSwap = false;
                for(int i=1;i<n;i++){
                        if(a[i] < a[i-1]){
                                swap(a[i],a[i-1]);
                                bSwap = true; 
                        }       
                }       
        }while(bSwap);
}

int main()
{
        int N=10240;   
        int a[N];   
        for(int i=0;i<N;i++)   
        a[i] = N-i;    
        time_t t1 = time(NULL);
        sort(a,N);
        time_t t2 = time(NULL);
        cout << "time:" << t2-t1 << endl;
        for(int i=0;i<10;i++)   
                cout << a[i] << ' ';    
        cout << endl;   
}

---------------------------------------
* 插入法排序
1,将头两个元素排序
2,接下来依次将每一个元素排到正确的位置
3,直到所有的元素都排完

void sort(T a[], int n)
{

        int temp;
        int p;
        for(int i=1;i<n;i++){
                temp = a[i];
                for(p=i;p>0&&a[p-1]>temp;p--)
                        a[p] = a[p-1];
                a[p] = temp;
        }
}

-------------------------------
* 快速排序法

效率最高的排序方法
选出一个分界值,把数组分成两个部分
对于分成的两个部分分别再做同样的操作

选出分界值的方法:把第一个,中间,最后一个拿出来,取中间值

//快速排序法完整方法(比较难)
void sort(T a[], int n){
	if(n<=1) return ;
	swap(*a,a[n>>1]);
	T* L = a+1;
	T* R = a+n-1;
	T v = *a;
	while(L<R){
		while(*L<v&&L<R) L++;
		while(*R>=v&&R>a) R--;
		if(L<R) swap(*L,*R);
	}
	if(v>*R) swap(*a,*R);
	sort(a,R-a);
	sort(R+1,n-(R-a)-1);
}

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
=============================================
* 模板

  + 自定义模板
  + 标准模板库(STL)
c++是一种强类型语言,一个变量类型一旦定义终身不变.

//sort.cc
//函数模板
#include <iostream>
using namespace std;

template<typename/*可写成class*/ T>	//模板头
void sort(T* a, int n){
	//code..
}
void sort(char* a[], int n){  //优先考虑非模板函数
	//code...
}
template<typename T>   //模板头
void disp(T* a, int n){
	//code...
}
int main()
{
	double ad[5] = { ... };
	int ai[7] = { ... };
	char ac[4] = { ... };
	sort(ad,5);
	sort(ai,7);
	sort<char>(ac,4);
	disp(ad,5);//或disp<double>(ad,5);
	disp(ai,7);
	
} //end main

由此,模板编程又称为通用类型编程,也叫泛型编程.
一般情况按一般处理,特殊情况特殊处理.
编译器优先选用非模板函数.
模板声明和定义不要分开.(标准里是可以的,但是几乎所有的编译器都不支持)

#include <iostream>
using namespace std;

template<typename T>
T max(T* a, int n ){
        T max = *a;
        for(int i=0; i<n; i++){
                if(a[i]>max)
                        swap(max,a[i]);
        }
        return max;
}
int main()
{
        int a[3] = {1,2,3};
        cout << max(a,3) << endl;
        double b[3] = {1.1,2.2,3.3};
        cout << max(b,3) << endl;

}

注意函数模板要放在头文件中,声明和定义都要放在头文件中.因为模板就是一个样板.

//类模板
template<typename T>
class Stack{ //.....

template<typename T>
void show(Stack<T> s){
	//code
}
int main()
{
	Stack<int> si;
//因为创建对象时不一定会传递参数,编译器不能确定类型
//在使用时,必须指定类型.其中传过去的类型也叫模板形参.
//在确定模板类型的过程称为模板的实例化.
//实例化类模板之后才会变成类,才能创建对象
	Stack<double> sd;
	Stack<char> sc;  //Stack<char>是类名
	cout << sizeof(si) << endl;//输出结果会不一样
	cout << sizeof(sd) << endl;
	cout << sizeof(sc) << endl;//所以它们不是同一个类型
}

模板名<类型实参> 共同构成类名.

#include <iostream>
#include <string>
using namespace std;

template<typename T,typename U>//类模板
struct Pairs{
        T first;
        U second;
        Pairs():first(T()),second(U()){ }
        Pairs(const T& t,const U& u):first(t),second(u){ }
};
template<typename T, typename U>//函数模板
void show(Pairs<T,U> p){
        cout << p.first << ',' << p.second << endl;
}
template<typename T, typename U>//函数模板
Pairs<T,U> mkpair(T t, U u) {
        return Pairs<T,U>(t,u);
}
int main()
{
        Pairs<int, double> p1;
        Pairs<int, string> p2(100,"Hi");
	//p1,p2是来自同一个模板的不同类型
        show(p1);
        show(p2);
        show(Pairs<char,int>('A',33));
        show(mkpair('A',33) );
}

========================================
* 标准模板库(STL)

  + 类模板叫容器,java里叫集合
  + 函数模板叫通用算法.
几乎所有的容器都有一个内部类:iterator(迭代器)
迭代器把类模板和函数模板联系在一起形成一个体系就是标准模板库(STL)
iterator里的封装了指针,但它又模仿指针操作.又称智能指针
在标准库里从来不直接用指针,用迭代来替代指针操作.

class iterator{
	T* p;
public:
	iterator(){ }
	iterator(const interator& i){ }
	iterator(T* q){ }
	operator*(){ }
	operator->(){ }
	operator++(){ }
	operator==(){ }
	operator!=(){ }
};//它是一个内部类

容器的区间是半开半闭的,*end不属于区间

* 容器的分类:
  + 序列式容器
- (重要)vector动态数组,重载的'[]'运算符
- deque(double end queue) 双端队列,首尾插入/删除数据方便
- (重要)list 双向链表
  + 关联式容器
- 所有的关联式容器都是二叉查找树模板
- map 映射 不允许重复
- multimap 多映射允许重复
- set 数据集 不允许重复
- multiset 多数据集 允许重复
* 容器的共性
  + 构造函数:都有无参,拷贝,区间构造函数
- 区间是由两个迭代器界定的一个范围.vector<int> v(beg,end)
  + 运算符的重载
- 包括: =,>,>=,<.<=,==,!=
- insert(迭代器,元素/*总是复制一份*/)//用迭代器指位置,而不是指针
- size()   //容器中已经有的元素个数
- empty()  //判断容器是否为空
- max_size()  //这一种容器最大容量
- clear() //清空整个容器
- swap(c2) //跟另一个容器交换,swap(c1,c2)不是成员函数
  + 头文件的名字跟容器的名字一致
  + begin() //返回指向第一个元素的迭代器
  + end()   //指向最后一个元素之后,因此end()指向的元素不属于这个容器

//容器例子
#include <iostream>
#include <list>
using namespace std;

int main()
{
        list<int> l1;
        int a[5] = {3,4,5,6,7};
        list<int> l2(a,a+5);
        cout << "l1.size():" << l1.size() << endl;
        cout << "l2.size():" << l2.size() << endl;
        list<int>::iterator it;
        for(it=l2.begin();it!=l2.end();it++)
                cout << *it << ' ';
        cout << endl;
        it = l2.begin();
        it ++;
        l2.erase(it);
        l2.insert(l2.begin(),100);
        l2.insert(l2.end(),200);
        for(it=l2.begin();it!=l2.end();it++)
                cout << *it << ' ';
        cout << endl;
}