一、程序员面试宝典学习笔记
1.数据类型和类型转换
Type Size数值范围
无值型void0 byte无值域
布尔型bool 1 byte true false
有符号短整型short [int] /signed short [int] 2 byte-32768~32767
无符号短整型unsigned short [int] 2 byte0~65535
有符号整型int /signed [int] 4 byte-2147483648~2147483647
无符号整型unsigned [int] 4 byte0~4294967295
有符号长整型long [int]/signed long [int] 4 byte-2147483648~2147483647
无符号长整型unsigned long [int] 4 byte0~4294967295
long long8 byte0~18446744073709552000
有符号字符型char/signed char 1 byte-128~127
无符号字符型unsigned char 1 byte0~255
宽字符型wchar_t (unsigned short.) 2 byte0~65535
单精度浮点型float 4 byte-3.4E-38~3.4E+38
双精度浮点型double8 byte 1.7E-308~1.7E+308
long double8 byte
因此在类型转换的时候size大的强制转换成size小的类型就会发生截断。例如：
int a = 0x12345678;
char j = (char)a;
printf("a = %08x , j= %08x\n",a , j);
2.运算符优先级
1. () [] -> . ::最高
2. 单目次之（++ -- 在后比在前高）
3. 双目依次：算术，移位，关系，位，逻辑
4. 三目
5. 赋值
6. 单目、三目和赋值右结合。
3. C++ 程序中调用C程序需要加extern C
原因是因为C++支持函数重载（因而编译器产生的函数名不同，比如函数void foo(int x,int y)在C的编译器中可能产生为_foo，而在C++中可能产生为_foo_int_int之类）
Extern C的用法：
Phello.h文件：
#ifndef _PHELLO_H
#define _PHELLO_H
#ifdef __cplusplus //__cplusplus是cpp中的自定义宏，那么定义了这个宏的话表示这是一段cpp的代码extern "C"
{
#endif
extern int add(int x,int y);
#ifdef __cplusplus
}
#endif
#endif
Phello.c文件：
#ifndef _PHELLO_C
#define _PHELLO_C
int add(int x,int y) {return x+y;}
#endif
Main.cpp文件：
#include
#include "phello.h"
using namespace std;
int main(int argc, char *argv[])
{
int x=100,y=90;
int z;
z=add(x,y);
cout< } 4. 宏 写宏的时候注意两点： 1.参数注意用括号括起来 例如：#define W ANG(x,y) ((x)<(y)?(x):(y)) //防止展开的时候因为优先级问题导致逻辑错误2.定义大整数时注意加UL 例如：#define W ANG 1000000UL 5. mutable 作用 在const成员函数中，用mutable修饰成员变量之后，就可以修改类的成员变量 6.sizeof和内存对齐 struct A{ char m; long l; char s; }; struct B{ char m; char n; long l; }; struct C{ double d; char m; }; struct D{ static int a; int x; }; double returndouble(int x) { return x; } int main(int argc, char *argv[]) { char a[10]="123456789"; cout< char *b="123456789"; cout< char c[100]="123"; cout< int e[100]={1,2,3,4}; cout< char *d = (char*)malloc(100); cout< static int f = 100; cout< cout< cout< cout< cout< cout<<"FUNCTION: "< } Sizeof和strlen的区别： 1.Sizeof是运算符，strlen是函数。这导致传数组参数的时候后者会退化为指针，同时导致另一个区别 sizeof通常在编译阶段计算，strlen在运行阶段计算。 2.Sizeof 后如果是类型必须加括号，如果是变量则不需加括号，strlen只能计算变量 Sizeof应用于类： 1.空类为1，单一继承或者多重继承空类的类也为1，但是虚继承有指针则为4. 2.不带virtual的普通类，和struct类似，也要考虑对齐的问题。普通成员函数不分配空间。 3.只要带有virtual函数，编译器在编译时就会自动插入一个指向虚函数表的指针vptr(大小为4字节). 7. 指针 （1）地址相减： int main(int argc, char *argv[]) { int x =10; int y = 20; int *xp =&x; int *yp = &y; cout< cout< cout<<(xp-yp)< } （2）类指针强制转换 class A{ private: int x; int y; public: A(){ x=10;y=20; } void fun(){ cout< } }; class B{ private: int z; public: B(){ z=30; } void fun() { cout< } }; int main(int argc, char *argv[]) { A a; B* pb= (B*)(&a); pb->fun(); //打印10 } （3）函数指针 int max(int x,int y){ return (x>y?x:y);} int min(int x,int y){ return (x int main(int argc, char *argv[]) { int m=100; int n=10; int (*cmp)(int,int); cmp = max; //等价于cmp = &max; cout< cmp = min; //可见只要函数原型相同就可以指向不同的函数cout< } （4）指针数组和指向数组的指针 Int *a[10]; //包含十个指针的数组 Int (*a)[10]; //指向数组的指针 （5）安全指针（智能指针auto_ptr） 主要缺点：缺少对引用数和数组的支持，不可将auto_ptr对象作为STL容器的元素 int rt(int x) { auto_ptr *p = 10; if(x==1)return 0; //如果不用安全指针这里就会造成内存泄露 else { free(p); return 1; } } 8. 面向对象 （1）const成员变量 Class A { //Const int size = 100; //错误 Static const int size = 100; }; （2） 1. 基类的析构函数最好为虚函数：这样在撤销指向子类对象的基类指针的时候才可以调用子类的析构函数，避免内存泄露（如果子类对象分配了内存空间的话）。 2. 构造函数不能为virtual：因为在创建对象的时候必须准确的知道对象的类型，而虚函数采用的是虚调用，这是一种可以在只有部分信息的情况下工作的机制。 3. 析构函数可以使inline的 4. 即使子类构造函数是有参数的，但是它所递归调用的父类构造函数是无参的版本。 （3） class Base{ private: int m_x; public: Base():m_x(0){ } Base(int i):m_x(i){ cout<<"hi base"< } ~Base(){ cout<<"byebye Base"< } }; int main(int argc, char *argv[]) { Base b = play(9); } OUT: hi base //在play(9)处，9通过隐含的类型转换调用了Base::Base(int i)构造函数 byebye Base //第一次析构，是在函数play返回时调用的 byebye Base //temp的析构函数调用；temp的构造函数调用的是编译器生成的拷贝构造函数 9. 编写string的构造函数、析构函数、拷贝构造函数、赋值函数以 及<<函数 很基础很重要！！ #include using namespace std; class mystring{ friend ostream& operator<<(ostream &os, const mystring &ms); public: mystring(const char * str = NULL); mystring(const mystring &other); ~mystring(); mystring& operator=(const mystring &other); private: char *m_data; }; mystring::~mystring() { delete [] m_data; } mystring::mystring(const char * str) { if(str == NULL) { m_data = new char[1]; *m_data = '\0'; } else { int length = strlen(str); m_data = new char[length + 1]; strcpy(m_data, str); } } mystring::mystring(const mystring& ms) { int length = strlen(ms.m_data); m_data = new char[length + 1]; strcpy(m_data, ms.m_data); } mystring& mystring::operator=(const mystring& ms) { if(&ms == this) { return *this; } delete [] m_data; int length = strlen(ms.m_data); m_data = new char[length + 1]; strcpy(m_data, ms.m_data); } ostream& operator<<(ostream& os, const mystring & ms) { cout< return os; } 10. 异常处理 程序中的错误分为编译时的错误和运行时的错误。把程序运行时的错误统称为异常，对异常处理称为异常处理。 C++中处理异常的过程是这样的：在执行程序发生异常，可以不在本函数中处理，而是抛出一个错误信息，把它传递给上一级的函数来解决，上一级解决不了，再传给其上一级，由其上一级处理。如此逐级上传，直到最高一级还无法处理的话，运行系统会自动调用系统函数terminate，由它调用abort终止程序。这样的异常处理方法使得异常引发和处理机制分离，而不在同一个函数中处理。这使得底层函数只需要解决实际的任务，而不必过多考虑对异常的处理，而把异常处理的任务交给上一层函数去处理。 C++的异常处理机制有3部分组成：try(检查)，throw(抛出)，catch(捕获)。把需要检查的语句放在try 模块中，检查语句发生错误，throw抛出异常，发出错误信息，由catch来捕获异常信息，并加以处理。一般throw抛出的异常要和catch所捕获的异常类型所匹配。异常处理的一般格式为：try { 被检查语句 throw 异常 } catch(异常类型1) { 进行异常处理的语句1 } catch(异常类型2) { 进行异常处理的语句2 } ... 几点注意： (1)try和catch块中必须要用花括号括起来，即使花括号内只有一个语句也不能省略花括号; (2)try和catch必须成对出现，一个try_catch结果中只能有一个try块，但可以有多个catch块，以便与不同的异常信息匹配; (3)如果在catch块中没有指定异常信息的类型，而用删节号"..."，则表示它可以捕获任何类型的异常信息; (4)如果throw不包括任何表达式，表示它把当前正在处理的异常信息再次抛出，传给其上一层的catch 来处理; (5)C++中一旦抛出一个异常，如果程序没有任何的捕获，那么系统将会自动调用一个系统函数terminate，由它调用abort终止程序; 举例： template T Div(T x,T y) { if(0==y) throw y; return x/y; } int main(int argc, char *argv[]) { int x=5; int y=0; double dx = 5; double dy = 0; try{ cout< cout< } catch(...) { try { cout<<"none type wrong!!1"< throw; } catch(int) { cout<<"int wrong!!"< } catch(double) { cout<<"double wrong!!"< } } return 0; } 11. assert用法 assert宏的原型定义在 void assert( int expression ); assert的作用是现计算表达式expression ，如果其值为假（即为0），那么它先向stderr打印一条出错信息，然后通过调用abort 来终止程序运行。 //#define NDEBUG //把这里注释去掉就可以禁用assert #include int main(int argc, char *argv[]) { int i=1; int j=0; assert(j!=0); //运行到这里会报错Assertion failed: j!=0 cout< } 注意： （1）使用assert的缺点是，频繁的调用会极大的影响程序的性能，增加额外的开销。 在调试结束后，可以通过在包含#include （2）assert可以在函数开始处检验传入参数的合法性 （3）每个assert只检验一个条件,因为同时检验多个条件时,如果断言失败,无法直观的判断是哪个条件失败 不好: assert(nOffset>=0 && nOffset+nSize<=m_nInfomationSize); 好: assert(nOffset >= 0); assert(nOffset+nSize <= m_nInfomationSize); （4）不能使用改变环境的语句,因为assert只在DEBUG个生效,如果这么做,会使用程序在真正运行时遇到问题 错误: assert(i++ < 100) 这是因为如果出错，比如在执行之前i=100,那么这条语句就不会执行，那么i++这条命令就没有执行。正确: assert(i < 100) i++; 12. strcpy char* strcpy(char* strDest, const char* strSrc) { assert(strDest != NULL); assert(strSrc != NULL); char* addr = strDest; while((*strDest++ = *strSrc++)!= '\0'); return addr; } 13. 多态 多态概念（比较易懂的解释）： 多态性是允许你将父对象设置成为和它的一个或更多的子对象相等的技术，赋值之后，父对象就可以根据当前赋值给它的子对象的特性以不同的方式运作。简单地说，就是允许将子类类型的指针赋值给父类类型的指针。多态性在C++中是以虚函数实现的。 14. 虚继承 虚继承是为解决多重继承而出现的。例如：如下继承结构 A / \ B C \ / D 普通情况下会在类D中出现两次A，如果使用虚继承则可以少出现一次，节省了空间。（这里要注意，用虚继承少出现了一次A，但是B和C各增加了4字节的虚基类表指针开销，D中就加了8），下面用代码说明： class A{ char A[100]; }; class B : public A{ //class B : public virtual A{ char B[100]; }; class C : public A{ //class C : public virtual A{ char C[100]; }; class D : public B , public C{ char D[100]; }; int main(int argc, char *argv[]) { cout<<"sizeof(A)"< cout<<"sizeof(B)"< cout<<"sizeof(C)"< cout<<"sizeof(D)"< //如果按照被注释掉的代码进行虚继承，则四个值分别为：100,204,204,408 //可见的确是省了一个class A的空间，但增加了两个指针的空间 } 一旦离开了多重继承，虚拟继承就完全失去了存在的必要 -------------------------------------------------更详细的解释---------------------------------------- 定义： 虚继承：在继承定义中包含了virtual关键字的继承关系； 虚基类：在虚继承体系中的通过virtual继承而来的基类，需要注意的是： struct CSubClass : public virtual CBase {}; 其中CBase称之为CSubClass的虚基类，而不是说CBase 就是个虚基类，因为CBase还可以不不是虚继承体系中的基类。 有了上面的定义后，就可以开始虚继承和虚基类的本质研究了，下面按照语法、语义、 模型、性能和应用五个方面进行全面的描述。 1. 语法 语法有语言的本身的定义所决定，总体上来说非常的简单，如下： struct CSubClass : public virtual CBaseClass {}; 其中可以采用public、protected、private三种不同的继承关键字进行修饰，只要 确保包含virtual就可以了，这样一来就形成了虚继承体系，同时CBaseClass就成为 了CSubClass的虚基类了。 其实并没有那么的简单，如果出现虚继承体系的进一步继承会出现什么样的状况呢？ 如下所示： ////// 带有数据成员的基类 struct CBaseClass1 { CBaseClass1( size_t i ) : m_val( i ) {} size_t m_val; }; ////////虚拟继承体系 struct CSubClassV1 : public virtual CBaseClass1 { CSubClassV1( size_t i ) : CBaseClass1( i ) {} }; struct CSubClassV2 : public virtual CBaseClass1 { CSubClassV2( size_t i ) : CBaseClass1( i ) {} }; struct CDiamondClass1 : public CSubClassV1, public CSubClassV2 { CDiamondClass1( size_t i ) : CBaseClass1( i ), CSubClassV1( i ), CSubClassV2( i ) {} }; struct CDiamondSubClass1 : public CDiamondClass1 { CDiamondSubClass1( size_t i ) : CBaseClass1( i ), CDiamondClass1( i ) {} }; 注意上面代码中的CDiamondClass1和CDiamondSubClass1两个类的构造函数初始化列表中的内容。可以发现其中均包含了虚基类CBaseClass1的初始化工作，如果没有这个初始化语句就会导致编译时错误，为什么会这样呢？一般情况下不是只要在CSubClassV1和CSubClassV2中包含初始化就可以了么？要解释该问题必须要明白继承的语义特征，所以参看下面语义部分的解释。 2. 语义 从语义上来讲什么是虚继承和虚基类呢？上面仅仅是从如何在C++语言中书写合法的虚继承类定义而已。首先来了解一下virtual这个关键字在C++中的公共含义，在C++语言中仅仅有两个地方可以使用virtual这个关键字，类成员虚函数和虚继承。不要看这两种应用场合好像没什么关系，其实他们在背景语义上具有virtual这个词所代表的共同的含义，所以才会在这两种场合使用相同的关键字。 那么virtual这个词的含义是什么呢？ virtual在《美国传统词典[双解]》中是这样定义的： adj.（形容词） 1. Existing or resulting in essence or effect though not in actual fact, form, or name: 实质上的，实际上的：虽然没有实际的事实、形式或名义，但在实际上或效 果上存在或产生的； 2. Existing in the mind, especially as a product of the imagination. Used in literary criticism of text. 虚的，内心的：在头脑中存在的，尤指意想的产物。用于文学批评中。 我们采用第一个定义，也就是说被virtual所修饰的事物或现象在本质上是存在的，但是没有直观的形式表现，无法直接描述或定义，需要通过其他的间接方式或手段才能够体现出其实际上的效果。那么在C++中就是采用了这个词意，不可以在语言模型中直接调用或体现的，但是确实是存在可以被间接的方式进行调用或体现的。比如：虚函数必须要通过一种间接的运行时（而不是编译时）机制才能够激活（调用）的函数，而虚继承也是必须在运行时才能够进行定位访问的一种体制。存在，但间接。其中关键就在于存在、间接和共享这三种特征。 对于虚函数而言，这三个特征是很好理解的，间接性表明了他必须在运行时根据实际的对象来完成函数寻址，共享性表象在基类会共享被子类重载后的虚函数，其实指向相同的函数入口。 对于虚继承而言，这三个特征如何理解呢？存在即表示虚继承体系和虚基类确实存在，间接性表明了在访问虚基类的成员时同样也必须通过某种间接机制来完成（下面模型中会讲到），共享性表象在虚基类会在虚继承体系中被共享，而不会出现多份拷贝。那现在可以解释语法小节中留下来的那个问题了，“为什么一旦出现了虚基类，就必须在每一个继承类中都必须包含虚基类的初始化语句”。由上面的分析可以知道，虚基类是被共享的，也就是在继承体系中无论被继承多少次，对象内存模型中均只会出现一个虚基类的子对象（这和多继承是完全不同的），这样一来既然是共享的那么每一个子类都不会独占，但是总还是必须要有一个类来完成基类的初始化过程（因为所有的对象都必须被初始化，哪怕是默认的），同时还不能够重复进行初始化，那到底谁应该负责完成初始化呢？C++标准中选择在每一次继承子类中都必须书写初始化语句（因为每一次继承子类可能都会用来定义对象），而在最下层继承子类中实际执行初始化过程。所以上面在每一个继承类中都要书写初始化语句，但是在创建对象时，而仅仅会在创建对象用的类构造函数中实际的执行初始化语句，其他的初始化语句都会被压制不调用。 3. 模型 为了实现上面所说的三种语义含义，在考虑对象的实现模型（也就是内存模型）时就 很自然了。在C++中对象实际上就是一个连续的地址空间的语义代表，我们来分析虚继承下的内存模型。 3.1. 存在 也就是说在对象内存中必须要包含虚基类的完整子对象，以便能够完成通过地址完成对象的标识。那么至于虚基类的子对象会存放在对象的那个位置（头、中间、尾部）则由各个编译器选择，没有差别。（在VC8中无论虚基类被声明在什么位置，虚基类的子对象都会被放置在对象内存的尾部） 3.2. 间接 间接性表明了在直接虚基承子类中一定包含了某种指针（偏移或表格）来完成通过子类访问虚基类子对象（或成员）的间接手段（因为虚基类子对象是共享的，没有确定关系），至于采用何种手段由编译器选择。（在VC8中在子类中放置了一个虚基类指针vbc，该指针指向虚函数表中的一个slot，该slot中存放则虚基类子对象的偏移量的负值，实际上就是个以补码表示的int类型的值，在计算虚基类子对象首地址时，需要将该偏移量取绝对值相加，这个主要是为了和虚表中只能存放虚函数地址这一要求相区别，因为地址是原码表示的无符号int类型的值） 3.3. 共享 共享表明了在对象的内存空间中仅仅能够包含一份虚基类的子对象，并且通过某种间接的机制来完成共享的引用关系。在介绍完整个内容后会附上测试代码，体现这些内容。 4. 性能 由于有了间接性和共享性两个特征，所以决定了虚继承体系下的对象在访问时必然会在时间和空间上与一般情况有较大不同。 4.1. 时间 在通过继承类对象访问虚基类对象中的成员（包括数据成员和函数成员）时，都必须通过某种间接引用来完成，这样会增加引用寻址时间（就和虚函数一样），其实就是调整this指针以指向虚基类对象，只不过这个调整是运行时间接完成的。（在VC8中通过打开汇编输出，可以查看*.cod文件中的内容，在访问虚基类对象 成员时会形成三条mov间接寻址语句，而在访问一般继承类对象时仅仅只有一条mov常量直接寻址语句） 4.2. 空间 由于共享所以不同在对象内存中保存多份虚基类子对象的拷贝，这样较之多继承节省空间。 5. 应用 谈了那么多语言特性和内容，那么在什么情况下需要使用虚继承，而一般应该如何使用呢？ 这个问题其实很难有答案，一般情况下如果你确信出现多继承没有必要，必须要共享基类子对象的时候可以考虑采用虚继承关系（C++标准ios体系就是这样的）。由于每一个继承类都必须包含初始化语句而又仅仅只在最底层子类中调用，这样可能就会使得某些上层子类得到的虚基类子对象的状态不是自己所期望的（因为自己的初始化语句被压制了），所以一般建议不要在虚基类中包含任何数据成员（不要有状态），只可以作为接口类来提供。 15. 多继承 有意思的例子： class A{ char A[100]; }; class B{ char B[100]; }; class C : public A , public B{ char C[100]; }; int main(int argc, char *argv[]) { C* pc = new C; A* pa = dynamic_cast B* pb = dynamic_cast cout<<"pc located in : "<<(int)pc< cout<<"pa located in : "<<(int)pa< cout<<"pb located in : "<<(int)(pb)< if(pc == pb) cout<<"pc == pb"< if((int)pc == (int)pb) cout<<"(int)pc == (int)pb"< } 注意看上面的几个数字，可以说明一个问题：pb实际上指向的地址是对象C中父类B的部分。 所以pa和pc位置一样，而pb地址大了100. 而pc == pb这是因为发生了子类到父类的隐式类型转换，即为pc == pb 等价于(B*)pc == pb （这里和书上不一样，估计书上错了，因为没有父类到子类的隐式类型转换），所以结果为true，执行了后面的cout 16.函数传参获取数组长度的方法 template void printlen(T (&c)[N]) { cout<<"c[]length: "< cout< } int main(int argc, char *argv[]) { int p[]={1, 2, 3, 4, 5}; printlen(p); } 这是一种非类型模板形参，在需要常量表达式的时候可使用非类型模板形参。如上例，当调用printlen 函数时编译器从数组实参中读取int N的值 17. 私有继承 小心继承时候default的私有继承，例如 class B : A {}; 这里就发生了私有继承，B对象不得使用A的public成员。 18. 类型转换函数 用转换构造函数可以将一个指定类型的数据转换为类的对象?但是不能反过来将一个类的对象转换为一个其他类型的数据(例如将一个Complex类对象转换成double类型数据) C++提供类型转换函数(type conversion function)来解决这个问题?类型转换函数的作用是将一个类的对象转换成另一类型的数据?如果已声明了一个Complex类,可以在Complex类中这样定义类型转换函数: operator double( ) { return real; } 类型转换函数的一般形式为 operator 类型名( ) { 实现转换的语句 } 在函数名前面不能指定函数类型,函数没有参数?其返回值的类型是由函数名中指定的类型名来确定的?类型转换函数只能作为成员函数,因为转换的主体是本类的对象?不能作为友元函数或普通函数? 从函数形式可以看到,它与运算符重载函数相似,都是用关键字operator开头,只是被重载的是类型名?double类型经过重载后,除了原有的含义外,还获得新的含义(将一个Complex类对象转换为double类型数据,并指定了转换方法)?这样,编译系统不仅能识别原有的double型数据,而且还会把Complex类对象作为double型数据处理? 那么程序中的Complex类对具有双重身份,既是Complex类对象,又可作为double类型数据?Complex 类对象只有在需要时才进行转换,要根据表达式的上下文来决定?转换构造函数和类型转换运算符有一个共同的功能: 当需要的时候,编译系统会自动调用这些函数,建立一个无名的临时对象(或临时变量)? 转换函数的基本规则： 转换函数只能是成员函数，无返回值，空参数。 不能定义到void的转换，也不允许转换成数组或者函数类型。 转换常定义为const形式，原因是它并不改变数据成员的值。 19. 排序算法总结 注：所有排序都按照从小到大排。 1. 冒泡排序 1）排序思想 依次两两比较大小，并总把大的放到后面，这样每趟都能产生一个已经放到正确位置的最大值。2）排序实现 template void exchange(T &m,T &n) { T temp; temp = m; m = n; n = temp; } template void bubbleSort (vector { bool exchangeflag = 0; //转换标志，如果无转换则直接return size_t len = vec.size(); while(len > 0) { exchangeflag = 0; for(int i = 0; i < len-1; i++) { if(vec[i] > vec[i+1]) { exchange(vec[i],vec[i+1]); exchangeflag = 1; } } if(0 == exchangeflag)return; len--; } } 3）复杂度和稳定性分析 稳定性： 如果两个元素相等，则不会交换；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。 时间复杂度： 最好：正序，比较次数n-1，移动次数0，复杂度O(n) 最差：逆序，比较次数n(n-1)/2，移动次数3* n(n-1)/2，复杂度O(n2) 平均：O(n2) 空间复杂度：O(1) 2. 插入排序 1）排序思想 2）排序实现 template void insertSort(vector size_t len = vec.size(); for(int sorted = 0; sorted < len-1; ++sorted) { T unsortedData = vec[sorted + 1]; for(int i = sorted; i >= 0;i--) { if(unsortedData >= vec[i]) //这里的>=表示是稳定的 { vec[i + 1] = unsortedData; break; } else { vec[i + 1] = vec[i]; if(i == 0)vec[i] = unsortedData; //如果比较到第一个数仍然小，移动后，需要把该值赋给第一个数 } } } } 3）复杂度和稳定性分析 稳定性：相同则直接不移动，故而是稳定的 时间复杂度： 最好：正序，移动次数0，比较次数n-1，复杂度O(n) 最差：逆序，移动次数n(n-1)/2，比较次数2*n(n-1)/2，复杂度O(n2) 平均：O(n2) 空间复杂度：O(1) 3. 归并排序 4. 快速排序 1）排序思想 分治的思想 2）排序实现 void sort(int array[],int zz,int yy) { int z,y,i,cutNum; if(zz { z=zz; y=yy; cutNum=array[z]; do { while((z y--; if(z array[z++]=array[y];//右边的元素小于k，移到k左 while((z z++; if(z array[y--]=array[z]; } while(z!=y); array[z]=cutNum; sort(array,zz,z-1); sort(array,z+1,yy); } } 3）复杂度和稳定性分析 时间复杂度： 最好：O(nlogn) 最坏：O(n2) 平均：O(nlogn) 空间复杂度：O(logn)，因为递归树的高度为logn。 稳定性：不稳定 5.shell排序 1）排序思想 步长选择为length的一半，每次循环减半 2）排序实现 void shellSort(int *data,int len) { int d= len; while(d > 1) { d = (d+1)/2; for(int i =0; i < len-d; ++i) { if(data[i + d] < data[i]) exchange(data[i + d],data[i]); } } } 3）复杂度和稳定性分析 时间复杂度：O(nlogn) 空间复杂度：O(1) 稳定性：不稳定 6.堆排序 1）排序思想 每次选出一个最大值（选取方法：从n/2开始到根，与各自的孩子节点比较并交换）并放到数组的末尾。最终就成为一个从小到大的有序数组了。 2）排序实现 void FindMaxInHeap(int arr[], const int size) { for (int j = size - 1; j > 0; --j) { int parent = j / 2; int child = j; if (j < size - 1 && arr[j] < arr[j+1]) ++child; if (arr[child] > arr[parent]) exchange(arr[child],arr[parent]);
相关主题
文本预览