1. 結(jié)構(gòu)體和共同體的區(qū)別。

定義：

結(jié)構(gòu)體struct：把不同類型的數(shù)據(jù)組合成一個整體，自定義類型。

共同體union：使幾個不同類型的變量共同占用一段內(nèi)存。

地址：

struct和union都有內(nèi)存對齊，結(jié)構(gòu)體的內(nèi)存布局依賴于CPU、操作系統(tǒng)、編譯器及編譯時的對齊選項。

關(guān)于內(nèi)存對齊，先讓我們看四個重要的基本概念：1.數(shù)據(jù)類型自身的對齊值：對于char型數(shù)據(jù)，其自身對齊值為1，對于short型為2，對于int,float,double類型，其自身對齊值為4，單位字節(jié)。2.結(jié)構(gòu)體或者類的自身對齊值：其成員中自身對齊值最大的那個值。3.指定對齊值：#PRagma pack(n)，n=1,2,4,8,16改變系統(tǒng)的對齊系數(shù)4.數(shù)據(jù)成員、結(jié)構(gòu)體和類的有效對齊值：自身對齊值和指定對齊值中小的那個值。
 常見數(shù)據(jù)類型及其長度：
注意long int和int一樣是4byte，long double和double一樣是8byte。
在標準c++中，int的定義長度要依靠你的機器的字長，也就是說，如果你的機器是32位的，int的長度為32位，如果你的機器是64位的，那么int的標準長度就是64位。
從上面的一段文字中，我們可以看出，首先根據(jù)結(jié)構(gòu)體內(nèi)部成員的自身對齊值得到結(jié)構(gòu)體的自身對齊值（內(nèi)部成員最大的長度），如果沒有修改系統(tǒng)設(shè)定的默認補齊長度4的話，取較小的進行內(nèi)存補齊。
結(jié)構(gòu)體struct：不同之處，stuct里每個成員都有自己獨立的地址。sizeof(struct)是內(nèi)存對齊后所有成員長度的加和。
共同體union：當共同體中存入新的數(shù)據(jù)后，原有的成員就失去了作用，新的數(shù)據(jù)被寫到union的地址中。sizeof(union)是最長的數(shù)據(jù)成員的長度。
總結(jié)： struct和union都是由多個不同的數(shù)據(jù)類型成員組成, 但在任何同一時刻, union中只存放了一個被選中的成員, 而struct的所有成員都存在。在struct中，各成員都占有自己的內(nèi)存空間，它們是同時存在的。一個struct變量的總長度等于所有成員長度之和。在Union中，所有成員不能同時占用它的內(nèi)存空間，它們不能同時存在。Union變量的長度等于最長的成員的長度。對于union的不同成員賦值, 將會對其它成員重寫, 原來成員的值就不存在了, 而對于struct的不同成員賦值是互不影響的。
 
 
 2.static 和const分別怎么用，類里面static和const可以同時修飾成員函數(shù)嗎。
 static的作用：
對變量：
1.局部變量：
在局部變量之前加上關(guān)鍵字static，局部變量就被定義成為一個局部靜態(tài)變量。
  1）內(nèi)存中的位置：靜態(tài)存儲區(qū)
  2）初始化：未經(jīng)初始化的全局靜態(tài)變量會被程序自動初始化為0（自動對象的值是任意的，除非他被顯示初始化）
  3）作用域：作用域仍為局部作用域，當定義它的函數(shù)或者語句塊結(jié)束的時候，作用域隨之結(jié)束。
 注：當static用來修飾局部變量的時候，它就改變了局部變量的存儲位置（從原來的棧中存放改為靜態(tài)存儲區(qū)）及其生命周期（局部靜態(tài)變量在離開作用域之后，并沒有被銷毀，而是仍然駐留在內(nèi)存當中，直到程序結(jié)束，只不過我們不能再對他進行訪問），但未改變其作用域。
2.全局變量
在全局變量之前加上關(guān)鍵字static，全局變量就被定義成為一個全局靜態(tài)變量。
1）內(nèi)存中的位置：靜態(tài)存儲區(qū)（靜態(tài)存儲區(qū)在整個程序運行期間都存在）
2）初始化：未經(jīng)初始化的全局靜態(tài)變量會被程序自動初始化為0（自動對象的值是任意的，除非他被顯示初始化）
3）作用域：全局靜態(tài)變量在聲明他的文件之外是不可見的。準確地講從定義之處開始到文件結(jié)尾。
注：static修飾全局變量，并為改變其存儲位置及生命周期，而是改變了其作用域，使當前文件外的源文件無法訪問該變量，好處如下：（1）不會被其他文件所訪問，修改（2）其他文件中可以使用相同名字的變量，不會發(fā)生沖突。對全局函數(shù)也是有隱藏作用。
對類中的
　　　　1.成員變量
　　　　用static修飾類的數(shù)據(jù)成員實際使其成為類的全局變量，會被類的所有對象共享，包括派生類的對象。因此，static成員必須在類外進行初始化(初始化格式： int base::var=10;)，而不能在構(gòu)造函數(shù)內(nèi)進行初始化，不過也可以用const修飾static數(shù)據(jù)成員在類內(nèi)初始化 。
　　　　特點：
不要試圖在頭文件中定義(初始化)靜態(tài)數(shù)據(jù)成員。在大多數(shù)的情況下，這樣做會引起重復(fù)定義這樣的錯誤。即使加上#ifndef #define #endif或者#pragma once也不行。 靜態(tài)數(shù)據(jù)成員可以成為成員函數(shù)的可選參數(shù)，而普通數(shù)據(jù)成員則不可以。靜態(tài)數(shù)據(jù)成員的類型可以是所屬類的類型，而普通數(shù)據(jù)成員則不可以。普通數(shù)據(jù)成員的只能聲明為 所屬類類型的指針或引用。
2.成員函數(shù)
用static修飾成員函數(shù)，使這個類只存在這一份函數(shù)，所有對象共享該函數(shù)，不含this指針。靜態(tài)成員是可以獨立訪問的，也就是說，無須創(chuàng)建任何對象實例就可以訪問。base::func(5,3);當static成員函數(shù)在類外定義時不需要加static修飾符。在靜態(tài)成員函數(shù)的實現(xiàn)中不能直接引用類中說明的非靜態(tài)成員，可以引用類中說明的靜態(tài)成員。因為靜態(tài)成員函數(shù)不含this指針。 
不可以同時用const和static修飾成員函數(shù)。
C++編譯器在實現(xiàn)const的成員函數(shù)的時候為了確保該函數(shù)不能修改類的實例的狀態(tài)，會在函數(shù)中添加一個隱式的參數(shù)const this*。但當一個成員為static的時候，該函數(shù)是沒有this指針的。也就是說此時const的用法和static是沖突的。
我們也可以這樣理解：兩者的語意是矛盾的。static的作用是表示該函數(shù)只作用在類型的靜態(tài)變量上，與類的實例沒有關(guān)系；而const的作用是確保函數(shù)不能修改類的實例的狀態(tài)，與類型的靜態(tài)變量沒有關(guān)系。因此不能同時用它們。
const的作用：
 1.限定變量為不可修改。
2.限定成員函數(shù)不可以修改任何數(shù)據(jù)成員。
3.const與指針：
const char *p 表示 指向的內(nèi)容不能改變。
char * const p，就是將P聲明為常指針，它的地址不能改變，是固定的，但是它的內(nèi)容可以改變。
 
 3.指針和引用的區(qū)別，引用可以用常指針實現(xiàn)嗎。
本質(zhì)上的區(qū)別是，指針是一個新的變量，只是這個變量存儲的是另一個變量的地址，我們通過訪問這個地址來修改變量。
而引用只是一個別名，還是變量本身。對引用進行的任何操作就是對變量本身進行操作，因此以達到修改變量的目的。
(1)指針：指針是一個變量，只不過這個變量存儲的是一個地址，指向內(nèi)存的一個存儲單元；而引用跟原來的變量實質(zhì)上是同一個東西，只不過是原變量的一個別名而已。如：int a=1;int *p=&a;int a=1;int &b=a;上面定義了一個整形變量和一個指針變量p，該指針變量指向a的存儲單元，即p的值是a存儲單元的地址。而下面2句定義了一個整形變量a和這個整形a的引用b，事實上a和b是同一個東西，在內(nèi)存占有同一個存儲單元。(2)可以有const指針，但是沒有const引用；(3)指針可以有多級，但是引用只能是一級（int **p；合法 而 int &&a是不合法的）(4)指針的值可以為空，但是引用的值不能為NULL，并且引用在定義的時候必須初始化；(5)指針的值在初始化后可以改變，即指向其它的存儲單元，而引用在進行初始化后就不會再改變了。(6)"sizeof引用"得到的是所指向的變量(對象)的大小，而"sizeof指針"得到的是指針本身的大小；(7)指針和引用的自增(++)運算意義不一樣；
指針傳參的時候，還是值傳遞，試圖修改傳進來的指針的值是不可以的。只能修改地址所保存變量的值。引用傳參的時候，傳進來的就是變量本身，因此可以被修改。
4.什么是多態(tài)，多態(tài)有什么用途。
定義：“一個接口，多種方法”，程序在運行時才決定調(diào)用的函數(shù)。實現(xiàn)：C++多態(tài)性主要是通過虛函數(shù)實現(xiàn)的，虛函數(shù)允許子類重寫override(注意和overload的區(qū)別，overload是重載，是允許同名函數(shù)的表現(xiàn)，這些函數(shù)參數(shù)列表/類型不同）。
多態(tài)與非多態(tài)的實質(zhì)區(qū)別就是函數(shù)地址是早綁定還是晚綁定。如果函數(shù)的調(diào)用，在編譯器編譯期間就可以確定函數(shù)的調(diào)用地址，并生產(chǎn)代碼，是靜態(tài)的，就是說地址是早綁定的。而如果函數(shù)調(diào)用的地址不能在編譯器期間確定，需要在運行時才確定，這就屬于晚綁定。
3.目的：接口重用。封裝可以使得代碼模塊化，繼承可以擴展已存在的代碼，他們的目的都是為了代碼重用。而多態(tài)的目的則是為了接口重用。
4.用法：聲明基類的指針，利用該指針指向任意一個子類對象，調(diào)用相應(yīng)的虛函數(shù)，可以根據(jù)指向的子類的不同而實現(xiàn)不同的方法。
補充一下關(guān)于重載、重寫、隱藏（總是不記得）的區(qū)別：
Overload(重載)：在C++程序中，可以將語義、功能相似的幾個函數(shù)用同一個名字表示，但參數(shù)或返回值不同（包括類型、順序不同），即函數(shù)重載。（1）相同的范圍（在同一個類中）；（2）函數(shù)名字相同；（3）參數(shù)不同；（4）virtual 關(guān)鍵字可有可無。Override(覆蓋)：是指派生類函數(shù)覆蓋基類函數(shù)，特征是：（1）不同的范圍（分別位于派生類與基類）；（2）函數(shù)名字相同；（3）參數(shù)相同；（4）基類函數(shù)必須有virtual 關(guān)鍵字。注：重寫基類虛函數(shù)的時候，會自動轉(zhuǎn)換這個函數(shù)為virtual函數(shù)，不管有沒有加virtual，因此重寫的時候不加virtual也是可以的，不過為了易讀性，還是加上比較好。Overwrite(重寫)：隱藏，是指派生類的函數(shù)屏蔽了與其同名的基類函數(shù)，規(guī)則如下：（1）如果派生類的函數(shù)與基類的函數(shù)同名，但是參數(shù)不同。此時，不論有無virtual關(guān)鍵字，基類的函數(shù)將被隱藏（注意別與重載混淆）。（2）如果派生類的函數(shù)與基類的函數(shù)同名，并且參數(shù)也相同，但是基類函數(shù)沒有virtual關(guān)鍵字。此時，基類的函數(shù)被隱藏（注意別與覆蓋混淆）。
補充一下虛函數(shù)表：
多態(tài)是由虛函數(shù)實現(xiàn)的，而虛函數(shù)主要是通過虛函數(shù)表（V-Table）來實現(xiàn)的。
如果一個類中包含虛函數(shù)（virtual修飾的函數(shù)），那么這個類就會包含一張?zhí)摵瘮?shù)表，虛函數(shù)表存儲的每一項是一個虛函數(shù)的地址。如下圖：
這個類的每一個對象都會包含一個虛指針（虛指針存在于對象實例地址的最前面，保證虛函數(shù)表有最高的性能），這個虛指針指向虛函數(shù)表。
注：對象不包含虛函數(shù)表，只有虛指針，類才包含虛函數(shù)表，派生類會生成一個兼容基類的虛函數(shù)表。
原始基類的虛函數(shù)表
　　下圖是原始基類的對象，可以看到虛指針在地址的最前面，指向基類的虛函數(shù)表（假設(shè)基類定義了3個虛函數(shù)）
單繼承時的虛函數(shù)（無重寫基類虛函數(shù)）
假設(shè)現(xiàn)在派生類繼承基類，并且重新定義了3個虛函數(shù)，派生類會自己產(chǎn)生一個兼容基類虛函數(shù)表的屬于自己的虛函數(shù)表。
　　Derive class 繼承了 Base class 中的三個虛函數(shù)，準確的說，是該函數(shù)實體的地址被拷貝到 Derive類的虛函數(shù)表，派生類新增的虛函數(shù)置于虛函數(shù)表的后面，并按聲明順序存放。
單繼承時的虛函數(shù)（重寫基類虛函數(shù)）
現(xiàn)在派生類重寫基類的x函數(shù)，可以看到這個派生類構(gòu)建自己的虛函數(shù)表的時候，修改了base::x()這一項，指向了自己的虛函數(shù)。
多重繼承時的虛函數(shù)（Derived ::public Base1,public Base2）
這個派生類多重繼承了兩個基類base1，base2，因此它有兩個虛函數(shù)表。
　　
　　它的對象會有多個虛指針（據(jù)說和編譯器相關(guān)），指向不同的虛函數(shù)表。
　　多重繼承時指針的調(diào)整：
Derive b;Base1* ptr1 = &b;   // 指向 b 的初始地址Base2* ptr2 = &b;   // 指向 b 的第二個子對象
因為 Base1 是第一個基類，所以 ptr1 指向的是 Derive 對象的起始地址，不需要調(diào)整指針（偏移）。
因為 Base2 是第二個基類，所以必須對指針進行調(diào)整，即加上一個 offset，讓 ptr2 指向 Base2 子對象。
當然，上述過程是由編譯器完成的。
Base1* b1 = (Base1*)ptr2;b1->y();                   // 輸出 Base2::y()Base2* b2 = (Base2*)ptr1;b2->y();                   // 輸出 Base1::y()
其實，通過某個類型的指針訪問某個成員時，編譯器只是根據(jù)類型的定義查找這個成員所在偏移量，用這個偏移量獲取成員。由于 ptr2 本來就指向 Base2 子對象的起始地址，所以b1->y()調(diào)用到的是Base2::y()，而 ptr1 本來就指向 Base1 子對象的起始地址（即 Derive對象的起始地址），所以b2->y()調(diào)用到的是Base1::y()。
虛繼承時的虛函數(shù)表
　　虛繼承的引入把對象的模型變得十分復(fù)雜，除了每個基類（MyClassA和MyClassB）和公共基類（MyClass）的虛函數(shù)表指針需要記錄外，每個虛擬繼承了MyClass的父類還需要記錄一個虛基類表vbtable的指針vbptr。MyClassC的對象模型如圖4所示。
　　
　　　虛基類表每項記錄了被繼承的虛基類子對象相對于虛基類表指針的偏移量。比如MyClassA的虛基類表第二項記錄值為24，正是MyClass::vfptr相對于MyClassA::vbptr的偏移量，同理MyClassB的虛基類表第二項記錄值12也正是MyClass::vfptr相對于MyClassA::vbptr的偏移量。（虛函數(shù)與虛繼承深入探討）
對象模型探討：
 
1.沒有繼承情況,vptr存放在對象的開始位置,以下是Base1的內(nèi)存布局
m_iData :100
 2.單繼承的情況下,對象只有一個vptr,它存放在對象的開始位置,派生類子對象在父類子對象的最后面,以下是D1的內(nèi)存布局
B1:: m_iData : 100
B1::vptr : 4294800
B2::vptr : 4294776
D::m_iData :300
4. 虛擬繼承情況下,虛父類子對象會放在派生類子對象之后,派生類子對象的第一個位置存放著一個vptr,虛擬子類子對象也會保存一個vptr,以下是VD1的內(nèi)存布局
 
 Unknown : 4294888
B1::vptr :4294864
VD1::vptr :        4294944
VD1::m_iData :  200
VD2::Unknown : 4294952
VD::m_iData : 500
B1::m_iData :  100
5. 棱形繼承的情況下,非虛基類子對象在派生類子對象前面,并按照聲明順序排列,虛基類子對象在派生類子對象后面
VD1::Unknown : 4294968
VD2::vptr :    4   294932
VD2::m_iData : 300
B1::vptr :       4294920
B1::m_iData :  100
 
補充一下純虛函數(shù)：
定義： 在很多情況下，基類本身生成對象是不合情理的。為了解決這個問題，方便使用類的多態(tài)性，引入了純虛函數(shù)的概念，將函數(shù)定義為純虛函數(shù)（方法：virtual ReturnType Function()= 0;）純虛函數(shù)不能再在基類中實現(xiàn)，編譯器要求在派生類中必須予以重寫以實現(xiàn)多態(tài)性。同時含有純虛擬函數(shù)的類稱為抽象類，它不能生成對象。特點：
1，當想在基類中抽象出一個方法，且該基類只做能被繼承，而不能被實例化；（避免類被實例化且在編譯時候被發(fā)現(xiàn)，可以采用此方法）
2，這個方法必須在派生類(derived class)中被實現(xiàn)；
目的：使派生類僅僅只是繼承函數(shù)的接口。補充一下純虛函數(shù)：定義：稱帶有純虛函數(shù)的類為抽象類。作用：為一個繼承體系提供一個公共的根，為派生類提供操作接口的通用語義。特點：1.抽象類只能作為基類來使用，而繼承了抽象類的派生類如果沒有實現(xiàn)純虛函數(shù)，而只是繼承純虛函數(shù)，那么該類仍舊是一個抽象類，如果實現(xiàn)了純虛函數(shù)，就不再是抽象類。　　　　　　2.抽象類不可以定義對象。補充一下多重繼承和虛繼承：多重繼承：定義：派生類繼承多個基類，派生類為每個基類（顯式或隱式地）指定了訪問級別——public、protected 或 private。
    class Panda : public Bear, public Endangered {    }
構(gòu)造：
派生類的對象包含每個基類的基類子對象。派生類構(gòu)造函數(shù)初始化所有基類（多重繼承中若沒有顯式調(diào)用某個基類的構(gòu)造函數(shù)，則編譯器會調(diào)用該基類默認構(gòu)造函數(shù)），派生類只能初始化自己的基類，并不需要考慮基類的基類怎么初始化。多重繼承時，基類構(gòu)造函數(shù)按照基類構(gòu)造函數(shù)在類派生列表中的出現(xiàn)次序調(diào)用。析構(gòu)：總是按構(gòu)造函數(shù)運行的逆序調(diào)用析構(gòu)函數(shù)。（基類的析構(gòu)函數(shù)最好寫成virtual，否則再子類對象銷毀的時候，無法銷毀子類對象部分資源。）假定所有根基類都將它們的析構(gòu)函數(shù)適當定義為虛函數(shù)，那么，無論通過哪種指針類型刪除對象，虛析構(gòu)函數(shù)的處理都是一致的。 拷貝構(gòu)造/賦值：如果要為派生類編寫拷貝構(gòu)造函數(shù)，則需要為調(diào)用基類相應(yīng)拷貝構(gòu)造函數(shù)并為其傳遞參數(shù)，否則只會拷貝派生類部分。
深拷貝與淺拷貝：淺拷貝：默認的復(fù)制構(gòu)造函數(shù)只是完成了對象之間的位拷貝，也就是把對象里的值完全復(fù)制給另一個對象，如A=B。這時，如果B中有一個成員變量指針已經(jīng)申請了內(nèi)存，那A中的那個成員變量也指向同一塊內(nèi)存。　　　　這就出現(xiàn)了問題：當B把內(nèi)存釋放了（如：析構(gòu)），這時A內(nèi)的指針就是野指針了，出現(xiàn)運行錯誤。深拷貝：自定義復(fù)制構(gòu)造函數(shù)需要注意，對象之間發(fā)生復(fù)制，資源重新分配，即A有5個空間，B也應(yīng)該有5個空間，而不是指向A的5個空間。
虛繼承與虛基類：
定義：在多重繼承下，一個基類可以在派生層次中出現(xiàn)多次。（派生類對象中可能出現(xiàn)多個基類對象）在 C++ 中，通過使用虛繼承解決這類問題。虛繼承是一種機制，類通過虛繼承指出它希望共享其虛基類的狀態(tài)。在虛繼承下，對給定虛基類，無論該類在派生層次中作為虛基類出現(xiàn)多少次，只繼承一個共享的基類子對象。共享的基類子對象稱為虛基類。
用法：istream 和 ostream 類對它們的基類進行虛繼承。通過使基類成為虛基類，istream 和 ostream 指定，如果其他類（如 iostream 同時繼承它們兩個，則派生類中只出現(xiàn)它們的公共基類ios的一個副本。通過在派生列表中包含關(guān)鍵字 virtual 設(shè)置虛基類：
    class istream : public virtual ios { ... };    class ostream : virtual public ios { ... };    // iostream inherits only one copy of its ios base class    class iostream: public istream, public ostream { ... };
5.各個排序算法的時間復(fù)雜度和穩(wěn)定性，快排的原理。
排序深入探討
插入排序
　　每次將一個待排序的數(shù)據(jù)，跟前面已經(jīng)有序的序列的數(shù)字一一比較找到自己合適的位置，插入到序列中，直到全部數(shù)據(jù)插入完成。
希爾排序
　　先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。由于希爾排序是對相隔若干距離的數(shù)據(jù)進行直接插入排序，因此可以形象的稱希爾排序為“跳著插”
冒泡排序
通過交換使相鄰的兩個數(shù)變成小數(shù)在前大數(shù)在后，這樣每次遍歷后，最大的數(shù)就“沉”到最后面了。重復(fù)N次即可以使數(shù)組有序。
冒泡排序改進1：在某次遍歷中如果沒有數(shù)據(jù)交換，說明整個數(shù)組已經(jīng)有序。因此通過設(shè)置標志位來記錄此次遍歷有無數(shù)據(jù)交換就可以判斷是否要繼續(xù)循環(huán)。
冒泡排序改進2：記錄某次遍歷時最后發(fā)生數(shù)據(jù)交換的位置，這個位置之后的數(shù)據(jù)顯然已經(jīng)有序了。因此通過記錄最后發(fā)生數(shù)據(jù)交換的位置就可以確定下次循環(huán)的范圍了。
快速排序
“挖坑填數(shù)+分治法”，首先令i =L; j = R; 將a[i]挖出形成第一個坑，稱a[i]為基準數(shù)。然后j--由后向前找比基準數(shù)小的數(shù)，找到后挖出此數(shù)填入前一個坑a[i]中，再i++由前向后找比基準數(shù)大的數(shù)，找到后也挖出此數(shù)填到前一個坑a[j]中。重復(fù)進行這種“挖坑填數(shù)”直到i==j。再將基準數(shù)填入a[i]中，這樣i之前的數(shù)都比基準數(shù)小，i之后的數(shù)都比基準數(shù)大。因此將數(shù)組分成二部分再分別重復(fù)上述步驟就完成了排序。
選擇排序
數(shù)組分成有序區(qū)和無序區(qū)，初始時整個數(shù)組都是無序區(qū)，然后每次從無序區(qū)選一個最小的元素直接放到有序區(qū)的最后，直到整個數(shù)組變有序區(qū)。
堆排序
堆的插入就是——每次插入都是將新數(shù)據(jù)放在數(shù)組最后，而從這個新數(shù)據(jù)的父結(jié)點到根結(jié)點必定是一個有序的數(shù)列，因此只要將這個新數(shù)據(jù)插入到這個有序數(shù)列中即可。
堆的刪除就是——堆的刪除就是將最后一個數(shù)據(jù)的值賦給根結(jié)點，然后再從根結(jié)點開始進行一次從上向下的調(diào)整。調(diào)整時先在左右兒子結(jié)點中找最小的，如果父結(jié)點比這個最小的子結(jié)點還小說明不需要調(diào)整了，反之將父結(jié)點和它交換后再考慮后面的結(jié)點。相當于從根結(jié)點開始將一個數(shù)據(jù)在有序數(shù)列中進行“下沉”。
因此，堆的插入和刪除非常類似直接插入排序，只不是在二叉樹上進行插入過程。所以可以將堆排序形容為“樹上插”
歸并排序
歸并排序主要分為兩步：分數(shù)列（divide），每次把數(shù)列一分為二，然后分到只有兩個元素的小數(shù)列；合數(shù)列（Merge），合并兩個已經(jīng)內(nèi)部有序的子序列，直至所有數(shù)字有序。用遞歸可以實現(xiàn)。
基數(shù)排序（桶排序）
基數(shù)排序，第一步根據(jù)數(shù)字的個位分配到每個桶里，在桶內(nèi)部排序，然后將數(shù)字再輸出（串起來）；然后根據(jù)十位分桶，繼續(xù)排序，再串起來。直至所有位被比較完，所有數(shù)字已經(jīng)有序。
 　　
 
6.vector中size()和capacity()的區(qū)別。
 
size()指容器當前擁有的元素個數(shù)（對應(yīng)的resize(size_type)會在容器尾添加或刪除一些元素，來調(diào)整容器中實際的內(nèi)容，使容器達到指定的大小。）；capacity（）指容器在必須分配存儲空間之前可以存儲的元素總數(shù)。
 
size表示的這個vector里容納了多少個元素，capacity表示vector能夠容納多少元素，它們的不同是在于vector的size是2倍增長的。如果vector的大小不夠了，比如現(xiàn)在的capacity是4，插入到第五個元素的時候，發(fā)現(xiàn)不夠了，此時會給他重新分配8個空間，把原來的數(shù)據(jù)及新的數(shù)據(jù)復(fù)制到這個新分配的空間里。（會有迭代器失效的問題）
各容器的特點：
 
7.map和set的原理。
(map和set的四個問題)
map和set的底層實現(xiàn)主要是由紅黑樹實現(xiàn)的。
紅黑樹：
性質(zhì)1 節(jié)點是紅色或黑色。性質(zhì)2 根節(jié)點是黑色。性質(zhì)3 每個葉節(jié)點（NIL節(jié)點，空節(jié)點）是黑色的。性質(zhì)4 每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)性質(zhì)5 從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。這些約束的好處是：保持了樹的相對平衡，同時又比AVL的插入刪除操作的復(fù)雜性要低許多。
（深入探討紅黑樹）