排序算法
冒泡排序
冒泡排序是最簡單的排序之一了揉抵，其大體思想就是通過與相鄰元素的比較和交換來把小的數(shù)交換到最前面野蝇。這個過程類似于水泡向上升一樣抛蚁，因此而得名椭赋。
舉個栗子：
對5,3,8,6,4這個無序序列進行冒泡排序。
1.首先從后向前冒泡扒寄，4和6比較鱼鼓，把4交換到前面，序列變成5,3,8,4,6该编。
2.同理4和8交換迄本，變成5,3,4,8,6,3和4無需交換。
3.5和3交換课竣，變成3,5,4,8,6,3.這樣一次冒泡就完了嘉赎，把最小的數(shù)3排到最前面了。
4.對剩下的序列依次冒泡就會得到一個有序序列于樟。冒泡排序的時間復(fù)雜度為O(n^2)公条。
實現(xiàn)代碼：
//冒泡排序，選擇排序迂曲，
//從最左邊開始 i=0
//比較第i個和第i+1個數(shù)字靶橱，如果arr[i]>arr[i+1],就將他們位置變化
//每一遍的結(jié)果，就是講最大的移動到最后面
//如果比較一遍后路捧，沒有移動任何一個元素降传，就表明這個數(shù)組已經(jīng)有序
public static void bobSort(int[] arr) {
boolean flag = true;
int a = arr.length - 1;
while (flag) {
flag = false;
for (int i = 0; i < a; i++) {
if (arr[i] > arr[i + 1]) {
int ch = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = ch;
flag = true;
}
}
a--;
}
}
選擇排序
選擇排序的思想其實和冒泡排序有點類似持际，都是在一次排序后把最小的元素放到最前面址遇。但是過程不同吩屹，冒泡排序是通過相鄰的比較和交換。而選擇排序是通過對整體的選擇章姓。
舉個栗子:
對5,3,8,6,4這個無序序列進行簡單選擇排序佳遣，
1.首先要選擇5以外的最小數(shù)來和5交換，也就是選擇3和5交換凡伊，一次排序后就變成了3,5,8,6,4.
2.對剩下的序列一次進行選擇和交換苍日，最終就會得到一個有序序列。
3.其實選擇排序可以看成冒泡排序的優(yōu)化窗声，因為其目的相同相恃，只是選擇排序只有在確定了最小數(shù)的前提下才進行交換，大大減少了交換的次數(shù)笨觅。選擇排序的時間復(fù)雜度為O(n^2)拦耐。
實現(xiàn)代碼：
// 選擇排序
// 從arr[i]后面選一個最小的，和arr[i]替換位置
public static void selectSort(int[] arr) {
int flag = 0;
int index = 0;
while (index < arr.length) {
for (int i = arr.length - 1; i > index; i--) {
if (arr[flag] > arr[i]) {
flag = i;
}
}
int a = arr[flag];
arr[flag] = arr[index];
arr[index] = a;
index++;
flag = index;
}
}
插入排序
插入排序不是通過交換位置而是通過比較找到合適的位置插入元素來達(dá)到排序的目的的见剩。
相信大家都有過打撲克牌的經(jīng)歷杀糯，特別是牌數(shù)較大的。在分牌時可能要整理自己的牌苍苞，牌多的時候怎么整理呢固翰？就是拿到一張牌狼纬，找到一個合適的位置插入。這個原理其實和插入排序是一樣的骂际。
舉個栗子:
對5,3,8,6,4這個無序序列進行簡單插入排序疗琉，
1.首先假設(shè)第一個數(shù)的位置時正確的，想一下在拿到第一張牌的時候歉铝，沒必要整理盈简。
2.然后3要插到5前面，把5后移一位太示，變成3,5,8,6,4.想一下整理牌的時候應(yīng)該也是這樣吧柠贤。
3.然后8不用動，6插在8前面类缤，8后移一位臼勉，4插在5前面，從5開始都向后移一位餐弱。
4.注意在插入一個數(shù)的時候要保證這個數(shù)前面的數(shù)已經(jīng)有序宴霸。簡單插入排序的時間復(fù)雜度也是O(n^2)。
實現(xiàn)代碼：
// 插入排序
// 前面i個已經(jīng)是有序的了岸裙，把第i+1個插入到前面i個里面合適的位置
public static void insetSort(int[] arr) {
int index = 0;
while (index < arr.length-1) {
for (int i = 0; i <= index; i++) {
if (arr[i] < arr[index + 1] && arr[i + 1] >= arr[index + 1]) {
moveArr(arr, index + 1, i+1);
}
}
index++;
}
}
// 插入排序所需要的移動方法
private static void moveArr(int[] arr, int start, int end) {
int a = arr[start];
for (int i = start; i > end; i--) {
arr[i] = arr[i - 1];
}
arr[end] = a;
}
快速排序
快速排序一聽名字就覺得很高端，在實際應(yīng)用當(dāng)中快速排序確實也是表現(xiàn)最好的排序算法速缆。
快速排序雖然高端降允，但其實其思想是來自冒泡排序，冒泡排序是通過相鄰元素的比較和交換把最小的冒泡到最頂端艺糜，而快速排序是比較和交換小數(shù)和大數(shù)剧董，這樣一來不僅把小數(shù)冒泡到上面同時也把大數(shù)沉到下面。
舉個栗子：
對5,3,8,6,4這個無序序列進行快速排序破停，思路是右指針找比基準(zhǔn)數(shù)小的翅楼，左指針找比基準(zhǔn)數(shù)大的，交換之真慢。
- 5,3,8,6,4 用5作為比較的基準(zhǔn)毅臊，最終會把5小的移動到5的左邊，比5大的移動到5的右邊黑界。
- 5,3,8,6,4 首先設(shè)置i,j兩個指針分別指向兩端管嬉，j指針先掃描（思考一下為什么？）4比5小停止朗鸠。然后i掃描蚯撩，8比5大停止。交換i,j位置烛占。
- 5,3,4,6,8 然后j指針再掃描胎挎，這時j掃描4時兩指針相遇。停止。然后交換4和基準(zhǔn)數(shù)犹菇。
- 4,3,5,6,8 一次劃分后達(dá)到了左邊比5小德迹，右邊比5大的目的。之后對左右子序列遞歸排序项栏，最終得到有序序列浦辨。
上面留下來了一個問題：為什么一定要j指針先動呢？首先這也不是絕對的沼沈，這取決于基準(zhǔn)數(shù)的位置流酬，因為在最后兩個指針相遇的時候，要交換基準(zhǔn)數(shù)到相遇的位置列另。一般選取第一個數(shù)作為基準(zhǔn)數(shù)芽腾，那么就是在左邊，所以最后相遇的數(shù)要和基準(zhǔn)數(shù)交換页衙，那么相遇的數(shù)一定要比基準(zhǔn)數(shù)小摊滔。所以j指針先移動才能先找到比基準(zhǔn)數(shù)小的數(shù)。
快速排序是不穩(wěn)定的店乐，其時間平均時間復(fù)雜度是O(nlgn)艰躺。
實現(xiàn)代碼：
其實上面的代碼還可以再優(yōu)化，上面代碼中基準(zhǔn)數(shù)已經(jīng)在pivotKey中保存了眨八，所以不需要每次交換都設(shè)置一個temp變量腺兴，在交換左右指針的時候只需要先后覆蓋就可以了。這樣既能減少空間的使用還能降低賦值運算的次數(shù)廉侧。優(yōu)化代碼如下：
//快速排序
//以第i個為基準(zhǔn)页响，從最右邊起，找到比arr[i]小的段誊，標(biāo)記arr[min],找到闰蚕。從第i個起，找到比arr[i]大的连舍，標(biāo)記為arr[max],交換max和min
//然后繼續(xù)没陡，直到下表max=min，然后把arr[i]和arr[max/min],交換索赏。
//此刻诗鸭，數(shù)組以arr[max/min],為界限，左邊比他小参滴，右邊比他大强岸，
//然后將這兩邊，繼續(xù)執(zhí)行這樣的操作
//進行一次劃分
public static int partition (int[] arr , int left, int right) {
// TODO Auto-generated method stub
int pivotKey = arr[left];
int pivotPointer = left;
while (left < right) {
while(arr[right] > pivotKey && left < right) {
right--;
}
while (arr[left] <= pivotKey && left < right) {
left++;
}
swap(arr, left, right);//交換位置
}
swap(arr, pivotPointer, left);
return left;
}
public static void quickSort(int[] arr ,int left , int right) {
if(left > right) {
return;
}
int pivotPos = partition(arr, left, right);
quickSort(arr, left, pivotPos-1);
quickSort(arr, pivotPos+1, right);
}
總結(jié)快速排序的思想：冒泡+二分+遞歸分治砾赔，慢慢體會蝌箍。青灼。。
堆排序
堆排序是借助堆來實現(xiàn)的選擇排序妓盲，思想同簡單的選擇排序杂拨，以下以大頂堆為例。注意：如果想升序排序就使用大頂堆悯衬，反之使用小頂堆弹沽。原因是堆頂元素需要交換到序列尾部。
首先筋粗，實現(xiàn)堆排序需要解決兩個問題：
- 如何由一個無序序列鍵成一個堆策橘？
- 如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個新的堆娜亿？
第一個問題丽已，可以直接使用線性數(shù)組來表示一個堆，由初始的無序序列建成一個堆就需要自底向上從第一個非葉元素開始挨個調(diào)整成一個堆买决。
第二個問題沛婴，怎么調(diào)整成堆？首先是將堆頂元素和最后一個元素交換督赤。然后比較當(dāng)前堆頂元素的左右孩子節(jié)點嘁灯，因為除了當(dāng)前的堆頂元素，左右孩子堆均滿足條件躲舌，這時需要選擇當(dāng)前堆頂元素與左右孩子節(jié)點的較大者（大頂堆）交換丑婿，直至葉子節(jié)點。我們稱這個自堆頂自葉子的調(diào)整成為篩選孽糖。
從一個無序序列建堆的過程就是一個反復(fù)篩選的過程枯冈。若將此序列看成是一個完全二叉樹毅贮，則最后一個非終端節(jié)點是n/2取底個元素办悟，由此篩選即可。
舉個栗子：
49,38,65,97,76,13,27,49序列的堆排序建初始堆和調(diào)整的過程如下：
實現(xiàn)代碼：
希爾排序
希爾排序是插入排序的一種高效率的實現(xiàn)滩褥，也叫縮小增量排序病蛉。簡單的插入排序中，如果待排序列是正序時瑰煎，時間復(fù)雜度是O(n)铺然，如果序列是基本有序的，使用直接插入排序效率就非常高酒甸。希爾排序就利用了這個特點魄健。基本思想是：先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序插勤，待整個序列中的記錄基本有序時再對全體記錄進行一次直接插入排序沽瘦。
舉個栗子：
從上述排序過程可見革骨，希爾排序的特點是，子序列的構(gòu)成不是簡單的逐段分割析恋，而是將某個相隔某個增量的記錄組成一個子序列良哲。
如上面的例子，第一堂排序時的增量為5助隧，第二趟排序的增量為3筑凫。由于前兩趟的插入排序中記錄的關(guān)鍵字是和同一子序列中的前一個記錄的關(guān)鍵字進行比較，因此關(guān)鍵字較小的記錄就不是一步一步地向前挪動并村，而是跳躍式地往前移巍实，從而使得進行最后一趟排序時，整個序列已經(jīng)做到基本有序橘霎，只要作記錄的少量比較和移動即可蔫浆。因此希爾排序的效率要比直接插入排序高。
希爾排序的分析是復(fù)雜的姐叁，時間復(fù)雜度是所取增量的函數(shù)瓦盛，這涉及一些數(shù)學(xué)上的難題。但是在大量實驗的基礎(chǔ)上推出當(dāng)n在某個范圍內(nèi)時外潜，時間復(fù)雜度可以達(dá)到O(n^1.3)原环。
實現(xiàn)代碼：
/**
*希爾排序，類似不同步長的選擇排序
* @param args
*/
public static void shellSort(int[] arr) {
int dk = arr.length/2;
while (dk>=1) {
System.out.printf("dk=%d",dk);
System.out.println();
shellInsertSort(arr, dk);
dk = dk/2;
}
}
//一次希爾排序
public static void shellInsertSort(int[] arr, int dk) {
for (int i = dk; i < arr.length; i++) {//從后面往前插入
if(arr[i] < arr[i-dk]) {
int j;
int x = arr[i];
arr[i] = arr[i-dk];
for(j = i-dk;j>=0&&x<arr[j];j = j-dk) {
arr[j+dk] = arr[j];
}
arr[j+dk] = x;
}
}
}
歸并排序
歸并排序是另一種不同的排序方法处窥，因為歸并排序使用了遞歸分治的思想嘱吗，所以理解起來比較容易。
其基本思想是滔驾，先遞歸劃分子問題谒麦，然后合并結(jié)果。把待排序列看成由兩個有序的子序列哆致，然后合并兩個子序列绕德，然后把子序列看成由兩個有序序列。摊阀。耻蛇。。胞此。倒著來看臣咖，其實就是先兩兩合并，然后四四合并漱牵。夺蛇。。最終形成有序序列酣胀〉笊猓空間復(fù)雜度為O(n)愿卸，時間復(fù)雜度為O(nlogn)。
舉個栗子：
實現(xiàn)代碼：
/**
* 合并兩個有序數(shù)組
* @param arr 待合并數(shù)組
* @param left 左指針
* @param mid 中間指針
* @param right 右指針
*/
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right-left+1];//中間過度數(shù)組
int index1 = left;//遍歷其中一個數(shù)組
int index2 = mid+1;//遍歷另外一個數(shù)組截型，因為mid可能等于left,遍歷的時候趴荸，不能左右數(shù)組都擁有mid這個數(shù)組值。
int index = 0;//中間數(shù)組temp的下標(biāo)
while(index1 <= mid && index2 <= right) {
if(arr[index1]>arr[index2]) {
temp[index] = arr[index2];
index2++;
}else {
temp[index] = arr[index1];
index1++;
}
index++;
}
while(index1 <= mid) {//把第一個數(shù)組剩余沒有插入的直接插入
temp[index] = arr[index1];
index++;
index1++;
}
while(index2 <= right) {//把第二個剩余沒有插入的直接插入
temp[index] = arr[index2];
index++;
index2++;
}
//覆蓋原來的數(shù)組
for (int i = 0; i < temp.length; i++) {
arr[left+i] = temp[i];
}
}
計數(shù)排序
如果在面試中有面試官要求你寫一個O(n)時間復(fù)雜度的排序算法宦焦，你千萬不要立刻說：這不可能发钝！雖然前面基于比較的排序的下限是O(nlogn)。但是確實也有線性時間復(fù)雜度的排序波闹，只不過有前提條件酝豪，就是待排序的數(shù)要滿足一定的范圍的整數(shù)，而且計數(shù)排序需要比較多的輔助空間精堕。其基本思想是孵淘，用待排序的數(shù)作為計數(shù)數(shù)組的下標(biāo)，統(tǒng)計每個數(shù)字的個數(shù)歹篓。然后依次輸出即可得到有序序列瘫证。
實現(xiàn)代碼：
/*
* 計數(shù)排序
* 用待排序的數(shù)作為計數(shù)數(shù)組的下標(biāo)，統(tǒng)計每個數(shù)字的個數(shù)庄撮。然后依次輸出即可得到有序序列背捌。
*/
public static void CountSort(int[] arr) {
if(arr.length == 0 || arr == null) {
return;
}
int maxsize = maxSize(arr);
int[] tmp = new int[maxsize+1];
for (int i = 0; i < arr.length; i++) {
tmp[arr[i]]++;
}
//將記錄好的數(shù)據(jù)，再放回arr數(shù)組中
int index = 0;
for (int i = 0; i < tmp.length; i++) {
for (int j = 1; j <= tmp[i]; j++) {//改坐標(biāo)下的數(shù)組洞斯，記錄了幾次毡庆，就循環(huán)輸出幾次
arr[index] = i;
index++;
}
}
}
public static int maxSize(int[] arr) {
int flag = 0;
for (int i = 0; i < arr.length; i++) {
if(arr[i]>arr[flag]) {
flag = i;
}
}
return arr[flag];
}
桶排序
桶排序算是計數(shù)排序的一種改進和推廣，但是網(wǎng)上有許多資料把計數(shù)排序和桶排序混為一談烙如。其實桶排序要比計數(shù)排序復(fù)雜許多么抗。
對桶排序的分析和解釋借鑒這位兄弟的文章（有改動）：http://hxraid.iteye.com/blog/647759
桶排序的基本思想：
假設(shè)有一組長度為N的待排關(guān)鍵字序列K[1….n]。首先將這個序列劃分成M個的子區(qū)間(桶) 亚铁。然后基于某種映射函數(shù) 蝇刀，將待排序列的關(guān)鍵字k映射到第i個桶中(即桶數(shù)組B的下標(biāo) i) ，那么該關(guān)鍵字k就作為B[i]中的元素(每個桶B[i]都是一組大小為N/M的序列)刀闷。接著對每個桶B[i]中的所有元素進行比較排序(可以使用快排)熊泵。然后依次枚舉輸出B[0]….B[M]中的全部內(nèi)容即是一個有序序列仰迁。bindex=f(key) 其中甸昏，bindex 為桶數(shù)組B的下標(biāo)(即第bindex個桶), k為待排序列的關(guān)鍵字。桶排序之所以能夠高效徐许，其關(guān)鍵在于這個映射函數(shù)施蜜，它必須做到：如果關(guān)鍵字k1
舉個栗子：
假如待排序列K= {49、 38 雌隅、 35翻默、 97 缸沃、 76、 73 修械、 27趾牧、 49 }。這些數(shù)據(jù)全部在1—100之間肯污。因此我們定制10個桶翘单，然后確定映射函數(shù)f(k)=k/10。則第一個關(guān)鍵字49將定位到第4個桶中(49/10=4)蹦渣。依次將所有關(guān)鍵字全部堆入桶中哄芜，并在每個非空的桶中進行快速排序后得到如圖所示。只要順序輸出每個B[i]中的數(shù)據(jù)就可以得到有序序列了柬唯。
桶排序分析：
桶排序利用函數(shù)的映射關(guān)系认臊，減少了幾乎所有的比較工作。實際上锄奢，桶排序的f(k)值的計算失晴，其作用就相當(dāng)于快排中劃分，希爾排序中的子序列拘央，歸并排序中的子問題师坎，已經(jīng)把大量數(shù)據(jù)分割成了基本有序的數(shù)據(jù)塊(桶)。然后只需要對桶中的少量數(shù)據(jù)做先進的比較排序即可堪滨。
對N個關(guān)鍵字進行桶排序的時間復(fù)雜度分為兩個部分：
(1) 循環(huán)計算每個關(guān)鍵字的桶映射函數(shù)胯陋，這個時間復(fù)雜度是O(N)。
(2) 利用先進的比較排序算法對每個桶內(nèi)的所有數(shù)據(jù)進行排序袱箱，其時間復(fù)雜度為 ∑ O(Ni*logNi) 遏乔。其中Ni 為第i個桶的數(shù)據(jù)量。
很顯然发笔，第(2)部分是桶排序性能好壞的決定因素盟萨。盡量減少桶內(nèi)數(shù)據(jù)的數(shù)量是提高效率的唯一辦法(因為基于比較排序的最好平均時間復(fù)雜度只能達(dá)到O(N*logN)了)。因此了讨，我們需要盡量做到下面兩點：
(1) 映射函數(shù)f(k)能夠?qū)個數(shù)據(jù)平均的分配到M個桶中捻激，這樣每個桶就有[N/M]個數(shù)據(jù)量。
(2) 盡量的增大桶的數(shù)量前计。極限情況下每個桶只能得到一個數(shù)據(jù)胞谭，這樣就完全避開了桶內(nèi)數(shù)據(jù)的“比較”排序操作。當(dāng)然男杈，做到這一點很不容易丈屹，數(shù)據(jù)量巨大的情況下，f(k)函數(shù)會使得桶集合的數(shù)量巨大伶棒，空間浪費嚴(yán)重旺垒。這就是一個時間代價和空間代價的權(quán)衡問題了彩库。
對于N個待排數(shù)據(jù)，M個桶先蒋，平均每個桶[N/M]個數(shù)據(jù)的桶排序平均時間復(fù)雜度為：
O(N)+O(M(N/M)log(N/M))=O(N+N(logN-logM))=O(N+NlogN-N*logM)
當(dāng)N=M時骇钦，即極限情況下每個桶只有一個數(shù)據(jù)時。桶排序的最好效率能夠達(dá)到O(N)竞漾。
總結(jié)：
桶排序的平均時間復(fù)雜度為線性的O(N+C)司忱，其中C=N*(logN-logM)。如果相對于同樣的N畴蹭，桶數(shù)量M越大坦仍，其效率越高，最好的時間復(fù)雜度達(dá)到O(N)叨襟。 當(dāng)然桶排序的空間復(fù)雜度 為O(N+M)繁扎，如果輸入數(shù)據(jù)非常龐大，而桶的數(shù)量也非常多糊闽，則空間代價無疑是昂貴的梳玫。此外，桶排序是穩(wěn)定的右犹。
實現(xiàn)代碼：
/**
* 桶排序
* @param arr
* @return
*/
public static void bucketSort(int[] arr) {
if(arr == null|| arr.length==0) {
return;
}
ArrayList<LinkedList> arrayList = new ArrayList<LinkedList>();//方便移動數(shù)據(jù)提澎，使用linkList裝數(shù)據(jù)
for (int i = 0; i < arr.length/10; i++) {
arrayList.add(new LinkedList<Integer>());
}
for (int i = 0; i < arr.length; i++) {//開始桶排序
int index = arr[i]/10;
arrayList.get(index).add(arr[i]);
}
//上面只是把數(shù)據(jù)放到同樣的桶里面了，但是不一定是排好序的念链，需要排一下需
//可以自己手寫排序盼忌，也可以使用Collection進行排序
for (LinkedList<Integer> linkedList : arrayList) {
Collections.sort(linkedList);
}
//開始獲取桶里面的數(shù)據(jù)，放到arr原始的數(shù)組中
int index = 0;
for (LinkedList<Integer> linkedList : arrayList) {
for (int i = 0; i < linkedList.size(); i++) {
arr[index++] = linkedList.get(i);
}
}
}
基數(shù)排序
基數(shù)排序又是一種和前面排序方式不同的排序方式掂墓，基數(shù)排序不需要進行記錄關(guān)鍵字之間的比較谦纱。
基數(shù)排序是一種借助多關(guān)鍵字排序思想對單邏輯關(guān)鍵字進行排序的方法。所謂的多關(guān)鍵字排序就是有多個優(yōu)先級不同的關(guān)鍵字君编。
比如說成績的排序跨嘉，如果兩個人總分相同，則語文高的排在前面吃嘿，語文成績也相同則數(shù)學(xué)高的排在前面祠乃。。兑燥。如果對數(shù)字進行排序亮瓷，那么個位、十位贪嫂、百位就是不同優(yōu)先級的關(guān)鍵字艾蓝，如果要進行升序排序力崇，那么個位斗塘、十位、百位優(yōu)先級一次增加亮靴♀擅耍基數(shù)排序是通過多次的收分配和收集來實現(xiàn)的，關(guān)鍵字優(yōu)先級低的先進行分配和收集茧吊。
舉個栗子：
實現(xiàn)代碼：
/**
* 基數(shù)排序
* @param args
*/
public static void radixSort(int[] arr) {
ArrayList<ArrayList<Integer>> arrayList = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++) {//由于需要多次對基數(shù)進行調(diào)整贞岭，所以每次都需要清理一下基數(shù)，否則會有臟數(shù)據(jù)
arrayList.add(new ArrayList<Integer>());
}
int step = 1;
int array0Size = arrayList.get(0).size();
while(array0Size < arr.length) { //基數(shù)第一個裝了全部數(shù)據(jù)之后搓侄，表示已經(jīng)有序
System.out.println("arrayList.size="+arrayList.get(0).size()+",arr.length="+arr.length);
for (int i = 0; i < arr.length; i++) {
int index = (arr[i]/step)%10;
arrayList.get(index).add(arr[i]);
}
copy(arr,arrayList);
System.out.println("step = "+step);
step = step*10;
array0Size = arrayList.get(0).size();
arrayList.clear();
for (int i = 0; i < 10; i++) {//由于需要多次對基數(shù)進行調(diào)整瞄桨，所以每次都需要清理一下基數(shù)，否則會有臟數(shù)據(jù)
arrayList.add(new ArrayList<Integer>());
}
}
}
//讀出讶踪，并覆蓋元素組
public static void copy(int[] arr, ArrayList<ArrayList<Integer>> arrayList) {
int index = 0;
for (ArrayList arrayList2 : arrayList) {
System.out.println(arrayList2);
for (int i = 0; i < arrayList2.size(); i++) {
arr[index] = (int) arrayList2.get(i);
index++;
}
}
}
堆排序（性能很不錯）
大頂堆：
父節(jié)點大于左右子節(jié)點芯侥，左右子節(jié)點不進行大小比較
小頂堆：
父節(jié)點小于左右子節(jié)點，左右子節(jié)點不做比較乳讥。
思路：
通過大頂堆或者小頂堆的思路將數(shù)組進行排序（這里的堆柱查，指的是一個完全二叉樹，在數(shù)組中云石，完全二叉樹的父節(jié)點和左右葉子結(jié)點的關(guān)系為：父節(jié)點為n唉工，左子節(jié)點為2n+1，又子節(jié)點為2n+2）汹忠。
大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
如下圖：
步驟一 構(gòu)造初始堆淋硝。將給定無序序列構(gòu)造成一個大頂堆（一般升序采用大頂堆，降序采用小頂堆)宽菜。
a.假設(shè)給定無序序列結(jié)構(gòu)如下
2.此時我們從最后一個非葉子結(jié)點開始（葉結(jié)點自然不用調(diào)整奖地，第一個非葉子結(jié)點 arr.length/2-1=5/2-1=1，也就是下面的6結(jié)點）赋焕，從左至右参歹，從下至上進行調(diào)整。
4.找到第二個非葉節(jié)點4隆判，由于[4,9,8]中9元素最大犬庇，4和9交換。
這時侨嘀，交換導(dǎo)致了子根[4,5,6]結(jié)構(gòu)混亂臭挽，繼續(xù)調(diào)整，[4,5,6]中6最大咬腕，交換4和6欢峰。
此時，我們就將一個無需序列構(gòu)造成了一個大頂堆。
步驟二 將堆頂元素與末尾元素進行交換纽帖，使末尾元素最大宠漩。然后繼續(xù)調(diào)整堆，再將堆頂元素與末尾元素交換懊直，得到第二大元素扒吁。如此反復(fù)進行交換犬缨、重建公般、交換。
a.將堆頂元素9和末尾元素4進行交換
b.重新調(diào)整結(jié)構(gòu)狸吞，使其繼續(xù)滿足堆定義
c.再將堆頂元素8與末尾元素5進行交換融撞，得到第二大元素8.
后續(xù)過程盼铁，繼續(xù)進行調(diào)整，交換尝偎，如此反復(fù)進行捉貌，最終使得整個序列有序
再簡單總結(jié)下堆排序的基本思路：
a.將無需序列構(gòu)建成一個堆，根據(jù)升序降序需求選擇大頂堆或小頂堆;
b.將堆頂元素與末尾元素交換冬念，將最大元素"沉"到數(shù)組末端;
c.重新調(diào)整結(jié)構(gòu)趁窃，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素急前，反復(fù)執(zhí)行調(diào)整+交換步驟醒陆，直到整個序列有序。
代碼實現(xiàn)：
/**
* 堆排序
*
* @author zhanbei
*
*/
public class HeapSort {
public static void main(String[] arg) {
// TODO Auto-generated method stub
int[] arr = { 4, 6, 8, 5, 9 };
heapSort(arr);
System.out.println("排序后的arr = " + Arrays.toString(arr));
}
// 編寫一個堆排序
public static void heapSort(int[] arr) {
System.out.println("開始堆排序");
int temp = 0;// 每次堆排序后裆针，把堆頂元素保存到數(shù)組后刨摩，用于交換
// 開始構(gòu)建大頂堆，
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
// 將堆頂元素沉淀到末端
// 調(diào)整結(jié)構(gòu)世吨，繼續(xù)排序
// 再次沉淀
for (int j = arr.length - 1; j > 0; j--) {
System.out.println("j = " + j);
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, j);
}
}
// 將一個數(shù)組調(diào)整為大頂堆
/**
* 1澡刹、比較該父節(jié)點下的左右子節(jié)點 2、左右子節(jié)點較大的和父節(jié)點比較 3耘婚、將父節(jié)點和較大子節(jié)點交換罢浇，同時下標(biāo)交換，便于后期繼續(xù)比較
*/
/**
*
* @param arr 待調(diào)整的數(shù)組
* @param i 標(biāo)識葉子結(jié)點在數(shù)組中的額索引
* @param length 對少個元素進行調(diào)整沐祷，length在逐漸減少
*/
public static void adjustHeap(int arr[], int i, int length) {
int temp = arr[i];
for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
if (k+1 < length && arr[k] < arr[k + 1]) { // 比較左右子節(jié)點大小
k++;// 選大的
}
if (arr[k] > temp) {// 比較父節(jié)點和大的子節(jié)點的大小
arr[i] = arr[k];// 交換大的到父節(jié)點
i = k;// 交換下表
} else {
break;
}
arr[i] = temp;// 將父節(jié)點的值交換下來嚷闭。
}
}
}
總結(jié):
在前面的介紹和分析中我們提到了冒泡排序、選擇排序赖临、插入排序三種簡單的排序及其變種快速排序胞锰、堆排序、希爾排序三種比較高效的排序兢榨。后面我們又分析了基于分治遞歸思想的歸并排序還有計數(shù)排序嗅榕、桶排序顺饮、基數(shù)排序三種線性排序。我們可以知道排序算法要么簡單有效凌那，要么是利用簡單排序的特點加以改進兼雄，要么是以空間換取時間在特定情況下的高效排序。但是這些排序方法都不是固定不變的案怯，需要結(jié)合具體的需求和場景來選擇甚至組合使用君旦。才能達(dá)到高效穩(wěn)定的目的澎办。沒有最好的排序嘲碱，只有最適合的排序。
下面就總結(jié)一下排序算法的各自的使用場景和適用場合局蚀。
- 從平均時間來看麦锯，快速排序是效率最高的，但快速排序在最壞情況下的時間性能不如堆排序和歸并排序琅绅。而后者相比較的結(jié)果是扶欣，在n較大時歸并排序使用時間較少，但使用輔助空間較多千扶。
- 上面說的簡單排序包括除希爾排序之外的所有冒泡排序料祠、插入排序、簡單選擇排序澎羞。其中直接插入排序最簡單髓绽，但序列基本有序或者n較小時，直接插入排序是好的方法妆绞，因此常將它和其他的排序方法顺呕，如快速排序、歸并排序等結(jié)合在一起使用括饶。
- 基數(shù)排序的時間復(fù)雜度也可以寫成O(d*n)株茶。因此它最使用于n值很大而關(guān)鍵字較小的的序列。若關(guān)鍵字也很大图焰，而序列中大多數(shù)記錄的最高關(guān)鍵字均不同启盛，則亦可先按最高關(guān)鍵字不同，將序列分成若干小的子序列技羔，而后進行直接插入排序驰徊。
- 從方法的穩(wěn)定性來比較，基數(shù)排序是穩(wěn)定的內(nèi)排方法堕阔，所有時間復(fù)雜度為O(n^2)的簡單排序也是穩(wěn)定的棍厂。但是快速排序、堆排序超陆、希爾排序等時間性能較好的排序方法都是不穩(wěn)定的牺弹。穩(wěn)定性需要根據(jù)具體需求選擇浦马。
- 上面的算法實現(xiàn)大多數(shù)是使用線性存儲結(jié)構(gòu)，像插入排序這種算法用鏈表實現(xiàn)更好张漂，省去了移動元素的時間晶默。具體的存儲結(jié)構(gòu)在具體的實現(xiàn)版本中也是不同的。
附：基于比較排序算法時間下限為O(nlogn)的證明：
基于比較排序下限的證明是通過決策樹證明的航攒，決策樹的高度Ω（nlgn）磺陡，這樣就得出了比較排序的下限。
首先要引入決策樹漠畜。 首先決策樹是一顆二叉樹币他，每個節(jié)點表示元素之間一組可能的排序，它予以京進行的比較相一致憔狞，比較的結(jié)果是樹的邊蝴悉。 先來說明一些二叉樹的性質(zhì)，令T是深度為d的二叉樹瘾敢，則T最多有2^片樹葉拍冠。 具有L片樹葉的二叉樹的深度至少是logL。 所以簇抵，對n個元素排序的決策樹必然有n!片樹葉（因為n個數(shù)有n!種不同的大小關(guān)系）庆杜，所以決策樹的深度至少是log(n!)，即至少需要log(n!)次比較碟摆。 而 log(n!)=logn+log(n-1)+log(n-2)+…+log2+log1 >=logn+log(n-1)+log(n-2)+…+log(n/2) >=(n/2)log(n/2) >=(n/2)logn-n/2 =O(nlogn) 所以只用到比較的排序算法最低時間復(fù)雜度是O(nlogn)晃财。
查找算法
二分查找
前提：已經(jīng)有序的數(shù)組，通過遞歸或者偽遞歸的方式進行查找焦履，通過和數(shù)組中間數(shù)對比拓劝，如果不是，就根據(jù)大小嘉裤，采取決策郑临，向右遞歸或者左遞歸繼續(xù)二分查找
實現(xiàn)代碼：
/**
* 二分查找，前提：有序
*
* @param arr 需要排序數(shù)組
* @param start 開始下表
* @param end 結(jié)束下表
* @param target 要查找的數(shù)字
*/
public static int binarySearch(int[] arr, int start, int end, int target) {
if(start>end) {
return -1;
}
int flag = (start + end) / 2;
if (arr[flag] == target) {
return flag;
}
if (arr[flag] > target) {
return binarySearch(arr, start, flag-1, target);
}
if (arr[flag] < target) {
return binarySearch(arr, flag+1, end, target);
}
return -1;
}
插值查找算法
- 插值查找原理介紹:
插值查找算法類似于二分查找屑宠，不同的是插值查找每次從自適應(yīng)mid處開始查找厢洞。
- 將折半查找中的求mid索引的公式，low表示左邊索引left, high表示右邊索引right.
key就是前面我們講的findVal
- int mid = low + (high - low) * (key - arr[low])/ (arr[high]- arr[low]) ;/插值索引/
對應(yīng)前面的代碼公式:
int mid= left+ (right - left) * (findVal - arr[left])/ (arr[right] - arr[left])
備注：主要判斷mid是否數(shù)組越界
斐波那契（換金分割）查找算法
1)黃金分割點是指把一條線段分割為兩部分典奉，使其中-部分與 全長之比等于另- -部分 與這部分之比躺翻。取其前三位，數(shù)字的近似值是0.618卫玖。由于按此比例設(shè)計的造型十分美麗公你，因此稱為黃金分割，也稱為中外比假瞬。這是一個神奇的數(shù)字陕靠，會帶來意向不大的效果迂尝。
2)斐波那契數(shù)列 {1,1,2,3,5, 8, 13,21,34,55 }發(fā)現(xiàn)斐波那契數(shù)列的兩個相鄰數(shù)的比例，無限接近黃金分割值
斐波那契查找原理
斐波那契查找原理與前兩種相似剪芥，僅僅改變了中間結(jié)點(mid)的位置垄开，mid不再是中間或插值得到，而是位置税肪，于黃金分割點附近溉躲，即mid=low+F(k-1)-1 (F代表斐波那契數(shù)列)，如下圖所示
?對F(k-1)-1的理解:
- 由斐波那契數(shù)列F[k]=F[k-1]+F[k-2] 的性質(zhì)益兄，可以得到(F[k]-1) = (F[k-1]-1) + (F[k-2]-1) +1锻梳。該式說明:只要順序表的長度為F[k]-1,則可以將該表分成長度為F[k-1]-1和F[k<-2]-1的兩段，即如上圖所示偏塞。從而中間位置為mid=low+F(k-1)-1
2)類似的唱蒸， 每一.子段也可以用相同的方式分割
3)但順序表長度n 不一定剛好等于F[k]-1,所以需要將原來的順序表長度n增加至F[k]-1邦鲫。這里的k值只要能使得F[k]-1恰好大于或等于n即可灸叼，由以下代碼得到,順序表長度增加后，新增的位置(從n+1到F[k]-1位置)庆捺，都賦為n位置的值即可古今。while(n> fb(k)-1) k++;
代碼實現(xiàn)：
/**
* 產(chǎn)生一個斐波那契數(shù)列
* @param maxSize 數(shù)列對大長度
* @return 如果不存在，就直接返回-1滔以，如果存在捉腥，返回下表
*/
private static int[] fib(int maxSize) {
int[] f = new int[maxSize];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < maxSize; i++) {
f[i] = f[i-1] + f[i-2];
}
return f;
}
public static int fibSearch(int[] arr , int key) {
int low = 0;
int hight = arr.length-1;
int k = 0;//標(biāo)識斐波那契分割數(shù)值的下表
int mid = 0 ;
int[] f = fib(arr.length);
//獲取斐波那契分割數(shù)組下表
while (hight > f[k] - 1) {
k++;
}
//因為f[k]值可能大于arr的長度，我們使用arrays類你画，構(gòu)造一個新的數(shù)組抵碟，并指向arr[]
int[] tmp = Arrays.copyOf(arr, f[k]);
//補齊新構(gòu)造的數(shù)組的后幾位
for(int i = hight+1;i<tmp.length;i++) {
tmp[i] = arr[hight];
}
while (hight>=low) {
mid=low+f[k-1]-1;
if(arr[mid] > key) {
hight = mid-1;
k--;
}else if(arr[mid] < key) {
low = mid+1;
k-=2;
}else {
if(mid<=hight) {
return mid;
}else {
return hight;
}
}
}
return -1;
}
哈希表
代碼實現(xiàn)：
//雇員信息
class Emp {
public int id;
public String name;
public Emp nextEmp;
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Emp getNextEmp() {
return nextEmp;
}
public void setNextEmp(Emp nextEmp) {
this.nextEmp = nextEmp;
}
}
//哈希表中的鏈表頭結(jié)點
class EmpLinkedList {
Emp head = null;
}
//哈希表
class HashTab {
EmpLinkedList[] empLinkedListsArr;
public HashTab(int size) {
empLinkedListsArr = new EmpLinkedList[size];
}
public void addEmp(Emp emp) {
int flag = emp.id % empLinkedListsArr.length;
Emp empFlag = empLinkedListsArr[flag].head;
while (Optional.ofNullable(empFlag).map(Emp::getNextEmp) != null) {
if (empFlag.getNextEmp().getId() > emp.id) {// 從小到大排序
emp.nextEmp = empFlag.nextEmp;
empFlag.nextEmp = emp;
}
}
}
public Emp get(int id) {
int flag = id % empLinkedListsArr.length;
Emp empFlag = empLinkedListsArr[flag].head;
while (Optional.ofNullable(empFlag).map(Emp::getNextEmp) != null) {
if(empFlag.id == id) {
return empFlag;
}
}
return null;
}
//.................
}
樹結(jié)構(gòu)
二叉樹
各種樹定義
滿二叉樹：一棵有n層的二叉樹，除第n層外坏匪，每層都有兩個子節(jié)點拟逮，那么這棵樹就是滿二叉樹。
完全二叉樹：
完全二叉樹由滿二叉樹引進而來适滓。假設(shè)二叉樹有h層敦迄，除第h層外，其他各層的節(jié)點數(shù)均已達(dá)到最大個數(shù)（1至h-1層為滿二叉樹）凭迹，第h層所有的節(jié)點都集中在最左邊罚屋，這棵樹就是完全二叉樹。
另見：http://www.reibang.com/p/683ccf7b4712
遍歷(前序遍歷嗅绸，中序遍歷脾猛，后序遍歷)：
前序遍歷：
- 先輸出當(dāng)前節(jié)點
- 如果左子樹點不為空，則遞歸繼續(xù)前序遍歷
- 如果右子樹節(jié)點不為空鱼鸠，則遞歸繼續(xù)前序遍歷
中序遍歷：
- 如果當(dāng)前節(jié)點左子樹不為空猛拴，則遞歸中序遍歷
- 輸出當(dāng)前節(jié)點
- 如果當(dāng)前節(jié)點右子樹不為空喉刘，則遞歸中序遍歷
后序遍歷：
- 如果當(dāng)前節(jié)點左子樹不為空，遞歸后序遍歷
- 如果當(dāng)前節(jié)點右子樹不為空漆弄，遞歸后序遍歷
- 輸出輸出當(dāng)前節(jié)點
二叉樹查找指定節(jié)點
使用中序睦裳，前序，后序遍歷進行查找
代碼實現(xiàn)：
//先創(chuàng)建HeroNode 結(jié)點
class HeroNode {
private int no;
private String name;
private HeroNode left; //默認(rèn)null
private HeroNode right; //默認(rèn)null
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public HeroNode getLeft() {
return left;
}
public void setLeft(HeroNode left) {
this.left = left;
}
public HeroNode getRight() {
return right;
}
public void setRight(HeroNode right) {
this.right = right;
}
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + "]";
}
//遞歸刪除結(jié)點
//1.如果刪除的節(jié)點是葉子節(jié)點撼唾，則刪除該節(jié)點
//2.如果刪除的節(jié)點是非葉子節(jié)點廉邑，則刪除該子樹
public void delNode(int no) {
//思路
/*
* 1. 因為我們的二叉樹是單向的，所以我們是判斷當(dāng)前結(jié)點的子結(jié)點是否需要刪除結(jié)點倒谷，而不能去判斷當(dāng)前這個結(jié)點是不是需要刪除結(jié)點.
2. 如果當(dāng)前結(jié)點的左子結(jié)點不為空蛛蒙，并且左子結(jié)點 就是要刪除結(jié)點，就將this.left = null; 并且就返回(結(jié)束遞歸刪除)
3. 如果當(dāng)前結(jié)點的右子結(jié)點不為空渤愁，并且右子結(jié)點 就是要刪除結(jié)點牵祟，就將this.right= null ;并且就返回(結(jié)束遞歸刪除)
4. 如果第2和第3步?jīng)]有刪除結(jié)點，那么我們就需要向左子樹進行遞歸刪除
5. 如果第4步也沒有刪除結(jié)點抖格，則應(yīng)當(dāng)向右子樹進行遞歸刪除.
*/
//2. 如果當(dāng)前結(jié)點的左子結(jié)點不為空诺苹，并且左子結(jié)點 就是要刪除結(jié)點，就將this.left = null; 并且就返回(結(jié)束遞歸刪除)
if(this.left != null && this.left.no == no) {
this.left = null;
return;
}
//3.如果當(dāng)前結(jié)點的右子結(jié)點不為空雹拄，并且右子結(jié)點 就是要刪除結(jié)點收奔，就將this.right= null ;并且就返回(結(jié)束遞歸刪除)
if(this.right != null && this.right.no == no) {
this.right = null;
return;
}
//4.我們就需要向左子樹進行遞歸刪除
if(this.left != null) {
this.left.delNode(no);
}
//5.則應(yīng)當(dāng)向右子樹進行遞歸刪除
if(this.right != null) {
this.right.delNode(no);
}
}
//編寫前序遍歷的方法
public void preOrder() {
System.out.println(this); //先輸出父結(jié)點
//遞歸向左子樹前序遍歷
if(this.left != null) {
this.left.preOrder();
}
//遞歸向右子樹前序遍歷
if(this.right != null) {
this.right.preOrder();
}
}
//中序遍歷
public void infixOrder() {
//遞歸向左子樹中序遍歷
if(this.left != null) {
this.left.infixOrder();
}
//輸出父結(jié)點
System.out.println(this);
//遞歸向右子樹中序遍歷
if(this.right != null) {
this.right.infixOrder();
}
}
//后序遍歷
public void postOrder() {
if(this.left != null) {
this.left.postOrder();
}
if(this.right != null) {
this.right.postOrder();
}
System.out.println(this);
}
//前序遍歷查找
/**
*
* @param no 查找no
* @return 如果找到就返回該Node ,如果沒有找到返回 null
*/
public HeroNode preOrderSearch(int no) {
System.out.println("進入前序遍歷");
//比較當(dāng)前結(jié)點是不是
if(this.no == no) {
return this;
}
//1.則判斷當(dāng)前結(jié)點的左子節(jié)點是否為空，如果不為空滓玖，則遞歸前序查找
//2.如果左遞歸前序查找坪哄，找到結(jié)點，則返回
HeroNode resNode = null;
if(this.left != null) {
resNode = this.left.preOrderSearch(no);
}
if(resNode != null) {//說明我們左子樹找到
return resNode;
}
//1.左遞歸前序查找势篡，找到結(jié)點翩肌，則返回，否繼續(xù)判斷禁悠，
//2.當(dāng)前的結(jié)點的右子節(jié)點是否為空念祭，如果不空，則繼續(xù)向右遞歸前序查找
if(this.right != null) {
resNode = this.right.preOrderSearch(no);
}
return resNode;
}
//中序遍歷查找
public HeroNode infixOrderSearch(int no) {
//判斷當(dāng)前結(jié)點的左子節(jié)點是否為空绷蹲，如果不為空棒卷，則遞歸中序查找
HeroNode resNode = null;
if(this.left != null) {
resNode = this.left.infixOrderSearch(no);
}
if(resNode != null) {
return resNode;
}
System.out.println("進入中序查找");
//如果找到，則返回祝钢，如果沒有找到比规，就和當(dāng)前結(jié)點比較，如果是則返回當(dāng)前結(jié)點
if(this.no == no) {
return this;
}
//否則繼續(xù)進行右遞歸的中序查找
if(this.right != null) {
resNode = this.right.infixOrderSearch(no);
}
return resNode;
}
//后序遍歷查找
public HeroNode postOrderSearch(int no) {
//判斷當(dāng)前結(jié)點的左子節(jié)點是否為空拦英，如果不為空蜒什，則遞歸后序查找
HeroNode resNode = null;
if(this.left != null) {
resNode = this.left.postOrderSearch(no);
}
if(resNode != null) {//說明在左子樹找到
return resNode;
}
//如果左子樹沒有找到，則向右子樹遞歸進行后序遍歷查找
if(this.right != null) {
resNode = this.right.postOrderSearch(no);
}
if(resNode != null) {
return resNode;
}
System.out.println("進入后序查找");
//如果左右子樹都沒有找到疤估，就比較當(dāng)前結(jié)點是不是
if(this.no == no) {
return this;
}
return resNode;
}
}
二叉樹-結(jié)點刪除
1灾常、規(guī)定：
- 如果刪除的是葉子結(jié)點霎冯，則直接刪除該節(jié)點
- 如果刪除的非葉子結(jié)點，則刪除該節(jié)點樹
思路：
- 首先處理：判斷是否為空樹钞瀑，如果只有root一個節(jié)點沈撞，等價于二叉樹置空
- 通過遞歸方式，進行遍歷雕什，判斷是該節(jié)點的子節(jié)點是否為需要刪除的節(jié)點缠俺，如果是，則this.left=null;返回遞歸贷岸，或者this.right=null壹士；結(jié)束遞歸。
規(guī)定：
- 如果葉子節(jié)點偿警，直接刪除躏救。
- 如果非葉子節(jié)點，僅僅刪除該節(jié)點螟蒸，然后找到左子樹最右邊葉子結(jié)點盒使，替補該節(jié)點，或者找右子樹尿庐，最左葉子結(jié)點忠怖，替代要刪除的節(jié)點呢堰。
思路：
- 首先處理：判斷是否為空樹抄瑟，如果只有root一個節(jié)點，等價于二叉樹置空
- 通過遍歷（可以遞歸枉疼，也可以不遞歸）皮假，查找到需要刪除的節(jié)點
- 查找刪除節(jié)點的右子樹的最左葉子結(jié)點，或者左子樹的最右葉子結(jié)點
順序存儲二叉樹
概念：
- 基本說明：從數(shù)據(jù)結(jié)構(gòu)看骂维，數(shù)組存儲方式和樹的存儲方式可以互換惹资，即數(shù)組可以轉(zhuǎn)換成樹，樹也可以轉(zhuǎn)換為數(shù)組
要求：
- 以數(shù)組方式存儲樹
- 遍歷數(shù)組的時候航闺，仍然可以用一起的前序褪测，中序，后序方式完成結(jié)點遍歷
順序存儲二叉樹特點：
- 順序二叉樹通常只考慮二叉樹
- 第n個元素的左子節(jié)點為2*n+1
- 第n個元素的右子節(jié)點為2*n+2
- 第n個元素的父節(jié)點為（n-1）/2
- n：表示二叉樹中的第幾個元素（按0開始編號）
代碼實現(xiàn)：
//編寫一個ArrayBinary'Tree,實現(xiàn)順序存儲二叉樹遍歷
class ArrBinaryTree
{
private int[r: ;
//存儲數(shù)據(jù)結(jié)點的數(shù)組
public ArBinaryTree(int[] arr)
{
this.arr = arr;
}
//重載preOrder
public void preOrder()
{
this.preOrder(0);
}
// 編寫一個方法潦刃， 完成順序存儲二叉樹的前序遍歷
/**
* @param index數(shù)組的下標(biāo)
*/
public void preOrder(int index)
{
//如果數(shù)組為空侮措，或者ar.length= 0
if(arr = null II arr.length == 0)
{
System.out.printn("數(shù)組為空，不能按照二叉樹的前
//輸出當(dāng)前這個元素
Sytem.out.printlnfarr[index);
//向左遞歸遍歷
if(index * 2 + 1) < arr.length)
{
preOrder(2 * index + 1);
//向右遞歸遍歷
if(index * 2 + 2) < ar.length)
{
preOrder(2 * index + 2);
}
}
}
}
備注：八大排序算法中的堆排序乖杠，就會使用到順序儲存二叉樹
線索二叉樹
哈弗曼樹
- 給定n個權(quán)值分扎，最為n個葉子節(jié)點，構(gòu)造一個二叉樹胧洒，如果該樹的代權(quán)路徑長度（wpl）達(dá)到最小畏吓，稱這個二叉樹為最優(yōu)二叉樹墨状，也稱哈弗曼樹。
- 哈弗曼樹代權(quán)路徑最短的樹菲饼，權(quán)值較大肾砂，離節(jié)點較近。
代碼實現(xiàn)：
package dataConstruct;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
/**
* 哈夫曼樹和哈夫曼編碼宏悦， 1通今、哈夫曼樹的構(gòu)造 2、哈夫曼編碼壓縮和解壓
*
* @author zhanbei
*
*/
public class Huffman {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {1,2,3,5,69,8,7,4};
print(initHaffuMan(arr));
=
private static void print(TreeNode root) {
if (root == null) {
System.out.println("haffuMan樹為空肛根！");
}
// 前序遍歷
System.out.println("輸出最大節(jié)點辫塌，父節(jié)點--"+root.value);
}
/**
* 哈弗曼樹構(gòu)造
*/
private static TreeNode initHaffuMan(int[] arr) {
if (arr.length <= 0) {
System.out.println("數(shù)組為空，不可建立haffuman樹");
return null;
}
List<TreeNode> treeNodes = new ArrayList<TreeNode>(arr.length);
for (int i = 0; i < arr.length; i++) {
treeNodes.add(new TreeNode(arr[i]));
}
return createHaffuMan(treeNodes);
}
private static TreeNode createHaffuMan(List<TreeNode> treeNodes) {
System.out.println(treeNodes.size());
while (treeNodes.size() > 1) {
TreeNode treeNode = null;
Collections.sort(treeNodes);
TreeNode left = treeNodes.get(0);
TreeNode right = treeNodes.get(1);
treeNode = new TreeNode(treeNodes.get(0).value + treeNodes.get(1).value);
treeNode.left = left ;
treeNode.right = right ;
treeNodes.remove(left);
treeNodes.remove(right);
treeNodes.add(treeNode);
}
return treeNodes.get(0);
}
}
class TreeNode implements Comparable<TreeNode> {
int value;
TreeNode right;
TreeNode left;
public TreeNode(int value) {
this.value = value;
right = null;
left = null;
// TODO Auto-generated constructor stub
}
@Override
public int compareTo(TreeNode arg0) {
// TODO Auto-generated method stub
return arg0.value - value;
}
}
