排序演算法的缺陷

『壹』 數據結構中快速排序演算法的不足以及改進

一般快速排序演算法都是以最左元素作為劃分的基準值，這樣當數據元素本身已經完全有序（不管正序或者逆序）時，每一趟劃分只能將一個元素分割出來，其效率很低：時間復雜度O(n^2)，空間復雜度為O(n)
所以改進方法就是找尋合適的基準值，保證不至於在關鍵字有序或者接近有序時發生這個情況，一般可以使用三者取中（就是待劃分序列的頭元素、尾元素、中間元素三者的中間值）、或者隨機選擇等方法，這樣即使關鍵字完全有序，也可以保證時間復雜度O(nlogn)，空間復雜度O(logn)

『貳』 排序法的缺點有

排序的演算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小范圍內的排序演算法。

『叄』 如何看待Python/java的排序演算法被發現有潛在的bug

java和Python的默認排序演算法(TimSort)雖然在日常情況中運行良好,但在極端情況下會出現越界異常導致崩潰.這說明:

1. 以結果為導向的測試方法,雖然在普通情況下能夠方便,快速的測試程序。但是也存在特殊的情況，並且這些極端情況還很容易被忽視掉，然後造成一些bug和異常。

2. 2.形式化分析方法是有效的，可行的。在重點項目或者安全性要求高的項目中，盡可能的使用形式化分析方法。降低風險。
   

『肆』 各種排序演算法最好和最壞情況比較

都不知道怎麼回答，各種排序說的也太多了，這里講幾種簡單的吧，希望對你有幫助！
比如n個順序存儲元素進行排序，a[0]做「哨兵」（即a[0]不存數據，而是用作輔存空間使用）的情況
1 直接插入排序：比較次數 最少n-1次；最多(n-1)(n+2)/2
移動次數 最少0； 最多(n-1)(n+4)/2
使用一個輔助存儲空間，是穩定的排序；

2 折半插入排序：比較次數 最少與最多同，都是n*log2n（其中2為底，下邊表示同），
移動次數 最少0，最多時間復雜度為O(n2);(n的平方，以下也如此表示)；
使用一個輔助存儲空間，是穩定的排序；

3 冒泡排序： 比較最少為：n-1次，最多時間復雜度表示為o(n2);
移動次數最少為0，最多時間復雜度表示為O(n2);
使用一個輔存空間，是穩定的排序；

4 簡單選擇排序： 比較次數沒有多少之分，均是n(n-1)/2;
移動次數最少為0，最多為3(n-1);
使用一個輔存空間，是穩定的排序；

5 快速排序：比較和移動次數最少時間復雜度表示為O(n*log2n);
比較和移動次數最多的時間復雜度表示為O(n2);
使用的輔助存儲空間最少為log2n，最多為n的平方；是不穩定的排序；

6 堆排序： 比較和移動次數沒有好壞之分，都是O(n*log2n);
使用一個輔存空間，是不穩定的排序；

7 2-路歸並排序：比較和移動次數沒有好壞之分，都是O(n*log2n);
需要n個輔助存儲空間，是穩定的排序；

另外還有很多的排序方法如 希爾排序，基數排序，2-路插入排序 等等很多的排序方法，這里就不一一列舉了，希望列舉的對你有幫助！！

『伍』 搜索引擎的排序演算法都有哪些是怎麼實現的

2.1基於詞頻統計——詞位置加權的搜索引擎
利用關鍵詞在文檔中出現的頻率和位置排序是搜索引擎最早期排序的主要思想，其技術發展也最為成熟，是第一階段搜索引擎的主要排序技術，應用非常廣泛，至今仍是許多搜索引擎的核心排序技術。其基本原理是：關鍵詞在文檔中詞頻越高，出現的位置越重要，則被認為和檢索詞的相關性越好。
1）詞頻統計
文檔的詞頻是指查詢關鍵詞在文檔中出現的頻率。查詢關鍵詞詞頻在文檔中出現的頻率越高，其相關度越大。但當關鍵詞為常用詞時，使其對相關性判斷的意義非常小。TF/IDF很好的解決了這個問題。TF/IDF演算法被認為是信息檢索中最重要的發明。TF（Term Frequency）：單文本詞彙頻率，用關鍵詞的次數除以網頁的總字數，其商稱為「關鍵詞的頻率」。IDF（Inverse Document Frequency）：逆文本頻率指數，其原理是，一個關鍵詞在N個網頁中出現過，那麼N越大，此關鍵詞的權重越小，反之亦然。當關鍵詞為常用詞時，其權重極小，從而解決詞頻統計的缺陷。
2）詞位置加權
在搜索引擎中，主要針對網頁進行詞位置加權。所以，頁面版式信息的分析至關重要。通過對檢索關鍵詞在Web頁面中不同位置和版式，給予不同的權值，從而根據權值來確定所搜索結果與檢索關鍵詞相關程度。可以考慮的版式信息有：是否是標題，是否為關鍵詞，是否是正文，字體大小，是否加粗等等。同時，錨文本的信息也是非常重要的，它一般能精確的描述所指向的頁面的內容。
2.2基於鏈接分析排序的第二代搜索引擎
鏈接分析排序的思想起源於文獻引文索引機制，即論文被引用的次數越多或被越權威的論文引用，其論文就越有價值。鏈接分析排序的思路與其相似，網頁被別的網頁引用的次數越多或被越權威的網頁引用，其價值就越大。被別的網頁引用的次數越多，說明該網頁越受歡迎，被越權威的網頁引用，說明該網頁質量越高。鏈接分析排序演算法大體可以分為以下幾類：基於隨機漫遊模型的，比如PageRank和Repution演算法；基於概率模型的，如SALSA、PHITS；基於Hub和Authority相互加強模型的，如HITS及其變種；基於貝葉斯模型的，如貝葉斯演算法及其簡化版本。所有的演算法在實際應用中都結合傳統的內容分析技術進行了優化。本文主要介紹以下幾種經典排序演算法：
1）PageRank演算法
PageRank演算法由斯坦福大學博士研究生Sergey Brin和Lwraence Page等提出的。PageRank演算法是Google搜索引擎的核心排序演算法，是Google成為全球最成功的搜索引擎的重要因素之一，同時開啟了鏈接分析研究的熱潮。
PageRank演算法的基本思想是：頁面的重要程度用PageRank值來衡量，PageRank值主要體現在兩個方面：引用該頁面的頁面個數和引用該頁面的頁面重要程度。一個頁面P（A）被另一個頁面P（B）引用，可看成P（B）推薦P（A），P（B）將其重要程度（PageRank值）平均的分配P（B）所引用的所有頁面，所以越多頁面引用P（A），則越多的頁面分配PageRank值給P（A），PageRank值也就越高，P（A）越重要。另外，P(B)越重要，它所引用的頁面能分配到的PageRank值就越多，P（A）的PageRank值也就越高，也就越重要。
其計算公式為：

PR（A）：頁面A的PageRank值；
d：阻尼系數，由於某些頁面沒有入鏈接或者出鏈接，無法計算PageRank值，為避免這個問題（即LinkSink問題），而提出的。阻尼系數常指定為0.85。
R（Pi）：頁面Pi的PageRank值；
C（Pi）：頁面鏈出的鏈接數量；
PageRank值的計算初始值相同，為了不忽視被重要網頁鏈接的網頁也是重要的這一重要因素，需要反復迭代運算，據張映海撰文的計算結果，需要進行10次以上的迭代後鏈接評價值趨於穩定，如此經過多次迭代，系統的PR值達到收斂。
PageRank是一個與查詢無關的靜態演算法，因此所有網頁的PageRank值均可以通過離線計算獲得。這樣，減少了用戶檢索時需要的排序時間，極大地降低了查詢響應時間。但是PageRank存在兩個缺陷：首先PageRank演算法嚴重歧視新加入的網頁，因為新的網頁的出鏈接和入鏈接通常都很少，PageRank值非常低。另外PageRank演算法僅僅依靠外部鏈接數量和重要度來進行排名，而忽略了頁面的主題相關性，以至於一些主題不相關的網頁（如廣告頁面）獲得較大的PageRank值，從而影響了搜索結果的准確性。為此，各種主題相關演算法紛紛涌現，其中以以下幾種演算法最為典型。
2）Topic-Sensitive PageRank演算法
由於最初PageRank演算法中是沒有考慮主題相關因素的，斯坦福大學計算機科學系Taher Haveli-wala提出了一種主題敏感（Topic-Sensitive）的PageRank演算法解決了「主題漂流」問題。該演算法考慮到有些頁面在某些領域被認為是重要的，但並不表示它在其它領域也是重要的。
網頁A鏈接網頁B，可以看作網頁A對網頁B的評分，如果網頁A與網頁B屬於相同主題，則可認為A對B的評分更可靠。因為A與B可形象的看作是同行，同行對同行的了解往往比不是同行的要多，所以同行的評分往往比不是同行的評分可靠。遺憾的是TSPR並沒有利用主題的相關性來提高鏈接得分的准確性。
3）HillTop演算法
HillTop是Google的一個工程師Bharat在2001年獲得的專利。HillTop是一種查詢相關性鏈接分析演算法，克服了的PageRank的查詢無關性的缺點。HillTop演算法認為具有相同主題的相關文檔鏈接對於搜索者會有更大的價值。在Hilltop中僅考慮那些用於引導人們瀏覽資源的專家頁面（Export Sources）。Hilltop在收到一個查詢請求時，首先根據查詢的主題計算出一列相關性最強的專家頁面，然後根據指向目標頁面的非從屬專家頁面的數量和相關性來對目標頁面進行排序。
HillTop演算法確定網頁與搜索關鍵詞的匹配程度的基本排序過程取代了過分依靠PageRank的值去尋找那些權威頁面的方法，避免了許多想通過增加許多無效鏈接來提高網頁PageRank值的作弊方法。HillTop演算法通過不同等級的評分確保了評價結果對關鍵詞的相關性，通過不同位置的評分確保了主題（行業）的相關性，通過可區分短語數防止了關鍵詞的堆砌。
但是，專家頁面的搜索和確定對演算法起關鍵作用，專家頁面的質量對演算法的准確性起著決定性作用，也就忽略了大多數非專家頁面的影響。專家頁面在互聯網中占的比例非常低（1.79%），無法代表互聯網全部網頁，所以HillTop存在一定的局限性。同時，不同於PageRank演算法，HillTop演算法的運算是在線運行的，對系統的響應時間產生極大的壓力。
4）HITS
HITS（Hyperlink Inced Topic Search）演算法是Kleinberg在1998年提出的，是基於超鏈接分析排序演算法中另一個最著名的演算法之一。該演算法按照超鏈接的方向，將網頁分成兩種類型的頁面：Authority頁面和Hub頁面。Authority頁面又稱權威頁面，是指與某個查詢關鍵詞和組合最相近的頁面，Hub頁面又稱目錄頁，該頁面的內容主要是大量指向Authority頁面的鏈接，它的主要功能就是把這些Authority頁面聯合在一起。對於Authority頁面P，當指向P的Hub頁面越多，質量越高，P的Authority值就越大；而對於Hub頁面H，當H指向的Authority的頁面越多，Authority頁面質量越高，H的Hub值就越大。對整個Web集合而言，Authority和Hub是相互依賴、相互促進，相互加強的關系。Authority和Hub之間相互優化的關系，即為HITS演算法的基礎。
HITS基本思想是：演算法根據一個網頁的入度（指向此網頁的超鏈接）和出度（從此網頁指向別的網頁）來衡量網頁的重要性。在限定范圍之後根據網頁的出度和入度建立一個矩陣，通過矩陣的迭代運算和定義收斂的閾值不斷對兩個向量Authority和Hub值進行更新直至收斂。
實驗數據表明，HITS的排名准確性要比PageRank高，HITS演算法的設計符合網路用戶評價網路資源質量的普遍標准，因此能夠為用戶更好的利用網路信息檢索工具訪問互聯網資源帶來便利。
但卻存在以下缺陷：首先，HITS演算法只計算主特徵向量，處理不好主題漂移問題；其次，進行窄主題查詢時，可能產生主題泛化問題；第三，HITS演算法可以說一種實驗性質的嘗試。它必須在網路信息檢索系統進行面向內容的檢索操作之後，基於內容檢索的結果頁面及其直接相連的頁面之間的鏈接關系進行計算。盡管有人嘗試通過演算法改進和專門設立鏈接結構計算伺服器（Connectivity Server）等操作，可以實現一定程度的在線實時計算，但其計算代價仍然是不可接受的。
2.3基於智能化排序的第三代搜索引擎
排序演算法在搜索引擎中具有特別重要的地位，目前許多搜索引擎都在進一步研究新的排序方法，來提升用戶的滿意度。但目前第二代搜索引擎有著兩個不足之處，在此背景下，基於智能化排序的第三代搜索引擎也就應運而生。
1）相關性問題
相關性是指檢索詞和頁面的相關程度。由於語言復雜，僅僅通過鏈接分析及網頁的表面特徵來判斷檢索詞與頁面的相關性是片面的。例如：檢索「稻瘟病」，有網頁是介紹水稻病蟲害信息的，但文中沒有「稻瘟病」這個詞，搜索引擎根本無法檢索到。正是以上原因，造成大量的搜索引擎作弊現象無法解決。解決相關性的的方法應該是增加語意理解，分析檢索關鍵詞與網頁的相關程度，相關性分析越精準，用戶的搜索效果就會越好。同時，相關性低的網頁可以剔除，有效地防止搜索引擎作弊現象。檢索關鍵詞和網頁的相關性是在線運行的，會給系統相應時間很大的壓力，可以採用分布式體系結構可以提高系統規模和性能。
2）搜索結果的單一化問題
在搜索引擎上，任何人搜索同一個詞的結果都是一樣。這並不能滿足用戶的需求。不同的用戶對檢索的結果要求是不一樣的。例如：普通的農民檢索「稻瘟病」，只是想得到稻瘟病的相關信息以及防治方法，但農業專家或科技工作者可能會想得到稻瘟病相關的論文。
解決搜索結果單一的方法是提供個性化服務，實現智能搜索。通過Web數據挖掘，建立用戶模型（如用戶背景、興趣、行為、風格），提供個性化服務。

『陸』 數據結構的排序演算法中，哪些排序是穩定的，哪些排序是不穩定的

一、穩定排序演算法

1、冒泡排序

2、雞尾酒排序

3、插入排序

4、桶排序

5、計數排序

6、合並排序

7、基數排序

8、二叉排序樹排序

二、不穩定排序演算法

1、選擇排序

2、希爾排序

3、組合排序

4、堆排序

5、平滑排序

6、快速排序

排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。

一個排序演算法是穩定的，就是當有兩個相等記錄的關鍵字R和S，且在原本的列表中R出現在S之前，在排序過的列表中R也將會是在S之前。

不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地實現為穩定。

做這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個對象間之比較，就會被決定使用在原先數據次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。

(6)排序演算法的缺陷擴展閱讀：

排序演算法的分類：

1、通過時間復雜度分類

計算的復雜度（最差、平均、和最好性能），依據列表(list)的大小(n)。

一般而言，好的性能是 O(nlogn)，且壞的性能是 O(n^2)。對於一個排序理想的性能是 O(n)。

而僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要 O(nlogn)。

2、通過空間復雜度分類

存儲器使用量（空間復雜度）（以及其他電腦資源的使用）

3、通過穩定性分類

穩定的排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。

『柒』 怎樣理解選擇排序演算法的不穩定

怎樣理解選擇排序演算法的不穩定
區別在於：冒泡演算法，每次比較如果發現較小的元素在後面，就交換兩個相鄰的元素。而選擇排序演算法的改進在於：先並不急於調換位置，先從A[1]開始逐個檢查，看哪個數最小就記下該數所在的位置P，等一躺掃描完畢，再把A[P]和A[1]對調，這時A[1]到A[10]中最小的數據就換到了最前面的位置。 所以，選擇排序每掃描一遍數組，只需要一次真正的交換，而冒泡可能需要很多次。比較的次數是一樣的。

『捌』 簡述各種排序演算法的優缺點

一、冒泡排序
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與 a[2]的值，若a[1]大於a[2]則交換 兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大於a[3]則交換兩者的值，否則不變。再比 較a[3]與a[4]，以此 類推，最後比較a[n-1]與a[n]的值。這樣處理一輪後，a[n]的值一定是這組數據中最大的。再對a[1]~a[n- 1]以相同方法 處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理 n-1 輪 後a[1]、a[2]、……a[n]就以升序排列了。
優點：穩定；
缺點：慢，每次只能移動相鄰兩個數據。

二、選擇排序
每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數 據元素排完。
選擇排序是不穩定的排序方法。
n 個記錄的文件的直接選擇排序可經過n-1 趟直接選擇排序得到有序結果：
①初始狀態：無序區為R[1..n]，有序區為空。
②第1 趟排序 在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1 個記錄R[1]交換，使R[1..1]和R[2..n]分別變 為記錄個數增加1 個的新有序區和記錄個數減少1 個的新無序區。
③第i 趟排序
第i 趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n-1)。該趟 排序從當前無序區中選出關鍵字最 小的記錄 R[k]，將它與無序區的第1 個記錄R 交換，使R[1..i]和R 分別變為記錄個數增加1 個的新有序區和記錄個數減少 1 個的新無序區。
這樣，n 個記錄的文件的直接選擇排序可經過n-1 趟直接選擇排序得到有序結果。
優點：移動數據的次數已知（n-1 次）；
缺點：比較次數多。

三、插入排序
已知一組升序排列數據a[1]、a[2]、……a[n]，一組無序數據b[1]、 b[2]、……b[m]，需將二者合並成一個升序數列。 首先比較b[1]與a[1]的值，若b[1]大於a[1]，則跳過，比較b[1]與a[2]的值， 若b[1]仍然大於a[2]，則繼續跳過，直 到b[1]小於a 數組中某一數據a[x]，則將a[x]~a[n]分別向後移動一位，將b[1]插入到原來 a[x]的位置這就完成了b[1] 的插入。b[2]~b[m]用相同方法插入。（若無數組a，可將b[1]當作n=1 的數組a）
優點：穩定，快；
缺點：比較次數不一定，比較次數越少，插入點後的數據移動越多，特別是當數據總量龐大的時候，但用鏈表可以解決 這個問題。

四、縮小增量排序
由希爾在1959 年提出，又稱希爾排序(shell 排序)。
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。發現當n 不大時，插入 排序的效果很好。首先取一增 量d(d<n)，將a[1]、a[1+d]、a[1+2d]……列為第一組，a[2]、a[2+d]、 a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……="" 列為最後一組以次類推，在各組內用插入排序，然後取d'<d，重復上述操="" 作，直到d="1。"
優點：快，數據移動少；=""
缺點：不穩定，d="" 的取值是多少，應取多少個不同的值，都無法確切知道，只能憑經驗來取。=""

五、快速排序=""
快速排序是冒泡排序的改進版，是目前已知的最快的排序方法。
="" 已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先任取數據a[x]="" 作為基準。比較a[x]與其它數據並="" 排序，使a[x]排在數據的第k="" 位，並且使a[1]~a[k-1]中的每一個數="" 據a[x]，然後采 用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n] 兩組數據進行快速排序。
優點：極快，數據移動少；
缺點：不穩定。

『玖』 為什麼快速排序是不穩定的演算法

排序演算法不穩定的含義是:

在排序之前,有兩個數相等.
但是在排序結束之後,它們兩個有可能改變順序.

比如說:
在一個待排序隊列中,A和B相等,且A排在B的前面,而排序之後,A排在了B的後面.這個時候,我們說這種演算法是不穩定的.
(只要有這種可能性,我們就說演算法是不穩定的.)

注: 演算法的不穩定性,與所用的語言沒有關系的.

那麼,快速排序為什麼不穩定呢?

我們來看看快速排序的過程:(還是借用之前的那個假設,假設A,B相等,並和其它一堆數據一起參加排序.)

假設此時的快排是小於等於關鍵字為排在前面的一組組,大於為另外排在後面的一組.

在選取一個數出來分組的時候,如果選到了A,那麼在B<=A的情況下,B將會排在A的前面.

因為有這樣的_可能性_,所以說我們這種演算法是不穩定的.

注:請參考快排的具體演算法.
另外，TO 朱_大志同學,可能我們兩個的教材有一定的差別.