`
yunchow
  • 浏览: 316842 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

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

    博客分类:
  • C++
阅读更多
* 冒泡排序
一轮比较所有相邻数据对,如果顺序不合适就交换,本轮只要发生过交换就再来一轮.
#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;
}


0
0
分享到:
评论

相关推荐

    C++的STL标准模板库思维导图

    STL 是一些常用数据结构(如链表、可变长数组、排序二叉树)和算法(如排序、查找)的模板的结合,主要由 Alex Stepanov 主持开发,于 1998 年被加入 C++ 标准。 有了 STL,程序员就不必编写大多数常用的数据结构和...

    标准模板库STL(Standard Template Library)指南

    一个成员取得下一个成员,从头到尾“走过”结构中的元素〔就象排序算法不关心元素是存 放在数组中或是线性表中)。Stepanov 研究过一些算法可以用一种抽象的方式实现,而且不 会影响效率。 1.2 STL 历史 1985 年,...

    数据结构使用C++标准模板库STL 陈本林版

    讲述递归的实现和若干常用的排序算法。书中对讨论的每一种数据结构都给出了应用示例和运行结果。全书含有大量的例题,读者可以从这些例题中学习程序设计技巧和使用数据结构求解问题的方法。 本书内容丰富,取材新颖...

    stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列)

    算法由模板函数体现,这些函数不是容器类的成员函数,是独立的函数,它们可以用于STL容器,也可以用于普通的C++数组等. 头文件:#include 在STL的泛型算法中有4类基本的算法: 1)变序型队列算法: 可以改变容器内的数据...

    C++ STL开发技术导引(第5章)

    第23章 排序算法 339 23.1 元素入堆push_heap 339 23.2 创建堆make_heap 343 23.3 元素出堆pop_heap 348 23.4 堆排序sort_heap 351 23.5 是否为堆is_heap 352 23.6 局部排序partial_sort 354 23.7 ...

    数据结构、算法与应用:C++语言描述(原书第2版)第一部分

    新版书着重利用标准模板库(STL),把书中开发的数据结构和算法与相应的STL实现方法相互关联。本书还增加了很多新的实例和练习题。  书中的应用实例是它的特色。Sahni博士为每一个数据结构和算法都提供了若干个应用...

    数据结构、算法与应用:C++语言描述(原书第2版)第二部分

    18.4.2 排序算法的下限 第19章 动态规划 19.1 算法思想 19.2 应用 19.2.1 0/1背包问题 19.2.2 矩阵乘法链 19.2.3 所有顶点对之间的最短路径 19.2.4 带有负值的单源最短路径 19.2.5 网组的无交叉子集 19.3 参考及推荐...

    c++ SLT模板排序交换实例

    c++ STL模板实现简单排序及元素的交换实例 本实例实现的排序方法是在开发中常用的排序算法模式

    C++ STL 开发技术导引(第6章)

    第23章 排序算法 339 23.1 元素入堆push_heap 339 23.2 创建堆make_heap 343 23.3 元素出堆pop_heap 348 23.4 堆排序sort_heap 351 23.5 是否为堆is_heap 352 23.6 局部排序partial_sort 354 23.7 ...

    标准模板库(STL)源码剖析

    你将看到各种算法(排序、搜寻、排列组合、数据移动与复制…)的实现;你甚至将看到底层的memory pool 和高阶抽象的traits 机制的实现。那些数据结构、那些算法、那些重要观念、那些编程实务中最重要最根本的珍宝,...

    C++进阶课程讲义_v1.0.4.pdf

    10.3.5常用的排序算法 154 10.3.6常用的拷贝和替换算法 156 10.3.7常用的算术和生成算法 157 10.3.8常用的集合算法 158 10.4 STL综合案例 159 10.4.1案例学校演讲比赛 159 10.4.2案例:足球比赛 161

    C++标准程序库STL的架构

    9.9 排序算法 111 9.9.1 对所有元素排序 111 9.9.2 局部排序 112 9.9.3 根据第n个元素排序 113 9.9.4 heap算法 114 9.10 已序区间算法 115 9.10.1 搜寻元素 115 9.10.2 合并元素 117 9.11 数值算法 120 9.11.1 加工...

    java JGL标准程序库,类似C++的STL

    JGL实现了许多功能,可满足对一个集合库的大多数常规需求,它与C++的模板机制非常相似。JGL包括相互链接起来的列表、设置、队列、映射、堆栈、序列以及反复器,它们的功能比Enumeration(枚举)强多了。同时提供了...

    C++ 排序函数模板源码,MFC程序可用(冒泡)

    算法 一个排序可以用的C++函数模板,无意间需要对字符串集合CStringArray进行排序,但标准模板库STL提供的函数模板sort虽然功能强大,不过有些不便,可能我不太习惯吧,于是才想着要自编一个排序函数模板,方便和我...

    C++ STL开发技术导引(第3章)

    第23章 排序算法 339 23.1 元素入堆push_heap 339 23.2 创建堆make_heap 343 23.3 元素出堆pop_heap 348 23.4 堆排序sort_heap 351 23.5 是否为堆is_heap 352 23.6 局部排序partial_sort 354 23.7 ...

    谭浩强C语言程序设计,C++程序设计,严蔚敏数据结构,高一凡数据结构算法分析与实现.rar

    1.6 C和C++ 1.7 简单的C程序介绍 1.8 输入和输出函数 1.9 C源程序的结构特点 1.10 书写程序时应遵循的规则 1.11 C语言的字符集 1.12 C语言词汇 1.13 Turbo C 2.0 集成开发环境的使用 1.13.1 Turbo C 2.0 ...

    C++STL程序员开发指南【可搜索+可编辑】

    第二篇C++ STL 技术原理和组成 第3 章STL 技术原理· · · · · · · · · · · · · · · · · ·................................. 103 3-1 模板概述· · · · · · • · · · · · · · · · ·...

    学会C语言之后还有必要学习C++吗?具体运用C++编写的代码解析.docx

    STL是C++中一个非常重要的库,它提供了许多基本数据结构和算法,如向量、列表、堆、排序等等。使用STL可以让程序员更加高效地编写代码,同时也可以提高代码的可读性和可维护性。 C++的应用范围非常广泛。在游戏

    STL双向链表list的sort

    对于C++的STL的双向链表,排序算法有的模板并没有实现,因此给出来,大家参考。

    数据结构与算法分析

     7.3 一些简单排序算法的下界   7.4 谢尔排序   7.5 堆排序   7.6 归并排序   7.7 快速排序   7.7.1 选取枢纽元   7.7.2 分割策略   7.7.3 小数组   7.7.4 实际的快速排序例程  ...

Global site tag (gtag.js) - Google Analytics