迭代和遞歸的特點(diǎn)，并比較優(yōu)缺點(diǎn)：
（1）定義：
程序調(diào)用自身稱為遞歸。
利用變量的原值推出新值稱為迭代绅这。
（2）優(yōu)缺點(diǎn)
遞歸
優(yōu)點(diǎn)：大問題轉(zhuǎn)化為小問題糯累，可以減少代碼量算利，同時(shí)代碼精簡，可讀性好泳姐；
缺點(diǎn)：就是遞歸調(diào)用浪費(fèi)了空間效拭，而且遞歸太深容易造成堆棧的溢出。
迭代
優(yōu)點(diǎn)：代碼運(yùn)行效率好胖秒，因?yàn)闀r(shí)間只因循環(huán)次數(shù)增加而增加缎患，而且沒有額外的空間開銷；
缺點(diǎn)：代碼不如遞歸簡潔
排序算法
穩(wěn)定的排序方式：冒泡排序阎肝，歸并排序较锡，直接插入排序
快速排序：
思路：
1.從序列中挑出一個(gè)元素，作為"基準(zhǔn)"(pivot).
2.把所有比基準(zhǔn)值小的元素放在基準(zhǔn)前面盗痒，所有比基準(zhǔn)值大的元素放在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）蚂蕴，這個(gè)稱為分區(qū)(partition)操作。
3.對每個(gè)分區(qū)遞歸地進(jìn)行步驟1~2俯邓，遞歸的結(jié)束條件是序列的大小是0或1骡楼，這時(shí)整體已經(jīng)被排好序了。
intPartition(intA[],int left, int right)// 劃分函數(shù){
int pivot = A[right];// 這里每次都選擇最后一個(gè)元素作為基準(zhǔn)
int tail = left -1; // tail為小于基準(zhǔn)的子數(shù)組最后一個(gè)元素的索引
for(int i = left; i < right; i++)// 遍歷基準(zhǔn)以外的其他元素? ? {
? ? ? ? if(A[i] <= pivot)// 把小于等于基準(zhǔn)的元素放到前一個(gè)子數(shù)組末尾? ? ? ? {
? ? ? ? ? ? Swap(A, ++tail, i);
? ? ? ? }
? ? }
? ? Swap(A, tail +1, right);// 最后把基準(zhǔn)放到前一個(gè)子數(shù)組的后邊稽鞭，剩下的子數(shù)組既是大于基準(zhǔn)的子數(shù)組
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 該操作很有可能把后面元素的穩(wěn)定性打亂鸟整，所以快速排序是不穩(wěn)定的排序算法returntail +1;// 返回基準(zhǔn)的索引}
voidQuickSort(intA[],int left, int right)
{
? ? if(left >= right)
? ? ? ? return;
?int pivot_index = Partition(A, left, right);// 基準(zhǔn)的索引
QuickSort(A, left, pivot_index -1);
QuickSort(A, pivot_index +1, right);
}
堆排序：
思路：父節(jié)點(diǎn)的值大于它子節(jié)點(diǎn)的值
1.由輸入的無序數(shù)組構(gòu)造一個(gè)最大堆，作為初始的無序區(qū)
2.把堆頂元素（最大值）和堆尾元素互換
3.把堆（無序區(qū)）的尺寸縮小1朦蕴，并調(diào)用heapify(A, 0)從新的堆頂元素開始進(jìn)行堆調(diào)整
4.重復(fù)步驟2篮条，直到堆的尺寸為1
void Heapify(intA[],int i, int size)// 從A[i]向下進(jìn)行堆調(diào)整{
? ? int left_child =2* i +1;// 左孩子索引
????int right_child =2* i +2;// 右孩子索引
? ?int max = i;// 選出當(dāng)前結(jié)點(diǎn)與其左右孩子三者之中的最大值if(left_child < size && A[left_child] > A[max])
? ? ? ? max = left_child;
? ? if(right_child < size && A[right_child] > A[max])
? ? ? ? max = right_child;
? ? if(max != i)
? ? {
? ? ? ? Swap(A, i, max);? ? ? ? ? ? ? ? // 把當(dāng)前結(jié)點(diǎn)和它的最大(直接)子節(jié)點(diǎn)進(jìn)行交換
Heapify(A, max, size);// 遞歸調(diào)用弟头，繼續(xù)從當(dāng)前結(jié)點(diǎn)向下進(jìn)行堆調(diào)整? ? }
}intBuildHeap(intA[],int n)// 建堆，時(shí)間復(fù)雜度O(n){
? ? int heap_size = n;
? ? for(int i = heap_size /2-1; i >=0; i--)// 從每一個(gè)非葉結(jié)點(diǎn)開始向下進(jìn)行堆調(diào)整? ? ? ?
?????Heapify(A, i, heap_size);
? ? return heap_size;
}voidHeapSort(intA[],int n)
{
? ? int heap_size = BuildHeap(A, n);// 建立一個(gè)最大堆while(heap_size >1)// 堆（無序區(qū)）元素個(gè)數(shù)大于1涉茧，未完成排序? ? {
? ? ? ? // 將堆頂元素與堆的最后一個(gè)元素互換赴恨，并從堆中去掉最后一個(gè)元素
? ? ? ? // 此處交換操作很有可能把后面元素的穩(wěn)定性打亂，所以堆排序是不穩(wěn)定的排序算法
Swap(A,0, --heap_size);
? ? ? ? Heapify(A, 0, heap_size);// 從新的堆頂元素開始向下進(jìn)行堆調(diào)整伴栓，時(shí)間復(fù)雜度O(logn)? ? }
}
歸并排序：
思路：1452排序
先把1452分開伦连，變?yōu)? 4 5 2，第一次結(jié)果為14钳垮，25惑淳，第二次排序結(jié)果為1245.遞歸方式
void MergeSortRecursion(intA[],int left, int right)// 遞歸實(shí)現(xiàn)的歸并排序(自頂向下){
? ? if(left == right)// 當(dāng)待排序的序列長度為1時(shí)，遞歸開始回溯饺窿，進(jìn)行merge操作return;
? ? int mid = (left + right) /2;
? ? MergeSortRecursion(A, left, mid);
? ? MergeSortRecursion(A, mid +1, right);
? ? Merge(A, left, mid, right);
}
void Merge(intA[],int left, int mid, int right)// 合并兩個(gè)已排好序的數(shù)組A[left...mid]和A[mid+1...right]{
? ? int len = right - left +1;
? ? int*temp =ne wint[len];// 輔助空間O(n)int index =0;
? ? int i = left;// 前一數(shù)組的起始元素int j = mid +1;// 后一數(shù)組的起始元素while(i <= mid && j <= right)
? ? {
? ? ? ? temp[index++] = A[i] <= A[j] ? A[i++] : A[j++];// 帶等號保證歸并排序的穩(wěn)定性? ? }
? ? while(i <= mid)
? ? {
? ? ? ? temp[index++] = A[i++];
? ? }
? ? while(j <= right)
? ? {
? ? ? ? temp[index++] = A[j++];
? ? }
? ? for(int k =0; k < len; k++)
? ? {
? ? ? ? A[left++] = temp[k];
? ? }
}
單例模式：在內(nèi)部創(chuàng)建一個(gè)實(shí)例歧焦，構(gòu)造器全部設(shè)置為private，所有方法均在該實(shí)例上改動肚医，在創(chuàng)建上要注意類的實(shí)例化只能執(zhí)行一次绢馍，可以采用許多種方法來實(shí)現(xiàn)，如Synchronized關(guān)鍵字忍宋，或者利用內(nèi)部類等機(jī)制來實(shí)現(xiàn)痕貌。
較為優(yōu)良的雙重鎖機(jī)制：
public class Singleton {
? ? private volatile static Singleton singleton;?
? ? private Singleton (){}?
? ? public static Singleton getSingleton() {?
? ? if (singleton == null) {?
? ? ? ? synchronized (Singleton.class) {?
? ? ? ? if (singleton == null) {?
? ? ? ? ? ? singleton = new Singleton();?
? ? ? ? }?
? ? ? ? }?
? ? }?
? ? return singleton;?
? ? }? }
建造者模式：?1、需要生成的對象具有復(fù)雜的內(nèi)部結(jié)構(gòu)糠排。 2舵稠、需要生成的對象內(nèi)部屬性本身相互依賴。
使用：一些基本部件不會變入宦，而其組合經(jīng)常變化的時(shí)候哺徊。
適配器模式：使用場景為有動機(jī)地修改一個(gè)正常運(yùn)行的系統(tǒng)的接口，這時(shí)應(yīng)該考慮使用適配器模式乾闰。
適配器模式的作用就是在原來的類上提供新功能落追。主要可分為3種：
類適配：創(chuàng)建新類，繼承源類涯肩，并實(shí)現(xiàn)新接口轿钠，例如
class adapter extend soldClass implements newFunc{}
對象適配：創(chuàng)建新類持源類的實(shí)例，并實(shí)現(xiàn)新接口病苗，例如
class adapter implements newFunc {private old Class oldInstance ;}
接口適配：創(chuàng)建新的抽象類實(shí)現(xiàn)舊接口方法疗垛。例如
abstract class adapter implement soldClassFunc {void newFunc();}
工廠模式：主要解決：主要解決接口選擇的問題。何時(shí)使用：我們明確地計(jì)劃不同條件下創(chuàng)建不同實(shí)例時(shí)硫朦。
裝飾器模式：在不想增加很多子類的情況下擴(kuò)展類贷腕。允許向一個(gè)現(xiàn)有的對象添加新的功能，同時(shí)又不改變其結(jié)構(gòu)
interface Source{ void method();}
public class Decorator implements Source{
? ? private Source source ;
? ? public void decotate1(){
? ? ? ? System.out.println("decorate");
? ? }
? ? @Override
? ? public void method() {
? ? ? ? decotate1();
? ? ? ? source.method();
? ? }
}
觀察者模式：定義對象間的一種一對多的依賴關(guān)系，當(dāng)一個(gè)對象的狀態(tài)發(fā)生改變時(shí)泽裳，所有依賴于它的對象都得到通知并被自動更新瞒斩。
場景：一個(gè)對象（目標(biāo)對象）的狀態(tài)發(fā)生改變，所有的依賴對象（觀察者對象）都將得到通知涮总，進(jìn)行廣播通知胸囱。
