• 數(shù)據(jù)結(jié)構(gòu) ：哈希表、堆、棧、隊(duì)列、鏈表、二叉樹
• 操作系統(tǒng)（iOS）的堆、棧
• 算法 ：排序、冒泡、快排、二分查找

1.png

數(shù)據(jù)結(jié)構(gòu)

哈希表(Hash table)

哈希表（Hash table，也叫散列表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
哈希表hashtable(key，value) 就是把Key通過一個固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個整型數(shù)字即哈希值，然后就將該數(shù)字對數(shù)組長度進(jìn)行取余，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)，將value存儲在以該數(shù)字為下標(biāo)的數(shù)組空間里。
而當(dāng)使用哈希表進(jìn)行查詢的時(shí)候，就是再次使用哈希函數(shù)將key轉(zhuǎn)換為對應(yīng)的數(shù)組下標(biāo)，并定位到該空間獲取value，如此一來，就可以充分利用到數(shù)組的定位性能進(jìn)行數(shù)據(jù)定位。

NSDictionary就是哈希表

堆（heap）、棧（stack）和隊(duì)列（queue）

堆是一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱堆通常是一個可以被看做一棵樹的數(shù)組對象。堆總是滿足下列性質(zhì)：
1、堆中某個節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
2、堆總是一棵完全二叉樹。

棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表， LIFO。

隊(duì)列是只允許在一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作的線性表，F(xiàn)IFO。

鏈表是一種線性表，但是并不會按線性的鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。

樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個有限結(jié)點(diǎn)組成一個具有層次關(guān)系的集合。
樹具有的特點(diǎn)有：
（1）每個結(jié)點(diǎn)有零個或多個子結(jié)點(diǎn)
（2）沒有父節(jié)點(diǎn)的結(jié)點(diǎn)稱為根節(jié)點(diǎn)
（3）每一個非根結(jié)點(diǎn)有且只有一個父節(jié)點(diǎn)
（4）除了根結(jié)點(diǎn)外，每個子結(jié)點(diǎn)可以分為多個不相交的子樹。

https://www.cnblogs.com/manji/p/4903990.html
二叉樹-你必須要懂?。ǘ鏄湎嚓P(guān)算法實(shí)現(xiàn)-iOS）

下面是線性表定義

2.png

iOS操作系統(tǒng)中的堆棧

進(jìn)程的內(nèi)存分區(qū)

所有進(jìn)程（執(zhí)行的程序）都必須占用一定數(shù)量的內(nèi)存，它或是用來存放從磁盤載入的程序代碼，或是存放取自用戶輸入的數(shù)據(jù)等等。不過進(jìn)程對這些內(nèi)存的管理方式因內(nèi)存用途不一而不盡相同，有些內(nèi)存是事先靜態(tài)分配和統(tǒng)一回收的，而有些卻是按需要動態(tài)分配和回收的。

3.png

1. 代碼區(qū)：代碼段是用來存放可執(zhí)行文件的操作指令

2. 全局（靜態(tài)）區(qū)包含下面兩個分區(qū)：

3. 數(shù)據(jù)區(qū)：數(shù)據(jù)段用來存放可執(zhí)行文件中已初始化全局變量，換句話說就是存放程序靜態(tài)分配的變量和全局變量。

4. BSS區(qū)：BSS段包含了程序中未初始化全局變量。

5. 常量區(qū)：常量存儲區(qū)，這是一塊比較特殊的存儲區(qū)，他們里面存放的是常量

6. 堆（heap）區(qū)：堆是由程序員分配和釋放，用于存放進(jìn)程運(yùn)行中被動態(tài)分配的內(nèi)存段，它大小并不固定，可動態(tài)擴(kuò)張或縮減。
   當(dāng)進(jìn)程調(diào)用alloc等函數(shù)分配內(nèi)存時(shí)，新分配的內(nèi)存就被動態(tài)添加到堆上（堆被擴(kuò)張）；當(dāng)利用realse釋放內(nèi)存時(shí)，被釋放的內(nèi)存從堆中被剔除（堆被縮減），因?yàn)槲覀儸F(xiàn)在iOS基本都使用ARC來管理對象，所以不用我們程序員來管理，但是我們要知道這個對象存儲的位置。

7. 棧（stack）區(qū)：棧是由編譯器自動分配并釋放，用戶存放程序臨時(shí)創(chuàng)建的局部變量，存放函數(shù)的參數(shù)值，局部變量等。
   也就是說我們函數(shù)括弧“{}”中定義的變量（但不包括static聲明的變量，static意味這在數(shù)據(jù)段中存放變量）。除此以外在函數(shù)被調(diào)用時(shí)，其參數(shù)也會被壓入發(fā)起調(diào)用的進(jìn)程棧中，并且待到調(diào)用結(jié)束后，函數(shù)的返回值也回被存放回棧中。由于棧的先進(jìn)后出特點(diǎn)，所以棧特別方便用來保存/恢復(fù)調(diào)用現(xiàn)場。從這個意義上將我們可以把?？闯梢粋€臨時(shí)數(shù)據(jù)寄存、交換的內(nèi)存區(qū)。

舉一個??

#import "ViewController.h"

int age = 24;//全局初始化區(qū)（數(shù)據(jù)區(qū)）
NSString *name;//全局未初始化區(qū)（BSS區(qū)）
static NSString *sName = @"Dely";//全局（靜態(tài)初始化）區(qū)

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    
    int tmpAge;//棧
    NSString *tmpName = @"Dely";//棧
    NSString *number = @"123456"; //123456\\\\0在常量區(qū)，number在棧上。
    NSMutableArray *array = [NSMutableArray arrayWithCapacity:1];//分配而來的8字節(jié)的區(qū)域就在堆中，array在棧中，指向堆區(qū)的地址
    NSInteger total = [self getTotalNumber:1 number2:1];
    //通常以這種方式創(chuàng)建對象：
    NSObject *obj = [[NSObject alloc] init];
    //系統(tǒng)會在棧上存儲obj這個指針變量，它所指的對象在堆中。
    //通過[NSObject alloc]系統(tǒng)會為其在堆中開辟一塊內(nèi)存空間，并為其生成NSObject所需內(nèi)存結(jié)構(gòu)布局。
    
    /**這里有一個例外
     block在創(chuàng)建的時(shí)候它的內(nèi)存是默認(rèn)是分配在棧(stack)上, 而不是堆(heap)上的.
     所以它的作用域僅限創(chuàng)建時(shí)候的當(dāng)前上下文(函數(shù), 方法...).
     當(dāng)你使用block時(shí)候，如果你想對其保持引用，你需要對其進(jìn)行copy操作，（從棧上copy到堆中，并返回一個指向他的指針）。
     
     一個 block 剛聲明的時(shí)候是在棧上
     賦值給一個普通變量之后就會被 copy 到堆上
     賦值給一個 weak 變量不會被 copy
     作為屬性：
     用 strong 和 copy 修飾的屬性會被 copy
     用 weak 和 assign 修飾的屬性不會被 copy
     函數(shù)傳參：
     作為參數(shù)傳入函數(shù)不會被 copy
     作為函數(shù)的返回值會被 copy
     */
}

- (NSInteger)getTotalNumber:(NSInteger)number1 number2:(NSInteger)number2
{
    return number1 + number2;//number1和number2 棧區(qū)
}


@end

堆（heap）和棧（stack）區(qū)別

1. 申請方式和回收方式
   棧區(qū)（stack） ：由編譯器自動分配并釋放
   堆區(qū)（heap）：由程序員分配和釋放

2. 申請后系統(tǒng)的響應(yīng)
   棧區(qū)（stack）：存儲每一個函數(shù)在執(zhí)行的時(shí)候都會向操作系統(tǒng)索要資源，棧區(qū)就是函數(shù)運(yùn)行時(shí)的內(nèi)存，棧區(qū)中的變量由編譯器負(fù)責(zé)分配和釋放，內(nèi)存隨著函數(shù)的運(yùn)行分配，隨著函數(shù)的結(jié)束而釋放，由系統(tǒng)自動完成。只要棧的剩余空間大于所申請空間，系統(tǒng)將為程序提供內(nèi)存，否則將報(bào)異常提示棧溢出。
   堆區(qū)（heap）：操作系統(tǒng)有一個記錄空閑內(nèi)存地址的鏈表，當(dāng)系統(tǒng)收到程序的申請時(shí)，會遍歷該鏈表，尋找第一個空間大于所申請空間的堆結(jié)點(diǎn)，然后將該結(jié)點(diǎn)從空閑結(jié)點(diǎn)鏈表中刪除，并將該結(jié)點(diǎn)的空間分配給程序，另外，對于大多數(shù)系統(tǒng)，會在這塊內(nèi)存空間中的首地址處記錄本次分配的大小，這樣，代碼中的delete語句才能正確的釋放本內(nèi)存空間。另外，由于找到的堆結(jié)點(diǎn)的大小不一定正好等于申請的大小，系統(tǒng)會自動的將多余的那部分重新放入空閑鏈表中。

3. 申請大小的限制
   棧區(qū)（stack）：棧是向低地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，是一塊連續(xù)的內(nèi)存的區(qū)域。這句話的意思是棧頂?shù)牡刂泛蜅５淖畲笕萘渴窍到y(tǒng)預(yù)先規(guī)定好的，棧的空間比較小，如果申請的空間超過棧的剩余空間時(shí)，將提示棧溢出。
   堆區(qū)（heap）：堆是向高地址擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，是不連續(xù)的內(nèi)存區(qū)域。這是由于系統(tǒng)是用鏈表來存儲的空閑內(nèi)存地址的，自然是不連續(xù)的，而鏈表的遍歷方向是由低地址向高地址。堆的大小受限于計(jì)算機(jī)系統(tǒng)中有效的虛擬內(nèi)存。由此可見，堆獲得的空間比較靈活，也比較大。

4. 申請效率的比較
   棧區(qū)（stack）：由系統(tǒng)自動分配，速度較快。但程序員是無法控制的。
   堆區(qū)（heap）：是由alloc分配的內(nèi)存，一般速度比較慢，而且容易產(chǎn)生內(nèi)存碎片,不過用起來最方便.

5. 分配方式的比較
   棧區(qū)（stack）：有2種分配方式：靜態(tài)分配和動態(tài)分配。靜態(tài)分配是編譯器完成的，比如局部變量的分配。動態(tài)分配由alloc函數(shù)進(jìn)行分配，但是棧的動態(tài)分配和堆是不同的，他的動態(tài)分配是由編譯器進(jìn)行釋放，無需我們手工實(shí)現(xiàn)。
   堆區(qū)（heap）：堆都是動態(tài)分配的，沒有靜態(tài)分配的堆。

6. 分配效率的比較
   棧區(qū)（stack）：棧是操作系統(tǒng)提供的數(shù)據(jù)結(jié)構(gòu)，計(jì)算機(jī)會在底層對棧提供支持：分配專門的寄存器存放棧的地址，壓棧出棧都有專門的指令執(zhí)行，這就決定了棧的效率比較高。
   堆區(qū)（heap）：堆則是C/C++函數(shù)庫提供的，它的機(jī)制是很復(fù)雜的，例如為了分配一塊內(nèi)存，庫函數(shù)會按照一定的算法（具體的算法可以參考數(shù)據(jù)結(jié)構(gòu)/操作系統(tǒng)）在堆內(nèi)存中搜索可用的足夠大小的空間，如果沒有足夠大小的空間（可能是由于內(nèi)存碎片太多），就有可能調(diào)用系統(tǒng)功能去增加程序數(shù)據(jù)段的內(nèi)存空間，這樣就有機(jī)會分到足夠大小的內(nèi)存，然后進(jìn)行返回。顯然，堆的效率比棧要低得多

總結(jié)一下優(yōu)點(diǎn)缺點(diǎn)

棧對象：
優(yōu)點(diǎn)：
1.高速，在棧上分配內(nèi)存是非?？斓摹?br> 2.簡單，棧對象有自己的生命周期，你永遠(yuǎn)不可能發(fā)生內(nèi)存泄露。因?yàn)樗偸窃诔鏊淖饔糜驎r(shí)被自動銷毀了
缺點(diǎn)：棧對象嚴(yán)格的定義了生命周期也是其主要的缺點(diǎn),棧對象的生命周期不適于Objective-C的引用計(jì)數(shù)內(nèi)存管理方法。
堆對象：
優(yōu)點(diǎn)：可以自己控制對象的生命周期。
缺點(diǎn)：需要程序員手動釋放，容易造成內(nèi)存泄漏。（我們有ARC）

算法

見代碼，幾種排序的OC版本。