|
C++知识点
一、＃i nclude “filename.h”和＃i nclude filename.h>的区别
＃i nclude “filename.h”是指编译器将从当前工作目录上开始查找此文件
＃i nclude filename.h>是指编译器将从标准库目录中开始查找此文件
二、头文件的作用
加强安全检测
通过头文件可能方便地调用库功能，而不必关心其实现方式
三、* , &修饰符的位置
对于*和&修饰符，为了避免误解，最好将修饰符紧靠变量名
四、if语句
不要将布尔变量与任何值进行比较，那会很容易出错的。
整形变量必须要有类型相同的值进行比较
浮点变量最好少比点，就算要比也要有值进行限制
指针变量要和NULL进行比较，不要和布尔型和整形比较
五、const和#define的比较
const有数据类型，
#define没有数据类型
个别编译器中const可以进行调试，#define不可以进行调试
在类中定义常量有两种方式
1、 在类在声明常量，但不赋值，在构造函数初始化表中进行赋值；
2、 用枚举代替const常量。
六、C++函数中值的传递方式
有三种方式：值传递(Pass by value)、指针传递(Pass by pointer)、引用传递(Pass by reference)
void fun(char c) //pass by value
void fun(char *str) //pass by pointer
void fun(char &str) //pass by reference
如果输入参数是以值传递的话，最好使用引用传递代替，因为引用传递省去了临时对象的构造和析构
函数的类型不能省略，就算没有也要加个void
七、函数体中的指针或引用常量不能被返回
Char *func(void)
{
char str[]=”Hello Word”;
//这个是不能被返回的，因为str是个指向栈内存的指针，不是一般的值，函数结束后会被注销掉
return str;
}
函数体内的指针变量并不会随着函数的消亡而自动释放
例子:
char * fun(void)
{
char * st="hello ssssssssssssss ";
return st; //函数体内的指针变量并不会随着函数的消亡而自动释放
}
void main()
{
char *p3;
p3 = fun()
printf(p3);
}
八、一个内存拷贝函数的实现体
void *memcpy(void *pvTo,const void *pvFrom,size_t size)
{
assert((pvTo!=NULL)&&(pvFrom!=NULL));
byte *pbTo=(byte*)pvTo; //防止地址被改变
byte *pbFrom=(byte*)pvFrom;
while (size-- >0)
pbTo++ = pbForm++;
return pvTo;
}
九、内存的分配方式
分配方式有三种，请记住，说不定那天去面试的时候就会有人问你这问题
1、 静态存储区，是在程序编译时就已经分配好的，在整个运行期间都存在，如全局变量、常量。
2、 栈上分配，函数内的局部变量就是从这分配的，但分配的内存容易有限。
3、 堆上分配，也称动态分配，如我们用new,malloc分配内存，用delete,free来释放的内存。
十、内存分配的注意事项
用new或malloc分配内存时，必须要对此指针赋初值。
用delete 或free释放内存后，必须要将指针指向NULL
不能修改指向常量的指针数据
十一、内容复制与比较
//数组……
char a[]=”Hello Word!”;
char b[10];
strcpy(b,a);
if (strcmp(a,b)==0)
{}
//指针……
char a[]=”Hello Word!”;
char *p;
p=new char[strlen(a)+1];
strcpy(p,a);
if (strcmp(p,a)==0)
{}
十二、sizeof的问题
记住一点，C++无法知道指针所指对象的大小，指针的大小永远为4字节
char a[]=”Hello World!”
char *p=a;
count sizeof(a) end; //12字节
count sizeof(p) endl; //4字节
而且，在函数中，数组参数退化为指针，所以下面的内容永远输出为4
void fun(char a[1000])
{
count sizeof(a) endl; //输出4而不是1000
}
十三、关于指针
1、 指针创建时必须被初始化
2、 指针在free 或delete后必须置为NULL
3、 指针的长度都为4字节
４、释放内存时，如果是数组指针，必须要释放掉所有的内存，如
char *p=new char[100];
strcpy(p,”Hello World”);
delete []p; //注意前面的[]号
p=NULL;//置为NULL
５、数组指针的内容不能超过数组指针的最大容易。
如:
char *p=new char[5];
strcpy(p,”Hello World”); //报错 目标容易不够大
delete []p; //注意前面的［］号
p=NULL;
十四、关于malloc/free 和new /delete
l malloc/free 是C/C+的内存分配符，new /delete是C++的内存分配符。
l 注意：malloc/free是库函数，new/delete是运算符
l malloc/free不能执行构造函数与析构函数，而new/delete可以
l new/delete不能在C上运行，所以malloc/free不能被淘汰
l 两者都必须要成对使用
l C++中可以使用_set_new_hander函数来定义内存分配异常的处理
十五、Ｃ++的特性
Ｃ++新增加有重载(overload)，内联（inline），Const，Virtual四种机制
重载和内联：即可用于全局函数，也可用于类的成员函数；
Const和Virtual：只可用于类的成员函数；
重载：在同一类中，函数名相同的函数。由不同的参数决定调用那个函数。函数可要不可要Virtual关键字。和全局函数同名的函数
不叫重载。如果在类中调用同名的全局函数，必须用全局引用符号::引用。
覆盖是指派生类函数覆盖基类函数
函数名相同；
参数相同；
基类函数必须有Virtual关键字；
不同的范围(派生类和基类)。
隐藏是指派生类屏蔽了基类的同名函数相同
1、 函数名相同，但参数不同，此时不论基类有无Virtual关键字，基类函数将被隐藏。
2、 函数名相同，参数也相同，但基类无Virtual关键字(有就是覆盖)，基类函数将被隐藏。
内联：inline关键字必须与定义体放在一起，而不是单单放在声明中。
Const：const是constant的缩写，“恒定不变”的意思。被const修饰的东西都受到强制保护，可以预防意外的变动，能提高程序的
健壮性。
1、 参数做输入用的指针型参数，加上const可防止被意外改动。
2、 按值引用的用户类型做输入参数时，最好将按值传递的改为引用传递，并加上const关键字，目的是为了提高效率。数据类型为
内部类型的就没必要做这件事情；如：
将void Func(A a) 改为void Func(const A &a)。
而void func(int a)就没必要改成void func(const int &a);
3、 给返回值为指针类型的函数加上const，会使函数返回值不能被修改，赋给的变量也只能是const型变量。如：函
数const char*GetString(void); char *str=GetString()将会出错。而const char *str=GetString()将是正确的。
4、 Const成员函数是指此函数体内只能调用Const成员变量，提高程序的键壮性。如声明函数 int GetCount(void) const;此函数
体内就只
能调用Const成员变量。
Virtual：虚函数：派生类可以覆盖掉的函数，纯虚函数：只是个空函数，没有函数实现体；
十六、extern“C”有什么作用？
Extern “C”是由Ｃ＋＋提供的一个连接交换指定符号，用于告诉Ｃ＋＋这段代码是Ｃ函数。这是因为C++编译后库中函数名会变
得很长，与C生成的不一致，造成Ｃ＋＋不能直接调用C函数，加上extren “c”后，C++就能直接调用C函数了。
Extern “C”主要使用正规DLL函数的引用和导出 和 在C++包含C函数或C头文件时使用。使用时在前面加上extern “c” 关键字即
可。
十七、构造函数与析构函数
派生类的构造函数应在初始化表里调用基类的构造函数；
派生类和基类的析构函数应加Virtual关键字。
不要小看构造函数和析构函数，其实编起来还是不容易。
＃i nclude
using namespace std;
class Base
{
public:
virtual ~Base() { cout "~Base" endl ; }
};
class Derived : public Base
{
public:
virtual ~Derived() { cout "~Derived" endl ; }
};
void main(void)
{
Base * pB = new Derived; // upcast
delete pB;
cin.get();
}
输出结果为：
~Derived
~Base
如果析构函数不为虚，那么输出结果为
~Base
十八、#IFNDEF/#DEFINE/#ENDIF有什么作用
仿止该头文件被重复引用
一、＃i nclude “filename.h”和＃i nclude filename.h>的区别
＃i nclude “filename.h”是指编译器将从当前工作目录上开始查找此文件
＃i nclude filename.h>是指编译器将从标准库目录中开始查找此文件
二、头文件的作用
加强安全检测
通过头文件可能方便地调用库功能，而不必关心其实现方式
三、* , &修饰符的位置
对于*和&修饰符，为了避免误解，最好将修饰符紧靠变量名
四、if语句
不要将布尔变量与任何值进行比较，那会很容易出错的。
整形变量必须要有类型相同的值进行比较
浮点变量最好少比点，就算要比也要有值进行限制
指针变量要和NULL进行比较，不要和布尔型和整形比较
五、const和#define的比较
const有数据类型，#define没有数据类型
个别编译器中const可以进行调试，#define不可以进行调试
在类中定义常量有两种方式
1、 在类在声明常量，但不赋值，在构造函数初始化表中进行赋值；
2、 用枚举代替const常量。
六、C++函数中值的传递方式
有三种方式：值传递(Pass by value)、指针传递(Pass by pointer)、引用传递(Pass by reference)
void fun(char c) //pass by value
void fun(char *str) //pass by pointer
void fun(char &str) //pass by reference
如果输入参数是以值传递的话，最好使用引用传递代替，因为引用传递省去了临时对象的构造和析构
函数的类型不能省略，就算没有也要加个void
七、函数体中的指针或引用常量不能被返回
Char *func(void)
{
char str[]=”Hello Word”;
//这个是不能被返回的，因为str是个指定变量，不是一般的值，函数结束后会被注销掉
return str;
}
函数体内的指针变量并不会随着函数的消亡而自动释放
八、一个内存拷贝函数的实现体
void *memcpy(void *pvTo,const void *pvFrom,size_t size)
{
assert((pvTo!=NULL)&&(pvFrom!=NULL));
byte *pbTo=(byte*)pvTo; //防止地址被改变
byte *pbFrom=(byte*)pvFrom;
while (size-- >0)
pbTo++ = pbForm++;
return pvTo;
}
九、内存的分配方式
分配方式有三种，请记住，说不定那天去面试的时候就会有人问你这问题
1、 静态存储区，是在程序编译时就已经分配好的，在整个运行期间都存在，如全局变量、常量。
2、 栈上分配，函数内的局部变量就是从这分配的，但分配的内存容易有限。
3、 堆上分配，也称动态分配，如我们用new,malloc分配内存，用delete,free来释放的内存。
十、内存分配的注意事项
用new或malloc分配内存时，必须要对此指针赋初值。
用delete 或free释放内存后，必须要将指针指向NULL
不能修改指向常量的指针数据
十一、内容复制与比较
//数组……
char a[]=”Hello Word!”;
char b[10];
strcpy(b,a);
if (strcmp(a,b)==0)
{}
//指针……
char a[]=”Hello Word!”;
char *p;
p=new char[strlen(a)+1];
strcpy(p,a);
if (strcmp(p,a)==0)
{}
十二、sizeof的问题
记住一点，C++无法知道指针所指对象的大小，指针的大小永远为4字节
char a[]=”Hello World!”
char *p=a;
count sizeof(a) end; //12字节
count sizeof(p) endl; //4字节
而且，在函数中，数组参数退化为指针，所以下面的内容永远输出为4
void fun(char a[1000])
{
count sizeof(a) endl; //输出4而不是1000
}
十三、关于指针
1、 指针创建时必须被初始化
2、 指针在free 或delete后必须置为NULL
3、 指针的长度都为4字节
４、释放内存时，如果是数组指针，必须要释放掉所有的内存，如
char *p=new char[100];
strcpy(p,”Hello World”);
delete []p; //注意前面的［］号
p=NULL;
５、数组指针的内容不能超过数组指针的最大容易。
如:
char *p=new char[5];
strcpy(p,”Hello World”); //报错 目标容易不够大
delete []p; //注意前面的［］号
p=NULL;
十四、关于malloc/free 和new /delete
l malloc/free 是C/C+的内存分配符，new /delete是C++的内存分配符。
l 注意：malloc/free是库函数，new/delete是运算符
l malloc/free不能执行构造函数与析构函数，而new/delete可以
l new/delete不能在C上运行，所以malloc/free不能被淘汰
l 两者都必须要成对使用
l C++中可以使用_set_new_hander函数来定义内存分配异常的处理
十五、Ｃ++的特性
Ｃ++新增加有重载(overload)，内联（inline），Const，Virtual四种机制
重载和内联：即可用于全局函数，也可用于类的成员函数；
Const和Virtual：只可用于类的成员函数；
重载：在同一类中，函数名相同的函数。由不同的参数决定调用那个函数。函数可要不可要Virtual关键字。和全局函数同名的函数
不叫重载。如果在类中调用同名的全局函数，必须用全局引用符号::引用。
覆盖是指派生类函数覆盖基类函数
函数名相同；
参数相同；
基类函数必须有Virtual关键字；
不同的范围(派生类和基类)。
隐藏是指派生类屏蔽了基类的同名函数相同
1、 函数名相同，但参数不同，此时不论基类有无Virtual关键字，基类函数将被隐藏。
2、 函数名相同，参数也相同，但基类无Virtual关键字(有就是覆盖)，基类函数将被隐藏。
内联：inline关键字必须与定义体放在一起，而不是单单放在声明中。
Const：const是constant的缩写，“恒定不变”的意思。被const修饰的东西都受到强制保护，可以预防意外的变动，能提高程序的健壮性。
1、 参数做输入用的指针型参数，加上const可防止被意外改动。
2、 按值引用的用户类型做输入参数时，最好将按值传递的改为引用传递，并加上const关键字，目的是为了提高效率。数据类型为内部类型
的就没必要做这件事情；如：
将void Func(A a) 改为void Func(const A &a)。
而void func(int a)就没必要改成void func(const int &a);
3、 给返回值为指针类型的函数加上const，会使函数返回值不能被修改，赋给的变量也只能是const型变量。如：函
数const char*GetString(void); char *str=GetString()将会出错。而const char *str=GetString()将是正确的。
4、 Const成员函数是指此函数体内只能调用Const成员变量，提高程序的键壮性。如声明函数 int GetCount(void) const;此函数体内就只能
调用Const成员变量。
Virtual：虚函数：派生类可以覆盖掉的函数，纯虚函数：只是个空函数，没有函数实现体；
十六、extern“C”有什么作用？
Extern “C”是由Ｃ＋＋提供的一个连接交换指定符号，用于告诉Ｃ＋＋这段代码是Ｃ函数。这是因为C++编译后库中函数名会变得
很长，与C生成的不一致，造成Ｃ＋＋不能直接调用C函数，加上extren “c”后，C++就能直接调用C函数了。
Extern “C”主要使用正规DLL函数的引用和导出 和 在C++包含C函数或C头文件时使用。使用时在前面加上extern “c” 关键字即可。
十七、构造函数与析构函数
派生类的构造函数应在初始化表里调用基类的构造函数；
派生类和基类的析构函数应加Virtual关键字。
不要小看构造函数和析构函数，其实编起来还是不容易。
＃i nclude iostream.h>
class Base
{
public:
virtual ~Base() { cout "~Base" endl ; }
};
class Derived : public Base
{
public:
virtual ~Derived() { cout "~Derived" endl ; }
};
void main(void)
{
Base * pB = new Derived; // upcast
delete pB;
}
输出结果为：
~Derived
~Base
如果析构函数不为虚，那么输出结果为
~Base
十八、#IFNDEF/#DEFINE/#ENDIF有什么作用
仿止该头文件被重复引用
学习C++必须掌握的概念
一、指针的概念
char str[] = “ABCDEFG”;
char *pc = str; //pc是指向string str的指针
short x = 33;
short *px = &x; //px是指向short x的指针
cout *pc endl; //这条语句将打印字符‘A’
pc += 4; //指针向右移动4指向第5个字符
cout *pc endl; //这时这条语句将打印字符‘E’
pc--; //向左移动指针
cout *pc endl; //这时这条语句将打印字符‘D’
cout *px + 3 endl; //这条语句打印36因为=33+3
在 C 程序中,假设我们已定义了以下的几个变量及函数: int k, tem, *P1, *P2, a[5], f(), *P3(); 以下的设定
叙述(Assignment statements)中, 那些有语法上的错误? 并请说明其原因
1.P1 = &k;
2.P2 = a;
3.P3 = f;
4.P1 = &a[3];
5.P1 = P2;
答案:
(1) P1 = &k; P1是指针变量, 因此P1表位址,而k表示一般变量,&k表示取出k的位址,故正确.
(2) P2 = a; a是数组名称,此时可代表数组存放在内存中的起始位址,而P2为指针变量,故正确.
(3) P3 = f; f代表函数的名称,此时代表呼叫函数f,因此含有传回值,而P3为指针变量,故此式有错误.
(4) P1 = &a[3];P1表指针变量,代表位址,而&a[3]表取出索引(index)为3的数组元素的位址,故正确.
(5) P1 = P2; P1,P2皆为指针变量代表位址,此叙述是指将P2的位址指定给P1,故正确.
结构的概念
结构是一种类型，它的成员默认是public.
struct Student //定义一个结构Student用来存放学生的资料
{
int id; //编号
char name[30]; //名字
}
Student s = {555, “Davis, Samuel”}; //初始化Student的实例s
cout s.id “ “ s.name endl; //这条将打印“ 555 Davis,Samuel”
类的概念我想大家都应该很清楚了，我就不废话了。
类的继承的概念
class base
{
private:
int a;
protected:
int b;
public:
int c;
};
class sub1:public base {…};
class sub2:private base{…};
说明在base,sub1,sub2中所能取用的data members各为何.并指出这些data members的access mode(private, protected或public).
Ans:
class data members access mode
base a private
b protected
c public
sub1
b protected
c public
sub2
b private
c private
虚函数和抽象类
多态 (polymorphism)
面向对象程设计的核心观念之一就是多态--它使一群类似的行为的同名称的方法, 但各对象可依适合自己所需的方式建构此同名动作的实行
细节, C++多态的关键在于所谓的虚函数这一类的函数。
虚函数(virtual function)
透过虚拟函数, 衍生类可重新定义基类的成员函数, 若想在C++程式中建立虚拟函数(然後才能实行多态), 只需利用virtual关键字声明函数即
可(如下所示)
virtual void Display();
虚函数的用处
针对共享相同基类的那些对象, 可有较一致的使用态度, 例如, 你可能定义一个名为Shape且带有一 个Draw虚拟成员函数的基类, 然后从它派
生了Circle类和Square类, 而且它们各自带有自己的Draw成员函数.从这些类派生建立的每个对象都可呼叫Draw成员函数; 但是编译程式可确
保各自应呼叫那个版本的Draw 函数.是基类的还是派生类的。
一个例子
重要观念: 指向父类的指针也可用来指向子类别
＃i nclude iostream.h>
class BaseClass
{
public:
virtual void Display( ) { cout 100 "\n"; }
};
class DerivedClass: public BaseClass
{
public:
virtual void Display( ) { cout 200 "\n"; }
};
void Print(BaseClass* pbc)
{ pbc->Display( ); }
int main( )
{ BaseClass* pbc = new BaseClass;
DerivedClass* pdc = new DerivedClass;
Print(pbc);//显示 100
Print(pdc);//显示 200
return 0;
}
V-table (Virtual function table)
当C++程式呼叫非虚函数, 采用与C程式呼叫函数所用方式一样的静态绑定来呼叫函数. 但是C++程式 若是透过指向类别的指针来呼叫虚函数
时, 编译程式则采用所谓的晚期绑定(late binding)或静态绑定 (static binding)技术来呼叫函数.
而C++虚函数用虚函数表(virtual function table), 或称V-表来实作动态绑定, 所谓的V-表是一 个函数指针的阵列, 这是编译程序替每个
使用虚函数的类所建制的。
纯虚函数 (pure virtual function)
一个不仅可被重新定义, 而且必须被重新定义的成员函数就称为纯虚函数, 你只要指定函数一个零值 (更有效说法是一个空指针),就可将虚
成员函数转为纯虚成员函数,如以下所示
virtual void PrintData() = 0;
抽象类 (abstract class)
当一个类含有至少一个纯虚函数时, 此类就称为抽象类,而你无法以此类来衍生建立对象.
C++ template classes
一般的声明及使用
class Collection
{ …
int A[10];
}
Collection object;
模板的声明及使用
template class T> //注意这里
class Collection
{ …
T A[10]; }// generic declaration
Collection int> object; //注意这里
Collection char> object; //注意这里
冒泡排序
陀陀木修 发表于2005-5-22 12:23:00
1、排序方法
将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往
上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
（1）初始
R[1..n]为无序区。
（2）第一趟扫描
从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key 第一趟扫描完毕时，"最轻"的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上。
（3）第二趟扫描
扫描R[2..n]。扫描完毕时，"次轻"的气泡飘浮到R[2]的位置上……
最后，经过n-1 趟扫描可得到有序区R[1..n]
注意：
第i趟扫描时，R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最
轻气泡飘浮到顶部位置R[i]上，结果是R[1..i]变为新的有序区。
2、冒泡排序过程示例
对关键字序列为49 38 65 97 76 13 27 49的文件进行冒泡排序的过程【参见动画演示】
3、排序算法
（1）分析
因为每一趟排序都使有序区增加了一个气泡，在经过n-1趟排序之后，有序区中就有n-1个气泡，而无序区中气泡的重量总是大于等于
有序区中气泡的重量，所以整个冒泡排序过程至多需要进行n-1趟排序。
若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程
可在此趟排序后终止。为此，在下面给出的算法中，引入一个布尔量exchange，在每趟排序开始前，先将其置为FALSE。若排序过程中发生了交换，则将其置为TRUE。各趟排序结束时检查exchange，若未曾发生过交换则终止算法，不再进行下一趟排序。
（2）具体算法
void BubbleSort(SeqList R)
{ //R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序
int i，j；
Boolean exchange； //交换标志
for(i=1;i exchange=FALSE； //本趟排序开始前，交换标志应为假
for(j=n-1;j>=i；j--) //对当前无序区R[i..n]自下向上扫描
if(R[j+1].key R[0]=R[j+1]； //R[0]不是哨兵，仅做暂存单元
R[j+1]=R[j]；
R[j]=R[0]；
exchange=TRUE； //发生了交换，故将交换标志置为真
}
if(!exchange) //本趟排序未发生交换，提前终止算法
return；
} //endfor(外循环)
} //BubbleSort
4、算法分析
（1）算法的最好时间复杂度
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：
Cmin=n-1
Mmin=0。
冒泡排序最好的时间复杂度为O(n)。
（2）算法的最坏时间复杂度
若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
Cmax=n(n-1)/2=O(n2)
Mmax=3n(n-1)/2=O(n2)
冒泡排序的最坏时间复杂度为O(n2)。
（3）算法的平均时间复杂度为O(n2)
虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。
（4）算法稳定性
冒泡排序是就地排序，且它是稳定的。
5、算法改进
上述的冒泡排序还可做如下的改进：
(1)记住最后一次交换发生位置lastExchange的冒泡排序
在每趟扫描中，记住最后一次交换发生的位置lastExchange，（该位置之前的相邻记录均已有序）。下一趟排序开始时，R[1..lastExchange-1]是有序区，R[lastExchange..n]是无序区。这样，一趟排序可能使当前有序区扩充多个记录，从而减少排序的趟数。具体算法【参见习题】。
(2) 改变扫描方向的冒泡排序
①冒泡排序的不对称性
能一趟扫描完成排序的情况：
只有最轻的气泡位于R[n]的位置，其余的气泡均已排好序，那么也只需一趟扫描就可以完成排序。
【例】对初始关键字序列12，18，42，44，45，67，94，10就仅需一趟扫描。
需要n-1趟扫描完成排序情况：
当只有最重的气泡位于R[1]的位置，其余的气泡均已排好序时，则仍需做n-1趟扫描才能完成排序。
【例】对初始关键字序列：94，10，12，18，42，44，45，67就需七趟扫描。
②造成不对称性的原因
每趟扫描仅能使最重气泡"下沉"一个位置，因此使位于顶端的最重气泡下沉到底部时，需做n-1趟扫描。
③改进不对称性的方法
在排序过程中交替改变扫描方向，可改进不对称性。具体算法【参见习题】。
C++，这个词在中国大陆的程序员圈子中通常被读做“C加加”，而西方的程序员通常读做“see plus plus”， 它是一种被使用的非常广泛的计算机编程语言。C++是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。它支持过程序程序设计、数据抽象、面向对象程序设计、泛型程序设计等多种程序设计风格。
布贾尼•斯特劳斯特卢普（Bjarne Stroustrup）博士在20世纪80年代发明并实现了C++（最初这种语言被称作“C with Classes”）。一开始C++是作为C语言的增强版出现的，从给C语言增加类开始，不断的增加新特性。虚函数、运算符重载、多重继承、模板、异常、RTTI、名字空间逐渐被加入标准。1998年国际标准组织（ISO）颁布了C++程序设计语言的国际标准ISO/IEC 14882-1998。遗憾的是，由于C++语言过于复杂，以及他经历了长年的演变，直到现在（2004年）只有少数几个完全符合这个标准的编译器出现。
另外，就目前学习C++而言，可以认为他是一门独立的语言；他并不依赖C语言，我们可以完全不学C语言，而直接学习C++。根据《C++编程思想》（Thinking in C++）一书所评述的，C++与C的效率往往相差在正负5%之间。所以有人认为在大多数场合C++ 完全可以取代C语言。
C++语言发展大概可以分为三个阶段：第一阶段从80年代到1995年。这一阶段C++语言基本上是传统类型上的面向对象语言，并且凭借着接
近C语言的效率，在工业界使用的开发语言中占据了相当大份额；第二阶段从1995年到2000年，这一阶段由于STL和后来的Boost等程序库的出
现，泛型程序设计在C++中占据了越来越多的比重性。当然，同时由于Java、C#等语言的出现和硬件价格的大规模下降，C++开始逐渐退出用户
级程序的开发领域，转向系统级别的程序开发；第三阶段从2000年至今，由于以Loki、MPL等程序库为代表的产生式编程和模板元编程的出
现，C++出现了发展历史上又一个新的高峰，这些新技术的出现以及和原有技术的融合，使C++已经成为当今主流程序设计语言中最庞大，最
复杂的一员。
何为算法？
陀陀木修 发表于2005-5-22 12:09:00
不论您在您的生活或工作中是否已经注意到，算法的直接或隐含的存在已经日益增多。算法是软件运算部分功能的基础，它存在于嵌入或
非嵌入的系统中间，默默地做着底层的事情。有些计算的功能是显而易见的，因此在编程的过程中算法并不显得很重要，不需要单独去考虑它，例如控制单一的开关，或单一的视窗。而越来越多与物理世界相关的复杂运算，人们并不直接地了解如何去算；那么在编程的过程中就需要对于这些算法进行开发；例如，如何最有效地压缩音乐信号数据，诸如通行的MP3算法；或者手机里面的GSM编解码算法。
计算机硬件的发展的速度之快，在其存储量与运算速度方面都早已超过了人类大脑。但是，却因为大大缺少足够的算法，使人们尚做不出
能够充分使用这些硬件的软件，以至于巨大的计算机还模拟不出一个简单蚂蚁的功能。模拟人类就更加遥远，即使是模拟人类的某个单一功能，如，语音对话。
那些已经相对成熟并经常使用的算法，就已经被固化在软件模块里面，甚至半导体芯片之中；可以方便地直接使用而无须重新开发。越是
尚未成熟标准化的领域，算法越需要直接去开发，例如语音识别的算法。更有人类与日俱增的观察世界和控制世界的欲望，了解自身、相互沟
通、以及提高生活的舒适程度的愿望。而这些新的愿望在刚出现的时候，往往还没有已经固化的算法可供选用，这样就不断产生出对新的算法
研发的需求。当然也存在由于商业的考虑而需要‘重新发明车轮’的情况。
任何算法以及软件都是要在一定的硬件系统中运行。一个完整的计算机或嵌入电子装置的功能，都是软、硬件结合的结果。因此系统结构
的合理性和算法同样很重要。但是，我们工作室的侧重面是对算法的探讨、研发和设计、实现。对于系统我们仅仅是去优化地选择使用，并不
花主要的精力去设计。在一切情况下，对于算法的需求包括未知算法本身的研发，以及已知算法在具体系统中的实现。
可以运用分而治之方法来解决排序问题，该问题是将n 个元素排成非递减顺序。分而治之方法通常用以下的步骤来进行排序算法：若n 为1，算法终止；否则，将这一元素集合分割成两个或更多个子集合，对每一个子集合分别排序，然后将排好序的子集合归并为一个集合。
假设仅将n 个元素的集合分成两个子集合。现在需要确定如何进行子集合的划分。一种可能性就是把前面n- 1个元素放到第一个子集中（称为A），最后一个元素放到第二个子集里（称为B）。按照这种方式对A递归地进行排序。由于B仅含一个元素，所以它已经排序完毕，在A排完序后，只需要用程序2 - 1 0中的函数i n s e r t将A和B合并起来。把这种排序算法与I n s e r t i o n S o r t（见程序2 - 1 5）进行比较，可以发现这种排序算法实际上就是插入排序的递归算法。该算法的复杂性为O (n 2 )。把n 个元素划分成两个子集合的另一种方法是将含有最大值的元素放入B，剩下的放入A中。然后A被递归排序。为了合并排序后的A和B，只需要将B添加到A中即可。假如用函数M a x（见程序1 - 3 1）来找出最大元素，这种排序算法实际上就是S e l e c t i o n S o r t（见程序2 - 7）的递归算法。
假如用冒泡过程（见程序2 - 8）来寻找最大元素并把它移到最右边的位置，这种排序算法就是B u b b l e S o r t（见程序2 - 9）的递归算法。这两种递归排序算法的复杂性均为(n2 )。若一旦发现A已经被排好序就终止对A进行递归分割，则算法的复杂性为O(n2 )（见例2 - 1 6和2 - 1 7）。
上述分割方案将n 个元素分成两个极不平衡的集合A和B。A有n- 1个元素，而B仅含一个元素。下面来看一看采用平衡分割法会发生什么情况： A集合中含有n/k 个元素，B中包含其余的元素。递归地使用分而治之方法对A和B进行排序。然后采用一个被称之为归并（ m e rg e）的过程，将已排好序的A和B合并成一个集合。
例2-5 考虑8个元素，值分别为[ 1 0，4，6，3，8，2，5，7 ]。如果选定k = 2，则[ 1 0 , 4 , 6 , 3 ]和[ 8 , 2 , 5 , 7 ]将被分别独立地排序。结果分别为[ 3 , 4 , 6 , 1 0 ]和[ 2 , 5 , 7 , 8 ]。从两个序列的头部开始归并这两个已排序的序列。元素2比3更小，被移到结果序列；3与5进行比较，3被移入结果序列；4与5比较，4被放入结果序列；5和6比较，.。如果选择k= 4，则序列[ 1 0 , 4 ]和[ 6 , 3 , 8 , 2 , 5 , 7 ]将被排序。排序结果分别为[ 4 , 1 0 ]和[ 2 , 3 , 5 , 6&n
文章来源：CSDN
|