鏈表和數(shù)組的區(qū)別
從邏輯結構來看
- 數(shù)組必須事先定義固定的長度碾褂，不能適應數(shù)據(jù)動態(tài)地增減的情況。當數(shù)據(jù)增加時暂殖，可能超出原先定義的元素個數(shù)价匠；當數(shù)據(jù)減少時，造成內存浪費呛每；數(shù)組可以根據(jù)下標直接存取踩窖。
- 鏈表動態(tài)地進行存儲分配，可以適應數(shù)據(jù)動態(tài)地增減的情況晨横，且可以方便地插入洋腮、刪除數(shù)據(jù)項箫柳。（數(shù)組中插入、刪除數(shù)據(jù)項時啥供，需要移動其它數(shù)據(jù)項悯恍，非常繁瑣）鏈表必須根據(jù)next指針找到下一個元素
從內存存儲來看
- (靜態(tài))數(shù)組從棧中分配空間, 對于程序員方便快速,但是自由度小
- 鏈表從堆中分配空間, 自由度大但是申請管理比較麻煩
從上面的比較可以看出，如果需要快速訪問數(shù)據(jù)伙狐，很少或不插入和刪除元素涮毫，就應該用數(shù)組；相反贷屎， 如果需要經常插入和刪除元素就需要用鏈表數(shù)據(jù)結構了罢防。
排序基本
作為排序依據(jù)的數(shù)據(jù)項稱為排序碼，也即數(shù)據(jù)元素的關鍵碼唉侄。若關鍵碼是主關鍵碼咒吐，則對于任意待排序序列，經排序后得到的結果是唯一的美旧；若關鍵碼是次關鍵碼渤滞，排序結果可能不唯一。
若對任意的數(shù)據(jù)元素序列榴嗅，使用某個排序方法妄呕，對它按關鍵碼進行排序：若相同關鍵碼元素間的位置關系，排序前與排序后保持一致嗽测，稱此排序方法是穩(wěn)定的绪励；而不能保持一致的排序方法則稱為不穩(wěn)定的。
排序分為兩大類：內排序和外排序唠粥。
- 內排序：指待排序列完全存放在內存中所進行的排序過程疏魏，適合不太大的元素序列。
- 外排序：指排序過程中還需訪問外存儲器晤愧，足夠大的元素序列大莫，因不能完全放入內存，只能使用外排序官份。
插入排序
插入排序是一種簡單直觀的排序算法只厘。它的工作原理是通過構建有序序列，對于未排序數(shù)據(jù)舅巷，在已排序序列中從后向前掃描羔味，找到相應位置并插入。插入排序在實現(xiàn)上钠右，通常采用in-place排序（即只需用到O(1)的額外空間的排序）赋元，因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間搁凸。
插入排序都采用in-place在數(shù)組上實現(xiàn)媚值，其運作如下：
1.從第一個元素開始，該元素可以認為已經被排序
2.取出下一個元素护糖，在已經排序的元素序列中從中向前掃描
3.如果該元素（已排序）大于新元素杂腰，將該元素移到下一位置
4.重復步驟3，直到找到已排序的元素小于或等于新元素的位置
5.將新元素插入到該位置后
6.重復步驟2~5
冒泡排序
- 冒泡排序是一種簡單的排序算法椅文。它重復地走訪過要排序的數(shù)列，一次比較兩個元素惜颇，如果他們的順序錯誤就把他們交換過來皆刺。
運作如下：
比較相鄰的元素。如果第一個比第二個大凌摄，就交換他們兩個羡蛾。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對锨亏。這步做完后痴怨，最后的元素會是最大的數(shù)。
針對所有的元素重復以上的步驟器予，除了最后一個浪藻。
持續(xù)每次對越來越少的元素重復上面的步驟，直到沒有任何一對數(shù)字需要比較乾翔。
快速排序
- 通過一趟排序將待排記錄分割成獨立的兩部分爱葵，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序反浓。
是冒泡排序的一種升級;
基本原理：
設定一個基準值（也就是軸）
將比軸小的值萌丈，移到軸的左邊，形成左子數(shù)列
將比軸大的值雷则，移到軸的右邊辆雾，形成右子數(shù)列
分別對左子數(shù)列和右子數(shù)列做上述三個步驟(遞歸)，直到左子數(shù)列或右子數(shù)列只剩一個值或沒有數(shù)值
選擇排序
- 比如在一個長度為N的無序數(shù)組中月劈，在第一趟遍歷N個數(shù)據(jù)度迂，找出其中最小的數(shù)值與第一個元素交換，第二趟遍歷剩下的N-1個數(shù)據(jù)艺栈，找出其中最小的數(shù)值與第二個元素交換......第N-1趟遍歷剩下的2個數(shù)據(jù)英岭，找出其中最小的數(shù)值與第N-1個元素交換，至此選擇排序完成湿右。
希爾排序
- 主要就是選定一個h的有序數(shù)組來進行預排序诅妹。這樣最后進行插入排序的時候，能使數(shù)據(jù)局部有序。就算交換的話吭狡，交換的次數(shù)也不會很多尖殃。這樣h序列稱為遞增序列。希爾的性能很大部分取決于遞增序列 划煮。一般來說我們使用這個序列3x + 1.
堆排序
- 它是選擇排序的一種送丰。可以利用數(shù)組的特點快速定位指定索引的元素弛秋。堆分為大根堆和小根堆器躏，是完全二叉樹。
二叉樹
- 在二叉樹的第i層上至多有2i-1個結點(i≥1)蟹略。
- 深度為k的二叉樹至多有2k-1個結點(k≥1)登失。
- 遍歷二叉樹
- 先序遍歷(DLR)
⑴訪問根結點；
⑵先序遍歷根結點的左子樹挖炬；
⑶先序遍歷根結點的右子樹揽浙。
- 中序遍歷(LDR)
⑴中序遍歷根結點的左子樹；
⑵訪問根結點意敛；
⑶中序遍歷根結點的右子樹馅巷。
- 后序遍歷(LRD)
⑴后序遍歷根結點的左子樹；
⑵后序遍歷根結點的右子樹草姻。
⑶訪問根結點钓猬；
- 層次遍歷（隊列實現(xiàn)）
構建一個隊列專門用來儲存二叉樹節(jié)點指針，先把根節(jié)點入隊撩独，假設是A逗噩，對A元素進行訪問，然后對A的左右孩子依次入隊跌榔，假設B,C异雁。A出隊列，再是對B進行訪問僧须，同樣將B的左右孩子入隊列纲刀，B出對列······重復以上，知道隊列為空担平。
哈希
- Hashing查找示绊，也稱為散列查找或雜湊查找。它既是一種查找方法暂论，又是一種存貯方法面褐，稱為散列存貯。散列存貯的內存存放形式也稱為散列表
- 哈希函數(shù)
在記錄的關鍵字與記錄的存儲地址之間建立的一種對應關系叫哈希函數(shù)取胎。
哈希函數(shù)是從關鍵字空間到存儲地址空間的一種映象
哈希函數(shù)可寫成：addr(ai)=H(keyi)
ai是表中的一個元素
addr(ai)是ai的存儲地址
keyi是ai的關鍵字
- 哈希表
應用哈希函數(shù)展哭，由記錄的關鍵字確定記錄在表中的地址湃窍，并將記錄放入此地址，這樣構成的表叫哈希表匪傍。
- 哈希查找
又叫散列查找您市，利用哈希函數(shù)進行查找的過程叫哈希查找。
- 沖突：key1?key2役衡，但H(key1)=H(key2)的現(xiàn)象叫沖突
