史上最詳細的演算法

① c語言問題： 什麼是演算法試從日常生活中找3個例子，描述它們的演算法。 詳細點，謝謝！

c語言中的演算法是指：一系列解決問題的清晰指令，用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。通俗說就是解決問題的方法和步驟。

描述演算法的例子：

1. 問題：從上海去到北京。

   其中的演算法：做汽車、做飛機、或者徒步。

2. 問題：喝茶。

   其中的演算法：先找到茶葉，再燒一壺開水，然後將茶葉放到杯子里，將開水倒入杯中，等茶葉泡好。

3. 問題：開車。

   其中的演算法：首先要打開車門，駕駛員坐好，插上車鑰匙，發動汽車。
   

② 調度演算法詳細資料大全

作業系統管理了系統的有限資源，當有多個進程（或多個進程發出的請求）要使用這些資源時，因為資源的有限性，必須按照一定的原則選擇進程（請求）來佔用資源。這就是調度。目的是控制資源使用者的數量,選取資源使用者許可佔用資源或佔用資源。

基本介紹

• 中文名 ：調度演算法
• 所屬領域 ：作業系統

調度演算法,評價因素,吞吐量,CPU利用率,周轉時間,確定進程調度原則,調度演算法分類,先來先服務(FCFS),輪轉法(Round Robin),多級反饋佇列演算法,linux進程調度演算法,

調度演算法

在作業系統中調度是指一種資源分配，因而調度演算法是指：根據系統的資源分配策略所規定的資源分配演算法。對於不同的的系統和系統目標，通常採用不同的調度演算法，例如，在批處理系統中，為了照顧為數眾多的段作業，應採用短作業優先的調度演算法；又如在分時系統中，為了保證系統具有合理的回響時間，應當採用輪轉法進行調度。目前存在的多種調度演算法中，有的演算法適用於作業調度，有的演算法適用於進程調度；但也有些調度演算法既可以用於作業調度，也可以用於進程調度。 通常將作業或進程歸入各種就緒或阻塞佇列。 調度演算法要求：高資源利用率、高吞吐量、用戶滿意等原則。 進程調度所採用的演算法是與整個系統的設計目標相一致的： 1.批處理系統：增加系統吞吐量和提高系統資源的利用率; 2.分時系統：保證每個分時用戶能容忍的回響時間。 3.實時系統：保證對隨機發生的外部事件做出實時回響。

評價因素

吞吐量

單位時間內CPU完成作業的數量。

CPU利用率

從0%～100%。

周轉時間

評價批處理系統的性能指標。 Ti = 作業完成時刻 － 作業提交時刻

確定進程調度原則

在系統角度來說，公平性：每個進程（不論優先權）都有機會被運行；較大的吞吐量。 用戶角度：及時性：回響速度要快；較短的周轉時間：不應當讓用戶等待時間過長。

調度演算法分類

先來先服務(FCFS)

先來先服務（FCFS, First Come First Serve）是最簡單的調度演算法，按先後順序進行調度。 1. FCFS演算法 按照作業提交或進程變為就緒狀態的先後次序，分派CPU； 當前作業或進程佔用CPU，直到執行完或阻塞，才出讓CPU（非搶占方式）。 在作業或進程喚醒後（如I/O完成），並不立即恢復執行，通常等到當前作業或梁兆進程出讓CPU。最簡單的演算法。 2. FCFS的特點 比較有利於長作業，而不利於短作業。 有利於CPU繁忙的作業，而不利於I/O繁忙的作業。

輪轉法(Round Robin)

輪轉法(Round Robin)是讓每個進程在就緒佇列中的等待時間與享受服務的時間成正比例。 1. 輪轉法 將系統中所有的就緒進程按照FCFS原則，排成一個佇列。 每次調度時將CPU分派給隊碧渣戚首進程，讓其執行一個時間片。時間片的長度從幾個ms到幾百ms。 在一個時間片結束時，發生時鍾中斷。 調度程式據此暫停當前進程的執行，將其送到就緒佇列的末尾，並通過上下文切換執行當前的隊首進程。? 進程可以未使用完一個時間片，就出讓CPU（如阻塞）。 2. 時間片長度的確定 時間片長度變化的影響2 過長－>退化為FCFS演算法，進程在一個時間片內都執行完，回響時間長。2 過短－>用戶的一次請求需要多個時間片才能處理完，上下文切換次數增加，回響時間長。 對回響時間的要求：T(回響悔陵時間)=N(進程數目)*q(時間片) 就緒進程的數目：數目越多，時間片越小 系統的處理能力：應當使用戶輸入通常在一個時間片內能處理完，否則使回響時間，平均周轉時間和平均帶權周轉時間延長。

多級反饋佇列演算法

多級反饋佇列演算法時間片輪轉演算法和優先權演算法的綜合和發展。優點：2 為提高系統吞吐量和縮短平均周轉時間而照顧短進程。2 為獲得較好的I/O設備利用率和縮短回響時間而照顧I/O型進程。2 不必估計進程的執行時間，動態調節。 1. 多級反饋佇列演算法2 設定多個就緒佇列，分別賦予不同的優先權，如逐級降低，佇列1的優先權最高。每個佇列執行時間片的長度也不同，規定優先權越低則時間片越長，如逐級加倍。2 新進程進入記憶體後，先投入佇列1的末尾，按FCFS演算法調度；若按佇列1一個時間片未能執行完，則降低投入到佇列2的末尾，同樣按FCFS演算法調度；如此下去，降低到最後的佇列，則按「時間片輪轉」演算法調度直到完成。2 僅當較高優先權的佇列為空，才調度較低優先權的佇列中的進程執行。如果進程執行時有新進程進入較高優先權的佇列，則搶先執行新進程，並把被搶先的進程投入原佇列的末尾。 2. 幾點說明 I/O型進程：讓其進入最高優先權佇列，以及時回響I/O互動。通常執行一個小時間片，要求可處理完一次I/O請求的數據，然後轉入到阻塞佇列。 計算型進程：每次都執行完時間片，進入更低級佇列。最終採用最大時間片來執行，減少調度次數。 I/O次數不多，而主要是CPU處理的進程。在I/O完成後，放回優先I/O請求時離開的佇列，以免每次都回到最高優先權佇列後再逐次下降。2為適應一個進程在不同時間段的運行特點，I/O完成時，提高優先權；時間片用完時，降低優先權。 3.shortest job next 系統計算程式調用的時間，時間最短的先執行。

linux進程調度演算法

linux核心的三種調度方法： 1. SCHED_OTHER 分時調度策略， 2. SCHED_FIFO實時調度策略，先到先服務 3. SCHED_RR實時調度策略，時間片輪轉 實時進程將得到優先調用，實時進程根據實時優先權決定調度權值，分時進程則通過nice和counter值決 定權值，nice越小，counter越大，被調度的機率越大，也就是曾經使用了cpu最少的進程將會得到優先調 度。 SHCED_RR和SCHED_FIFO的不同： 當採用SHCED_RR策略的進程的時間片用完，系統將重新分配時間片，並置於就緒佇列尾。放在佇列 尾保證了所有具有相同優先權的RR任務的調度公平。 SCHED_FIFO一旦佔用cpu則一直運行。一直運行直到有更高優先權任務到達或自己放棄。 如果有相同優先權的實時進程（根據優先權計算的調度權值是一樣的）已經准備好，FIFO時必須等待該 進程主動放棄後才可以運行這個優先權相同的任務。而RR可以讓每個任務都執行一段時間。 SHCED_RR和SCHED_FIFO的相同點： SHCED_RR和SHCED_FIFO都只用於實時任務。 創建時優先權大於0(1-99)。 按照可搶占優先權調度演算法進行。 就緒態的實時任務立即搶占非實時任務。 所有任務都採用linux分時調度策略時。 1. 創建任務指定採用分時調度策略，並指定優先權nice值(-20~19)。 2. 將根據每個任務的nice值確定在cpu上的執行時間(counter)。 3. 如果沒有等待資源，則將該任務加入到就緒佇列中。 4. 調度程式遍歷就緒佇列中的任務，通過對每個任務動態優先權的計算(counter+20-nice)結果，選擇 計算結果最大的一個去運行，當這 個時間片用完後(counter減至0)或者主動放棄cpu時，該任務將被放在 就緒佇列末尾(時間片用完)或等待佇列(因等待資源而放棄cpu)中。 5. 此時調度程式重復上面計算過程，轉到第4步。 6. 當調度程式發現所有就緒任務計算所得的權值都為不大於0時，重復第2步。 所有任務都採用FIFO時: 1. 創建進程時指定採用FIFO，並設定實時優先權rt_priority(1-99)。 2. 如果沒有等待資源，則將該任務加入到就緒佇列中。 3. 調度程式遍歷就緒佇列，根據實時優先權計算調度權值(1000+rt_priority),選擇權值最高的任務使用 cpu，該FIFO任務將一直佔有cpu直到有優先權更高的任務就緒(即使優先權相同也不行)或者主動放棄(等 待資源)。 4. 調度程式發現有優先權更高的任務到達(高優先權任務可能被中斷或定時器任務喚醒，再或被當前運行 的任務喚醒，等等)，則調度程式立即在當前任務 堆疊中保存當前cpu暫存器的所有數據，重新從高優先權 任務的堆疊中載入暫存器數據到cpu，此時高優先權的任務開始運行。重復第3步。 5. 如果當前任務因等待資源而主動放棄cpu使用權，則該任務將從就緒佇列中刪除，加入等待佇列，此時 重復第3步。 所有任務都採用RR調度策略時 1. 創建任務時指定調度參數為RR，並設定任務的實時優先權和nice值(nice值將會轉換為該任務的時間片 的長度)。 2. 如果沒有等待資源，則將該任務加入到就緒佇列中。 3. 調度程式遍歷就緒佇列，根據實時優先權計算調度權值(1000+rt_priority),選擇權值最高的任務使用 cpu。 4. 如果就緒佇列中的RR任務時間片為0，則會根據nice值設定該任務的時間片，同時將該任務放入就緒隊 列的末尾。重復步驟3。 5. 當前任務由於等待資源而主動退出cpu，則其加入等待佇列中。重復步驟3。 系統中既有分時調度，又有時間片輪轉調度和先進先出調度 1. RR調度和FIFO調度的進程屬於實時進程，以分時調度的進程是非實時進程。 2. 當實時進程准備就緒後，如果當前cpu正在運行非實時進程，則實時進程立即搶占非實時進程。 3. RR進程和FIFO進程都採用實時優先權做為調度的權值標准，RR是FIFO的一個延伸。FIFO時，如果兩 個進程的優先權一樣，則這兩個優先 級一樣的進程具體執行哪一個是由其在佇列中的未知決定的，這樣導 致一些不公正性(優先權是一樣的，為什麼要讓你一直運行?),如果將兩個優先權一樣的任務 的調度策略都 設為RR,則保證了這兩個任務可以循環執行，保證了公平。

③ 誰有數學建模十大演算法的詳細介紹啊

1、蒙特卡羅演算法（該演算法又稱隨機性模擬演算法，是通過計算機模擬來解決問題的演算法，
同時可以通過模擬可以來檢驗自己模型的正確性，是比賽時必用的方法）
2、數據擬合、參數估計、插值等數據處理演算法（比賽中通常會遇到大量的數據需要處理，
而處理數據的關鍵就在於這些演算法，通常使用Matlab作為工具）
3、線性規劃、整數規劃、多元規劃、二次規劃等規劃類問題（建模競賽大多數問題屬於最優化問題，
很多時候這些問題可以用數學規劃演算法來描述，通常使用Lindo、Lingo軟體實現）
4、圖論演算法（這類演算法可以分為很多種，包括最短路、網路流、二分圖等演算法，
涉及到圖論的問題可以用這些方法解決，需要認真准備）
5、動態規劃、回溯搜索、分治演算法、分支定界等計算機演算法（這些演算法是演算法設計中比較常用的方法，很多場合可以用到競賽中）
6、最優化理論的三大非經典演算法：模擬退火法、神經網路、遺傳演算法
（這些問題是用來解決一些較困難的最優化問題的演算法，對於有些問題非常有幫助，
但是演算法的實現比較困難，需慎重使用）
7、網格演算法和窮舉法（網格演算法和窮舉法都是暴力搜索最優點的演算法，在很多競賽題中有應用，
當重點討論模型本身而輕視演算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具）
8、一些連續離散化方法（很多問題都是實際來的，數據可以是連續的，而計算機只認的是離散的數據，因此將其離散化後進行差分代替微分、求和代替積分等思想是非常重要的）
9、數值分析演算法（如果在比賽中採用高級語言進行編程的話，那一些數值分析中常用的演算法比
如方程組求解、矩陣運算、函數積分等演算法就需要額外編寫庫函數進行調用）
10、圖象處理演算法（賽題中有一類問題與圖形有關，即使與圖形無關，論文中也應該要不乏圖片的，
這些圖形如何展示以及如何處理就是需要解決的問題，通常使用Matlab進行處理）

④ 求一道數據結構的排序效率比較的詳細演算法

排序演算法是一種基本並且常用的演算法。由於實際工作中處理的數量巨大，所以排序演算法 對演算法本身的速度要求很高。 而一般我們所謂的演算法的性能主要是指演算法的復雜度，一般用O方法來表示。在後面我將 給出詳細的說明。
對於排序的演算法我想先做一點簡單的介紹，也是給這篇文章理一個提綱。 我將按照演算法的復雜度，從簡單到難來分析演算法。 第一部分是簡單排序演算法，後面你將看到他們的共同點是演算法復雜度為O(N*N)（因為沒有使用word,所以無法打出上標和下標）。 第二部分是高級排序演算法，復雜度為O(Log2(N))。這里我們只介紹一種演算法。另外還有幾種 演算法因為涉及樹與堆的概念，所以這里不於討論。 第三部分類似動腦筋。這里的兩種演算法並不是最好的（甚至有最慢的），但是演算法本身比較 奇特，值得參考（編程的角度）。同時也可以讓我們從另外的角度來認識這個問題。現在，讓我們開始吧：
一、簡單排序演算法
由於程序比較簡單，所以沒有加什麼注釋。所有的程序都給出了完整的運行代碼，並在我的VC環境
下運行通過。因為沒有涉及MFC和WINDOWS的內容，所以在BORLAND C++的平台上應該也不會有什麼
問題的。在代碼的後面給出了運行過程示意，希望對理解有幫助。
1.冒泡法：
這是最原始，也是眾所周知的最慢的演算法了。他的名字的由來因為它的工作看來象是冒泡：
#include <iostream.h>
void BubbleSort(int* pData,int Count)
{
int iTemp;
for(int i=1;i<Count;i++)
{
for(int j=Count-1;j>=i;j--)
{
if(pData[j]<pData[j-1])
{
iTemp = pData[j-1];
pData[j-1] = pData[j];
pData[j] = iTemp;
}
}
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
BubbleSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}

倒序(最糟情況)
第一輪：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交換3次)
第二輪：7,10,9,8->7,10,8,9->7,8,10,9(交換2次)
第一輪：7,8,10,9->7,8,9,10(交換1次)
循環次數：6次
交換次數：6次
其他：
第一輪：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交換2次)
第二輪：7,8,10,9->7,8,10,9->7,8,10,9(交換0次)
第一輪：7,8,10,9->7,8,9,10(交換1次)
循環次數：6次
交換次數：3次
上面我們給出了程序段，現在我們分析它：這里，影響我們演算法性能的主要部分是循環和交換， 顯然，次數越多，性能就越差。從上面的程序我們可以看出循環的次數是固定的，為1+2+...+n-1。 寫成公式就是1/2*(n-1)*n。 現在注意，我們給出O方法的定義：
若存在一常量K和起點n0，使當n>=n0時，有f(n)<=K*g(n),則f(n) = O(g(n))。（呵呵，不要說沒 學好數學呀，對於編程數學是非常重要的！！！）

現在我們來看1/2*(n-1)*n，當K=1/2，n0=1，g(n)=n*n時，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) =O(g(n))=O(n*n)。所以我們程序循環的復雜度為O(n*n)。 再看交換。從程序後面所跟的表可以看到，兩種情況的循環相同，交換不同。其實交換本身同數據源的 有序程度有極大的關系，當數據處於倒序的情況時，交換次數同循環一樣（每次循環判斷都會交換）， 復雜度為O(n*n)。當數據為正序，將不會有交換。復雜度為O(0)。亂序時處於中間狀態。正是由於這樣的 原因，我們通常都是通過循環次數來對比演算法。
2.交換法：
交換法的程序最清晰簡單，每次用當前的元素一一的同其後的元素比較並交換。
#include <iostream.h>
void ExchangeSort(int* pData,int Count)
{
int iTemp;
for(int i=0;i<Count-1;i++)
{
for(int j=i+1;j<Count;j++)
{
if(pData[j]<pData[i])
{
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
}
}
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
ExchangeSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情況)
第一輪：10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交換3次)
第二輪：7,10,9,8->7,9,10,8->7,8,10,9(交換2次)
第一輪：7,8,10,9->7,8,9,10(交換1次)
循環次數：6次
交換次數：6次

其他：
第一輪：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交換1次)
第二輪：7,10,8,9->7,8,10,9->7,8,10,9(交換1次)
第一輪：7,8,10,9->7,8,9,10(交換1次)
循環次數：6次
交換次數：3次

從運行的表格來看，交換幾乎和冒泡一樣糟。事實確實如此。循環次數和冒泡一樣 也是1/2*(n-1)*n，所以演算法的復雜度仍然是O(n*n)。由於我們無法給出所有的情況，所以 只能直接告訴大家他們在交換上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。

3.選擇法：
現在我們終於可以看到一點希望：選擇法，這種方法提高了一點性能（某些情況下） 這種方法類似我們人為的排序習慣：從數據中選擇最小的同第一個值交換，在從省下的部分中 選擇最小的與第二個交換，這樣往復下去。
#include <iostream.h>
void SelectSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=0;i<Count-1;i++)
{
iTemp = pData[i];
iPos = i;
for(int j=i+1;j<Count;j++)
{
if(pData[j]<iTemp)
{
iTemp = pData[j];
iPos = j;
}
}
pData[iPos] = pData[i];
pData[i] = iTemp;
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
SelectSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情況)
第一輪：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交換1次)
第二輪：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交換1次)
第一輪：7,8,9,10->(iTemp=9)7,8,9,10(交換0次)
循環次數：6次
交換次數：2次

其他：
第一輪：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交換1次)
第二輪：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交換1次)
第一輪：7,8,10,9->(iTemp=9)7,8,9,10(交換1次)
循環次數：6次
交換次數：3次
遺憾的是演算法需要的循環次數依然是1/2*(n-1)*n。所以演算法復雜度為O(n*n)。 我們來看他的交換。由於每次外層循環只產生一次交換（只有一個最小值）。所以f(n)<=n 所以我們有f(n)=O(n)。所以，在數據較亂的時候，可以減少一定的交換次數。

4.插入法：
插入法較為復雜，它的基本工作原理是抽出牌，在前面的牌中尋找相應的位置插入，然後繼續下一張
#include <iostream.h>
void InsertSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=1;i<Count;i++)
{
iTemp = pData[i];
iPos = i-1;
while((iPos>=0) && (iTemp<pData[iPos]))
{
pData[iPos+1] = pData[iPos];
iPos--;
}
pData[iPos+1] = iTemp;
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
InsertSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}

倒序(最糟情況)
第一輪：10,9,8,7->9,10,8,7(交換1次)(循環1次)
第二輪：9,10,8,7->8,9,10,7(交換1次)(循環2次)
第一輪：8,9,10,7->7,8,9,10(交換1次)(循環3次)
循環次數：6次
交換次數：3次

其他：
第一輪：8,10,7,9->8,10,7,9(交換0次)(循環1次)
第二輪：8,10,7,9->7,8,10,9(交換1次)(循環2次)
第一輪：7,8,10,9->7,8,9,10(交換1次)(循環1次)
循環次數：4次
交換次數：2次

上面結尾的行為分析事實上造成了一種假象，讓我們認為這種演算法是簡單演算法中最好的，其實不是， 因為其循環次數雖然並不固定，我們仍可以使用O方法。從上面的結果可以看出，循環的次數f(n)<= 1/2*n*(n-1)<=1/2*n*n。所以其復雜度仍為O(n*n)（這里說明一下，其實如果不是為了展示這些簡單 排序的不同，交換次數仍然可以這樣推導）。現在看交換，從外觀上看，交換次數是O(n)（推導類似 選擇法），但我們每次要進行與內層循環相同次數的『=』操作。正常的一次交換我們需要三次『=』 而這里顯然多了一些，所以我們浪費了時間。

最終，我個人認為，在簡單排序演算法中，選擇法是最好的。

二、高級排序演算法：
高級排序演算法中我們將只介紹這一種，同時也是目前我所知道（我看過的資料中）的最快的。 它的工作看起來仍然象一個二叉樹。首先我們選擇一個中間值middle程序中我們使用數組中間值，然後 把比它小的放在左邊，大的放在右邊（具體的實現是從兩邊找，找到一對後交換）。然後對兩邊分別使 用這個過程（最容易的方法——遞歸）。
1.快速排序：
#include <iostream.h>
void run(int* pData,int left,int right)
{
int i,j;
int middle,iTemp;
i = left;
j = right;
middle = pData[(left+right)/2]; //求中間值
do{
while((pData[i]<middle) && (i<right))//從左掃描大於中值的數
i++;
while((pData[j]>middle) && (j>left))//從右掃描大於中值的數
j--;
if(i<=j)//找到了一對值
{
//交換
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次）

//當左邊部分有值(left<j)，遞歸左半邊
if(left<j)
run(pData,left,j);
//當右邊部分有值(right>i)，遞歸右半邊
if(right>i)
run(pData,i,right);
}
void QuickSort(int* pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
QuickSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
這里我沒有給出行為的分析，因為這個很簡單，我們直接來分析演算法：首先我們考慮最理想的情況
1.數組的大小是2的冪，這樣分下去始終可以被2整除。假設為2的k次方，即k=log2(n)。
2.每次我們選擇的值剛好是中間值，這樣，數組才可以被等分。
第一層遞歸，循環n次，第二層循環2*(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以演算法復雜度為O(log2(n)*n)
其他的情況只會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那麼他將變 成交換法（由於使用了遞歸，情況更糟）。但是你認為這種情況發生的幾率有多大？？呵呵，你完全 不必擔心這個問題。實踐證明，大多數的情況，快速排序總是最好的。 如果你擔心這個問題，你可以使用堆排序，這是一種穩定的O(log2(n)*n)演算法，但是通常情況下速度要慢 於快速排序（因為要重組堆）。

三、其他排序
1.雙向冒泡：
通常的冒泡是單向的，而這里是雙向的，也就是說還要進行反向的工作。 代碼看起來復雜，仔細理一下就明白了，是一個來回震盪的方式。 寫這段代碼的作者認為這樣可以在冒泡的基礎上減少一些交換（我不這么認為，也許我錯了）。 反正我認為這是一段有趣的代碼，值得一看。
#include <iostream.h>
void Bubble2Sort(int* pData,int Count)
{
int iTemp;
int left = 1;
int right =Count -1;
int t;
do {
//正向的部分
for(int i=right;i>=left;i--)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
left = t+1;
//反向的部分
for(i=left;i<right+1;i++)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
right = t-1;
}while(left<=right);
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
Bubble2Sort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}

2.SHELL排序
這個排序非常復雜，看了程序就知道了。 首先需要一個遞減的步長，這里我們使用的是9、5、3、1（最後的步長必須是1）。 工作原理是首先對相隔9-1個元素的所有內容排序，然後再使用同樣的方法對相隔5-1個元素的排序，以次類推。
#include <iostream.h>
void ShellSort(int* pData,int Count)
{
int step[4];
step[0] = 9;
step[1] = 5;
step[2] = 3;
step[3] = 1;
int i,Temp;
int k,s,w;
for(int i=0;i<4;i++)
{
k = step[i];
s = -k;
for(int j=k;j<Count;j++)
{
iTemp = pData[j];
w = j-k;//求上step個元素的下標
if(s ==0)
{
s = -k;
s++;
pData[s] = iTemp;
}
while((iTemp<pData[w]) && (w>=0) && (w<=Count))
{
pData[w+k] = pData[w];
w = w-k;
}
pData[w+k] = iTemp;
}
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};
ShellSort(data,12);
for (int i=0;i<12;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
呵呵，程序看起來有些頭疼。不過也不是很難，把s==0的塊去掉就輕松多了，這里是避免使用0 步長造成程序異常而寫的代碼。這個代碼我認為很值得一看。 這個演算法的得名是因為其發明者的名字D.L.SHELL。依照參考資料上的說法：「由於復雜的數學原因 避免使用2的冪次步長，它能降低演算法效率。」另外演算法的復雜度為n的1.2次冪。同樣因為非常復雜並 「超出本書討論范圍」的原因（我也不知道過程），我們只有結果了