1. 排序是什么磷雇？

它是指將一串?dāng)?shù)據(jù)按照特定的順序進(jìn)行排序的一種方法

排序算法中經(jīng)常關(guān)注的兩個(gè)問(wèn)題是：

（1）排序算法的穩(wěn)定性，就是指原來(lái)相等的數(shù)字排序后它們之間的前后位置沒(méi)有發(fā)生改變子眶。

（2）排序算法的時(shí)間復(fù)雜度，也就是要遍歷多少次才能實(shí)現(xiàn)相應(yīng)地排序

2. 排序算法列舉

2.1 冒泡排序算法

冒泡排序（英語(yǔ)：Bubble Sort）是一種簡(jiǎn)單的排序算法男娄。它重復(fù)地遍歷要排序的數(shù)列毅往，一次比較兩個(gè)元素檩淋，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)芬为。遍歷數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換萄金，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端媚朦。

冒泡排序算法的過(guò)程：

（1）比較相鄰的兩個(gè)元素氧敢，如果第一個(gè)比第二個(gè)打，就交換它們询张。

最優(yōu)時(shí)間復(fù)雜度為O(n)（即數(shù)列一開(kāi)始就是排序好的）孙乖，最壞時(shí)間復(fù)雜度為O(n的平方)（必須遍歷完所以次數(shù)）， 穩(wěn)定性為穩(wěn)定

2.2 選擇排序

選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法份氧。它的工作原理如下唯袄。首先在未排序序列中找到最小（大）元素蜗帜，存放到排序序列的起始位置恋拷，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最刑薄（大）元素蔬顾，然后放到已排序序列的末尾。以此類(lèi)推湘捎，直到所有元素均排序完畢诀豁。

選擇排序算法的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上窥妇，則它不會(huì)被移動(dòng)舷胜。選擇排序每次交換一對(duì)元素，它們當(dāng)中至少有一個(gè)將被移到其最終位置上秩伞，因此對(duì)n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換逞带。在所有的完全依靠交換去移動(dòng)元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N纱新。

最優(yōu)時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度都為O(n的平方)，穩(wěn)定性：不穩(wěn)定

2.3 插入排序

插入排序（英語(yǔ)：Insertion Sort）是一種簡(jiǎn)單直觀的排序算法穆趴。它的工作原理是通過(guò)構(gòu)建有序序列脸爱，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描未妹，找到相應(yīng)位置并插入簿废。插入排序在實(shí)現(xiàn)上，在從后向前掃描過(guò)程中络它，需要反復(fù)把已排序元素逐步向后挪位族檬，為最新元素提供插入空間。

時(shí)間復(fù)雜度：最優(yōu)時(shí)間復(fù)雜度為O(n)化戳，最壞時(shí)間復(fù)雜度為O(n的平方), 穩(wěn)定性為穩(wěn)定

2.4 快速排序：

快速排序（英語(yǔ)：Quicksort）单料，又稱(chēng)劃分交換排序（partition-exchange sort）埋凯，通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小扫尖，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序白对，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列换怖。

步驟為：

從數(shù)列中挑出一個(gè)元素甩恼，稱(chēng)為"基準(zhǔn)"（pivot），

重新排序數(shù)列沉颂，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面条摸，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后铸屉，該基準(zhǔn)就處于數(shù)列的中間位置屈溉。這個(gè)稱(chēng)為分區(qū)（partition）操作。

遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序抬探。

遞歸的最底部情形子巾，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了小压。雖然一直遞歸下去线梗，但是這個(gè)算法總會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中怠益，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去仪搔。

最優(yōu)時(shí)間復(fù)雜度：O(nlogn)

最壞時(shí)間復(fù)雜度：O(n2)

穩(wěn)定性：不穩(wěn)定

從一開(kāi)始快速排序平均需要花費(fèi)O(n log n)時(shí)間的描述并不明顯。但是不難觀察到的是分區(qū)運(yùn)算蜻牢，數(shù)組的元素都會(huì)在每次循環(huán)中走訪過(guò)一次烤咧，使用O(n)的時(shí)間。在使用結(jié)合（concatenation）的版本中抢呆，這項(xiàng)運(yùn)算也是O(n)煮嫌。

在最好的情況，每次我們運(yùn)行一次分區(qū)抱虐，我們會(huì)把一個(gè)數(shù)列分為兩個(gè)幾近相等的片段昌阿。這個(gè)意思就是每次遞歸調(diào)用處理一半大小的數(shù)列。因此恳邀，在到達(dá)大小為一的數(shù)列前懦冰，我們只要作log n次嵌套的調(diào)用。這個(gè)意思就是調(diào)用樹(shù)的深度是O(log n)谣沸。但是在同一層次結(jié)構(gòu)的兩個(gè)程序調(diào)用中刷钢，不會(huì)處理到原來(lái)數(shù)列的相同部分；因此乳附，程序調(diào)用的每一層次結(jié)構(gòu)總共全部?jī)H需要O(n)的時(shí)間（每個(gè)調(diào)用有某些共同的額外耗費(fèi)内地，但是因?yàn)樵诿恳粚哟谓Y(jié)構(gòu)僅僅只有O(n)個(gè)調(diào)用伴澄，這些被歸納在O(n)系數(shù)中）。結(jié)果是這個(gè)算法僅需使用O(n log n)時(shí)間瓤鼻。

2.5 希爾排序

希爾排序(Shell Sort)是插入排序的一種秉版。也稱(chēng)縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本茬祷。希爾排序是非穩(wěn)定排序算法清焕。該方法因DL．Shell于1959年提出而得名。 希爾排序是把記錄按下標(biāo)的一定增量分組祭犯，對(duì)每組使用直接插入排序算法排序秸妥；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多沃粗，當(dāng)增量減至1時(shí)粥惧，整個(gè)文件恰被分成一組，算法便終止最盅。

2.6 歸并排序

歸并排序是采用分治法的一個(gè)非常典型的應(yīng)用突雪。歸并排序的思想就是先遞歸分解數(shù)組，再合并數(shù)組涡贱。

將數(shù)組分解最小之后咏删，然后合并兩個(gè)有序數(shù)組，基本思路是比較兩個(gè)數(shù)組的最前面的數(shù)问词，誰(shuí)小就先取誰(shuí)督函，取了后相應(yīng)的指針就往后移一位。然后再比較激挪，直至一個(gè)數(shù)組為空辰狡，最后把另一個(gè)數(shù)組的剩余部分復(fù)制過(guò)來(lái)即可。

2.7 堆排序

3 搜索算法

搜索是在一個(gè)項(xiàng)目集合中找到一個(gè)特定項(xiàng)目的算法過(guò)程垄分。搜索算法有 順序查找宛篇、二分查找、二叉樹(shù)查找锋喜、哈希查找

3.1 二分查找方法

二分查找又稱(chēng)折半查找些己，優(yōu)點(diǎn)是比較次數(shù)少，查找速度快嘿般，平均性能好；其缺點(diǎn)是要求待查表為有序表涯冠，且插入刪除困難炉奴。