A. 基於關鍵字比較的排序演算法性能比較
三種排序的時間效率都是O(nlgn)，然而快排是平均O(nlgn)，而其他是最壞O(nlgn)。
針對隨機數據：
快排在隨機數據中是最快的，因為在隨機情況下，它的效率基本上是O(nlgn）。而因為它的代碼很緊湊，其省略的常數因子C很小，所以會快於歸並和堆排；
針對升序：
這是快排的最壞情況，為O(n^2)。而歸並和堆排都是O(nlgn)，具體差別在歸並的區間劃分上，如果劃分得好，組成一個平衡二叉樹，兩者時間就是接近的。並且堆排這時候不需要執行建堆過程，速度會快一些。而歸並並不是就地排序，因此在空間消耗上，堆排更優；
針對降序：
情況和升序是一樣的。
針對待定區間：
沒怎麼看懂題，實在是不好意思……
B. 比對演算法總結(二)——基於BWT索引結構的比對演算法-Bowite1
這是美國馬里蘭大學計算機研究所、生物信息學和計算生物學中心於2009年發表在《Genome Biology》雜志的一篇經典文章，至此以後依賴於BWT索引的比對演算法成為主流。 Bowite 是一款超快速、內存佔用低的短序列比對軟體，適用於將短reads比對至大型參考基因組。採用Burrows-Wheeler 演算法建立索引的Bowite軟體可以在1 CPU時內，將2000萬條reads 比對至人參考基因組，且內存只佔有1.3Gb。於此同時Bowite 採用了新的quality-aware backtracking（質量回溯）演算法，比對過程允許錯配。
在此之前都是採用對reads (SHRiMP, Maq, RMAP,ZOOM) 或者參考基因組 (SOAP)構建哈希表的演算法進行序列比對，該演算法已在上篇文章中進行了介紹 https://www.jianshu.com/p/f5ccff73b181 。
Bowite 採用了一種完全新的索引構建策略，適用於哺乳動物重測序。根據千人基因組計劃數據，Bowite 在35bp PE 序列上的比對速度要比Maq 軟體快35 倍，比SOAP軟體快300倍。Bowite 採用 Burrows-Wheeler 演算法對 full-text minute-space (FM) 構建索引，人參考基因組佔用的內存為1.3 GB。
為了追求速度，Bowite 針對哺乳動物重測序項目進行了很多合理的折中。例如，如果一條reads有多條最優匹配，Bowite 只會輸出一條最優匹配。當輸出的最優匹配也不是完全匹配時，Bowite並不能保證在所有情況下都能輸出最高質量的匹配。在設定了較高的匹配閾值時，一小部分含有多個錯配的reads可能會比對失敗。在默認參數條件下，Bowite 的靈敏度與SOAP 相當，略低於Maq。可以在命令行手動改變參數，在犧牲更多時間的情況下，增加靈敏度，給出reads所有可能的比對結果。目前Bowite 比對的reads長度范圍為4bp - 1024bp。
Bowite 對參考基因組建立索引的方法是 Burrows-Wheeler transform (BWT) 和 FM index。Bowite 建立的人類基因組索引在硬碟上的大小為2.2GB，在比對時的內存為1.3GB。FM index 常用的精確查找方法為 Ferragina 和 Manzini 演算法。Bowite 沒有完全使用該演算法，因為該演算法不允許錯配，不能比對含有測序錯誤和變異的reads。針對這種情況，Bowite引入了新的擴展演算法：quality-aware backtracking 演算法，允許錯配並支持高質量比對；double indexing 策略，避免過度回溯；Bowite比對策略與Maq軟體相似，允許小部分的高質量reads 含有錯配，並且對所有的錯配位點的質量值設置了上限閾值。
BWT 轉換是字元串的可逆性排列，它最早應用於文本數據的壓縮，依賴BWT建立的索引，可以在較低內存下，實現大型文本的有效搜索。它被在生物信息學中有廣泛的應用，包括重復區域計數、全基因組比對、微陣列探針設計、Smith-Waterman 比對到人參考基因組。Burrows-Wheeler transform (BWT) 的轉換步驟如圖1所示：
1、輪轉排序。如圖1a 所示，（1）將字元$ 添加到文本 T （acaacg）的末尾，但需注意其中字元$ 並未實際添加到文本 T 中，且其在字母表中邏輯順序小於 T 中所有出現過的字元。（2） 然後將當前字元串的第一個字元移到最後一位，形成一個新的字元串，再將新的字元串的第一位移到最後一位形成另一個新的字元串，就這樣不斷循環這個過程，直到字元串循環完畢（即$處於第一位）,這樣就形成了一個基於原字元串的字元矩陣M（這一步原圖1a 進行了省略，見下方小圖）。（3） 然後對矩陣M的各行字元按照字典先後順序排序，獲得排序後的字元矩陣 BWM（T），矩陣的最後一列定義為 BWT（T）。 前期經過一個小復雜的過程獲得了BWT（T）列，那這一列到底有什麼用呢？其實BWT（T）列通過簡單的演算法就可以推算出原始文本T的所有信息。而經過轉換之後的BWT（T）列大量重復字元是靠近的，只儲存該列信息，可以大大提高字元壓縮比例。
2、LF-Mapping。圖1a 轉換矩陣 BWM（T）含有一種 'last first (LF) mapping' 的特性，即最後一列L中出現某字元出現的順序與第一列F某字元出現的次序時一致的。根據Supplementary1 圖中演算法1 STEPLEFT 和 演算法2 UNPERMUTE 就可以推算出BWT（T）到 T 的過程， 圖1 b記錄了整個推算過程。 詳細推算過程可參考這個博客介紹： https://blog.csdn.net/stormlovetao/article/details/7048481 。
3、reads精確匹配。使用BWT演算法的最終目的是要將短reads比對到參考基因組上，確定短reads在參考基因組上的具體位置。轉換後的BWT（T）序列，可以利用Supplementary1 圖中演算法3 EXACTMATCH 實現reads的精確匹配。圖1c 列出了 字元串 aac 比對至acaacg 的過程 。 詳細推算過程可參考這篇介紹： https://zhuanlan.hu.com/p/158901556 。
上述的BWT轉換只能用於精確的匹配，但是測序reads是含有測序錯誤和突變的，精確匹配並不適用。這里應用了 backtracking 搜索的演算法，用於允許錯配快速比對 。含有錯配的reads只是一小部分。測序reads的每個鹼基都含有唯一的測序量值，測序質量值越該位點是測序錯誤的可能越大，只有當一條read 的所有錯配的測序質量值總和小於一定閾值時可以允許錯誤匹配。
圖2顯示了精確匹配和非精確匹配的過程，backtracking 搜索過程類似於 EXACTMATCH ，首先計算連續較長的後綴矩陣。如果矩陣中沒有搜索到相應的reads，則演算法會選擇一個已經匹配的查詢位置，替換一個不同鹼基，再次進行匹配。EXACTMATCH搜索從被替換位置之後開始，這樣就可以比對就可以允許一定的錯配。backtracking 過程發生在堆棧結構的上下文中，當有替換產生時，堆棧的結構會增長；當所有結果都不匹配時，堆棧結構會收縮。
Bowite 軟體的搜索演算法是比較貪婪的，Bowite軟體會報出遇到的第一個有效比對，並不一定是在錯配數目和變異質量上的「最佳比對」。沒有查詢最優比對的原因是尋找「最佳比對」會比現有的模型慢2-3倍。而在重測序項目上，速度是更重要的因素。Bowite 也設置了可以輸出多個比對位置（-k）和所有比對位置（-a）的參數，添加這些參數後，比對速度會顯著變慢。
目前的比對軟體會有過度回溯的情況，在reads的3『端花費大量無用時間去回溯。Bowite利用『double indexing』技術減少了過度回溯的發生。簡單來說就是對正向參考基因組進行BWT轉換，稱為 『Forward index』，同時對反向（注意不是互補配對序列,是反向序列）參考基因組也進行BWT轉換，稱為『Mirror index』。 當只允許一個錯配時，比對根據reads是前半段出現錯配，還是後半段出現錯配會有兩種情況：（1）Phase1 將Forward index 載入入內存，不允許查詢reads右半段出現錯配；（2）Phase2 將Mirror index 載入如內存，不允許查詢序列的反向reads右半段（原查詢序列的左半端） 出現錯配。這樣可以避免過度回溯，提高比比對的靈敏度。 但是，如果比對軟體允許一個reads有多個錯配時，仍然會有過度回溯的現象發生，為了減少過度回溯現象的發生，這里將回溯的上限進行了限定（默認值為：125次）。
Bowite 允許使用者在高質量reads的末端（默認是28bp）設置錯配數目（默認的錯配數目是2）。高質量reads末端的28bp序列被稱為 '種子' 序列。這個『種子』序列又可分為兩等份：14bp的高質量末端稱為 『hi-half』（通常位於5『端）,14bp的低質量末端稱為『lo-half』。 如果種子序列只允許2bp 的錯配，比對會出現4 種情況：（1）種子序列中沒有錯配(case1)；（2）hi-half區域沒有錯配，lo-half區域有一個或兩個錯配（case2）;（3）lo-half區域沒有錯配，hi-half區域有一個或兩個錯配（case3）;（4）lo-half區域有一個錯配，hi-half區域有一個錯配（case4）；
在所有情況下，reads的非種子部分允許任意數目的錯配。如圖3所示，Bowite 演算法會根據上面4 種情況交替變化『Forward index』和『Mirror index』比對策略，主要會有三種比對策略。
Bowite 建立一次參考基因組索引後，後續的比對可反復使用該索引。表1和表2列出了在默認參數條件下，Bowite、SOAP、Maq軟體性能的比較。在reads比對率相近的條件下，Bowite軟體的比對速度速度相對於SOAP、Maq軟體有較大的提升。
1、將reads 比對至人參考基因組上，Bowite相對於SOAP和Maq軟體有較大的優勢。它運行的內存非常小（1.2GB），在相同靈敏度下，速度有了較大的提升。
2、Bowite 軟體建立一次參考基因組索引後，後續的比對可反復使用該索引。
3、Bowite 速度快、內存佔用小、靈敏度高主要是因為使用了BWT演算法構建索引、利用回溯演算法允許錯配、採用Double index策略避免過度回溯。
4、Bowite 軟體目前並不支持插入、缺失比對，這個是今後需要努力的方向。
[1] Langmead B . Ultrafast and memory-efficient alignment of short DNA sequences to the human genome[J]. Genome biology, 2009, 10(3):R25.
[2] BWT 推算過程參考博客 https://blog.csdn.net/stormlovetao/article/details/7048481
[3] FM index 精確查匹配過程參考文章 https://zhuanlan.hu.com/p/158901556
C. 基於比較的排序演算法
基於比較的排序演算法，應該是最符合人們直覺的方法。在各種演算法的技術書上，已經證明了基於比較的排序演算法的時間最優復雜度為O(nlogn)。
下面是幾種常見的基於比較的排序演算法：
1. 選擇排序：這應該是最直觀的排序方法。在排序n個元素時，第一次遍歷，找到最小的元素，將其與第一個元素互換；第二次遍歷，找到次小的元素，將其與第二個元素交換；直至剩下最後一個元素。
2. 冒泡排序：這應該是我們學到的第一種排序演算法。基本思想就是，通過依次比較相鄰的兩個元素，如後值比前值小，則交換這兩個值，小值被交換到前面，大值被交換到後面。這樣一次遍歷後，最大值被放到最後。而小值被交換到n-1前。然後再次遍歷前n-1，n-2，直至最後2個元素。整個兒過程，小值隨著不斷的遍歷過程，逐漸被交換到前面，很像氣泡逐漸從水底逐漸冒出。所以被稱為冒泡演算法。
3. 插入排序：這個演算法的思想很直觀。按照《演算法導論》中的解釋，這個演算法可以參照我們平時打撲克的情形。當抓取一張牌的時候，按順序比較手牌，將其插入到恰當的位置。這樣保證了手中所有的牌依然有序。當已排序的值數量較多時，由於已經保證了有序，那麼在確定新值插入位置的時候，可以通過二分查找的方法來去確定插入位置。
4. 希爾排序：在冒泡演算法中，所以小值只能以步長為1的速度向前面移動。希爾排序在步長上作了優化，開始以一個較大的m步長進行分組，每組進行插入排序，這樣就實現了步長為m的移動。然後逐漸縮小步長m直至1。所以根本思想是盡可能的將元素移動較遠的位置代替移動一位。
5.歸並排序：該思想利用的是解決問題的一個常用思想，divide-and-conquer，即分而治之的思想。將n個元素每次2分，變為兩個n/2個元素組，直至1個元素——1個元素，自然是排好序了。然後，再兩兩合並元素組，最終合並為一個元素組。歸並演算法，因為需要歸並，所以必然需要一個額外的n空間來實現歸並。
6.快速排序：同樣是分而治之的思想，將原始數據分為2組。但是與歸並演算法直接將原始數據分為兩部分不同的是，快排選擇一個中值，新的兩個子組，一個子組所有的元素都小於中值，另外一個子組所有的元素都大於等於中值，直至元素個數為1。當元素個數為1時，實際上快排已經完成了排序。這點與歸並排序也不同，快排在子組完成以後，無需額外的操作。很明顯，快排的效率依賴於中值的選擇。如果中值可以將數據分為兩個數量相等的子組，那麼效率則為最高的。快排無需額外的存儲空間，可以in-place進行排序。
7.堆排序：該思想是將原始元素視為一個平衡二叉樹。然後要求父節點必須大於子節點的規則，調整該平衡二叉樹。由於是平衡二叉樹，所以數據被完美的等分。這樣根節點即為最大值。這時，堆排序完成了最大值的選擇。為排序，則將根節點與最後一個子節點交換。此時，樹的規則被破壞，需要從根節點逐級verify規則。
D. 常用的數據排序演算法有哪些,各有什麼特點舉例結合一種排序演算法並應用數組進行數據排序。
排序簡介
排序是數據處理中經常使用的一種重要運算,在計算機及其應用系統中,花費在排序上的時間在系統運行時間中佔有很大比重;並且排序本身對推動演算法分析的發展也起很大作用。目前已有上百種排序方法，但尚未有一個最理想的盡如人意的方法，本章介紹常用的如下排序方法，並對它們進行分析和比較。
1、插入排序（直接插入排序、折半插入排序、希爾排序）；
2、交換排序（起泡排序、快速排序）；
3、選擇排序（直接選擇排序、堆排序）；
4、歸並排序；
5、基數排序；
學習重點
1、掌握排序的基本概念和各種排序方法的特點，並能加以靈活應用；
2、掌握插入排序(直接插入排序、折半插入排序、希爾排序)、交換排序（起泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、二路歸並排序的方法及其性能分析方法；
3、了解基數排序方法及其性能分析方法。
排序（sort）或分類
所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。其確切定義如下：
輸入：n個記錄R1，R2，…，Rn，其相應的關鍵字分別為K1，K2，…，Kn。
輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
1．被排序對象--文件
被排序的對象--文件由一組記錄組成。
記錄則由若干個數據項(或域)組成。其中有一項可用來標識一個記錄，稱為關鍵字項。該數據項的值稱為關鍵字(Key)。
注意：
在不易產生混淆時，將關鍵字項簡稱為關鍵字。
2．排序運算的依據--關鍵字
用來作排序運算依據的關鍵字，可以是數字類型，也可以是字元類型。
關鍵字的選取應根據問題的要求而定。
【例】在高考成績統計中將每個考生作為一個記錄。每條記錄包含准考證號、姓名、各科的分數和總分數等項內容。若要惟一地標識一個考生的記錄，則必須用"准考證號"作為關鍵字。若要按照考生的總分數排名次，則需用"總分數"作為關鍵字。
排序的穩定性
當待排序記錄的關鍵字均不相同時，排序結果是惟一的，否則排序結果不唯一。
在待排序的文件中，若存在多個關鍵字相同的記錄，經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩定的；若具有相同關鍵字的記錄之間的相對次序發生變化，則稱這種排序方法是不穩定的。
注意：
排序演算法的穩定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得演算法不滿足穩定性要求，則該排序演算法就是不穩定的。
排序方法的分類
1．按是否涉及數據的內、外存交換分
在排序過程中，若整個文件都是放在內存中處理，排序時不涉及數據的內、外存交換，則稱之為內部排序(簡稱內排序)；反之，若排序過程中要進行數據的內、外存交換，則稱之為外部排序。
注意：
① 內排序適用於記錄個數不很多的小文件
② 外排序則適用於記錄個數太多，不能一次將其全部記錄放人內存的大文件。
2．按策略劃分內部排序方法
可以分為五類：插入排序、選擇排序、交換排序、歸並排序和分配排序。
排序演算法分析
1．排序演算法的基本操作
大多數排序演算法都有兩個基本的操作：
(1) 比較兩個關鍵字的大小；
(2) 改變指向記錄的指針或移動記錄本身。
注意：
第(2)種基本操作的實現依賴於待排序記錄的存儲方式。
2．待排文件的常用存儲方式
（1） 以順序表(或直接用向量)作為存儲結構
排序過程：對記錄本身進行物理重排（即通過關鍵字之間的比較判定，將記錄移到合適的位置）
（2） 以鏈表作為存儲結構
排序過程：無須移動記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈式)排序；
（3） 用順序的方式存儲待排序的記錄，但同時建立一個輔助表(如包括關鍵字和指向記錄位置的指針組成的索引表)
排序過程：只需對輔助表的表目進行物理重排（即只移動輔助表的表目，而不移動記錄本身）。適用於難於在鏈表上實現，仍需避免排序過程中移動記錄的排序方法。
3．排序演算法性能評價
（1） 評價排序演算法好壞的標准
評價排序演算法好壞的標准主要有兩條：
① 執行時間和所需的輔助空間
② 演算法本身的復雜程度
（2） 排序演算法的空間復雜度
若排序演算法所需的輔助空間並不依賴於問題的規模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。
非就地排序一般要求的輔助空間為O(n)。
（3） 排序演算法的時間開銷
大多數排序演算法的時間開銷主要是關鍵字之間的比較和記錄的移動。有的排序演算法其執行時間不僅依賴於問題的規模，還取決於輸入實例中數據的狀態。
文件的順序存儲結構表示
#define n l00 //假設的文件長度，即待排序的記錄數目
typedef int KeyType； //假設的關鍵字類型
typedef struct{ //記錄類型
KeyType key； //關鍵字項
InfoType otherinfo；//其它數據項，類型InfoType依賴於具體應用而定義
}RecType；
typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個單元一般用作哨兵
注意：
若關鍵字類型沒有比較算符，則可事先定義宏或函數來表示比較運算。
【例】關鍵字為字元串時，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那麼演算法中"a<b"可用"LT(a，b)"取代。若使用C++，則定義重載的算符"<"更為方便。
按平均時間將排序分為四類：
（1）平方階(O(n2))排序
一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；
（2）線性對數階(O(nlgn))排序
如快速、堆和歸並排序；
（3）O(n1+￡)階排序
￡是介於0和1之間的常數，即0<￡<1，如希爾排序；
（4）線性階(O(n))排序
如桶、箱和基數排序。
各種排序方法比較
簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。
影響排序效果的因素
因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法應綜合考慮下列因素：
①待排序的記錄數目n；
②記錄的大小(規模)；
③關鍵字的結構及其初始狀態；
④對穩定性的要求；
⑤語言工具的條件；
⑥存儲結構；
⑦時間和輔助空間復雜度等。
不同條件下，排序方法的選擇
(1)若n較小(如n≤50)，可採用直接插入或直接選擇排序。
當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少於直接插人，應選直接選擇排序為宜。
(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜；
(3)若n較大，則應採用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸並排序。
快速排序是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
堆排序所需的輔助空間少於快速排序，並且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。
若要求排序穩定，則可選用歸並排序。但本章介紹的從單個記錄起進行兩兩歸並的 排序演算法並不值得提倡，通常可以將它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子文件，然後再兩兩歸並之。因為直接插入排序是穩定的，所以改進後的歸並排序仍是穩定的。
4)在基於比較的排序方法中，每次比較兩個關鍵字的大小之後，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程。
當文件的n個關鍵字隨機分布時，任何藉助於"比較"的排序演算法，至少需要O(nlgn)的時間。
箱排序和基數排序只需一步就會引起m種可能的轉移，即把一個記錄裝入m個箱子之一，因此在一般情況下，箱排序和基數排序可能在O(n)時間內完成對n個記錄的排序。但是，箱排序和基數排序只適用於像字元串和整數這類有明顯結構特徵的關鍵字，而當關鍵字的取值范圍屬於某個無窮集合(例如實數型關鍵字)時，無法使用箱排序和基數排序，這時只有藉助於"比較"的方法來排序。
若n很大，記錄的關鍵字位數較少且可以分解時，採用基數排序較好。雖然桶排序對關鍵字的結構無要求，但它也只有在關鍵字是隨機分布時才能使平均時間達到線性階，否則為平方階。同時要注意，箱、桶、基數這三種分配排序均假定了關鍵字若為數字時，則其值均是非負的，否則將其映射到箱(桶)號時，又要增加相應的時間。
(5)有的語言(如Fortran，Cobol或Basic等)沒有提供指針及遞歸，導致實現歸並、快速(它們用遞歸實現較簡單)和基數(使用了指針)等排序演算法變得復雜。此時可考慮用其它排序。
(6)本章給出的排序演算法，輸人數據均是存儲在一個向量中。當記錄的規模較大時，為避免耗費大量的時間去移動記錄，可以用鏈表作為存儲結構。譬如插入排序、歸並排序、基數排序都易於在鏈表上實現，使之減少記錄的移動次數。但有的排序方法，如快速排序和堆排序，在鏈表上卻難於實現，在這種情況下，可以提取關鍵字建立索引表，然後對索引表進行排序。然而更為簡單的方法是：引人一個整型向量t作為輔助表，排序前令t[i]=i(0≤i<n)，若排序演算法中要求交換R[i]和R[j]，則只需交換t[i]和t[j]即可；排序結束後，向量t就指示了記錄之間的順序關系：
R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
若要求最終結果是：
R[0].key≤R[1].key≤…≤R[n-1].key
則可以在排序結束後，再按輔助表所規定的次序重排各記錄，完成這種重排的時間是O(n)。