一秕硝、常見的排序算法
基本思想：
1远豺、冒泡排序:兩兩比較相鄰數(shù)據(jù)，逆序則交換惊来，如果有一趟沒有發(fā)生交換棺滞，說明排序完成内狸。
2昆淡、簡單選擇排序：每一趟（第i趟）通過n-i次數(shù)據(jù)比較昂灵，從n-i+1個(gè)數(shù)據(jù)中選擇最小的數(shù)據(jù)作為第i個(gè)數(shù)據(jù)舞萄。一共排n次。
3撑螺、直接插入排序：將待排序的數(shù)據(jù)分成有序序列和無序序列的兩部分崎弃，每次從無序序列取一個(gè)數(shù)據(jù)插入到已經(jīng)排好的有序序列中，直到無序序列中沒有數(shù)據(jù)线婚。
4盆均、希爾排序：先將整個(gè)待排序列分割成若干子序列分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行直接插入排序游沿，待整個(gè)序列中的數(shù)據(jù)基本有序時(shí)诀黍，再對全體序列進(jìn)行一次直接插入排序（增量為1）唇敞。
5、堆排序:將待排序數(shù)據(jù)構(gòu)造成一個(gè)大頂堆咒精。此時(shí)旷档，整個(gè)序列的最大值就是堆頂?shù)母Y(jié)點(diǎn)。將它與序列末尾元素交換范咨，然后將剩余n-1個(gè)數(shù)據(jù)重新構(gòu)造一個(gè)堆，這樣就會得到n個(gè)元素中的次小值渠啊，如此反復(fù)執(zhí)行，直到排序完成贯溅。
6它浅、歸并排序:假設(shè)初始序列有n個(gè)數(shù)據(jù)镣煮，可以看作n個(gè)有序的子序列，每個(gè)子序列長度為1镊折，首先進(jìn)行兩兩歸并蚓聘，然后四四歸并，然后八八歸并，一直下去侣签，直至得到一個(gè)長度為n的有序序列為止。
7蹦肴、快速排序：通過一趟排序?qū)⑿蛄袆澐殖蓛刹糠忠趸希渲幸徊糠炙袛?shù)據(jù)都小于另一部分的數(shù)據(jù)卷中，再按照此方法繼續(xù)對這兩部分分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行议忽，直到變成有序序列十减。
優(yōu)缺點(diǎn)比較：
1愤估、快排的效率最高玩焰。但其缺點(diǎn)十分明顯：在待排序列基本有序的情況下芍锚，會退化成冒泡排序，時(shí)間復(fù)雜度接近 O(N^2)蒿赢。
2羡棵、希爾排序?qū)υ隽康倪x擇標(biāo)準(zhǔn)仍然沒有較為滿意的答案嗅钻，而增量的選取直接影響排序的效率；
3秃流、在數(shù)據(jù)規(guī)模較大時(shí)柳弄，歸并排序比希爾排序、堆排序速度更快嚣伐；
4萍丐、堆排序在數(shù)據(jù)規(guī)模較小的情況下速度較快逝变，但是隨著規(guī)模的增大，時(shí)間代價(jià)也開始和希爾和歸并兩種排序拉開距離拱层。
適用條件：
(1) n較小态贤，待排序列基本有序時(shí)，選擇直接插入排序或冒泡排序箱吕；
(2)n較小，對穩(wěn)定性沒要求時(shí)兆旬，用選擇排序丽猬；
(3)n較大熏瞄，待排序列隨機(jī)分布，對穩(wěn)定性沒要求時(shí)由桌，用快速排序邮丰；
(4)n較大，待排序列基本有序娃循，對穩(wěn)定性有要求時(shí)斗蒋，在空間允許的情況下，用歸并排序骤星；
(5)n較大爆哑，待排序列基本有序揭朝，對穩(wěn)定性沒要求時(shí)潭袱，用堆排序锋恬；
(6)海量級別的數(shù)據(jù)，必須按塊存放在外存(磁盤)中彤悔，用歸并排序；抑片；
(7)若待排序的記錄的關(guān)鍵字在一個(gè)明顯有限范圍內(nèi)時(shí),且空間允許是用桶排序杨赤。
上面的排序算法，當(dāng)記錄的規(guī)模較大時(shí)植捎，為避免耗費(fèi)大量的時(shí)間去移動記錄阳柔，可以用鏈表作為存儲結(jié)構(gòu)。譬如插入排序医咨、歸并排序拟淮、基數(shù)排序都易于在鏈表上實(shí)現(xiàn)谴忧，使之減少記錄的移動次數(shù)。但有的排序方法委造，如快速排序和堆排序均驶，在鏈表上卻難于實(shí)現(xiàn)，在這種情況下爬虱，可以提取關(guān)鍵字建立索引表跑筝，然后對索引表進(jìn)行排序瞒滴。
二、查找算法性能總結(jié)
三虏两、解釋平衡二叉樹，以及在數(shù)據(jù)結(jié)構(gòu)中的應(yīng)用（紅黑樹）
Q1：平衡二叉樹是一種二叉排序樹忘瓦，其中每個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差至多等于1.
Q2：可以用于查找數(shù)據(jù)引颈，時(shí)間復(fù)雜度為O(logN)。但是蝙场，由于插入或者刪除一個(gè)節(jié)點(diǎn)需要掃描兩趟樹，一次需要尋找插入點(diǎn)罚拟，一次需要向上平衡樹赐俗，效率不高（不如紅黑樹效率高）。
補(bǔ)充：
AVL樹阻逮，平衡二叉樹秩彤。適合增刪少，查找多的場景瓜富。
紅黑樹降盹，近似的平衡二叉樹，能夠以O(shè)(log2 n)的時(shí)間復(fù)雜度進(jìn)行搜索仅胞、插入剑辫、刪除操作妹蔽。此外，由于它的設(shè)計(jì)编整，任何不平衡都會在三次旋轉(zhuǎn)之內(nèi)解決乳丰。適合插入刪除次數(shù)多，查找次數(shù)也多的場景汞斧。
在數(shù)據(jù)結(jié)構(gòu)中的應(yīng)用：java中的TreeMap和TreeSet
1）插入刪除查找效率高：能夠以O(shè)(log2 N) 的時(shí)間復(fù)雜度進(jìn)行搜索什燕、插入、刪除操作
2）有序：TreeMap 中的所有元素總是按 key 根據(jù)指定排序規(guī)則保持有序狀態(tài)庙睡，TreeSet 中所有元素總是根據(jù)指定排序規(guī)則保持有序狀態(tài)（TreeSet 底層是通過 TreeMap 來實(shí)現(xiàn)的）乘陪。
B樹雕擂，B+樹：多路查找樹，一般用于磁盤存儲捂刺，分支多，層數(shù)少森缠，有效減少了磁盤的I/O操作次數(shù)贵涵，有效減少了數(shù)據(jù)查找的時(shí)間。
紅黑樹與AVL樹的比較
四宾茂、快排的時(shí)間復(fù)雜度和空間復(fù)雜度跨晴。
時(shí)間復(fù)雜度：
快速排序的平均時(shí)間復(fù)雜度也是：O(nlogn)片林。
最優(yōu)的情況下時(shí)間復(fù)雜度為：O( nlogn )怀骤。
最差的情況就是每一次取到的元素就是數(shù)組中最小/最大的蒋伦，這種情況其實(shí)就是冒泡排序了(每一次都排好一個(gè)元素的順序)焚鹊，時(shí)間復(fù)雜度為：O( n^2 )。
2)空間復(fù)雜度：
就地快速排序:O(1)
遞歸實(shí)現(xiàn)快速排序：
因?yàn)槊看芜f歸就要保持一些數(shù)據(jù)研叫；
最優(yōu)的情況下空間復(fù)雜度為：O(logn) 阻塑；每一次都平分?jǐn)?shù)組的情況
最差的情況下空間復(fù)雜度為：O( n )；退化為冒泡排序的情況渤昌。
