演算法導論快速排序

A. 為什麼《演算法導論》中的數組序號是從1開始的

c語言下標從零開始是個錯誤，並且 index 也是一個有誤導性的名詞，它表示的是偏移量，明明應該用 offset。
然後 c 的徒子徒孫都學了它，導致現在很多人都誤以為下標應該從 0 開始。
早期蠻荒時代，很多東西都不科學，演算法導論作者致力於與落後文明作斗爭，然而卻遭到了樓主你的不理解，實乃編程屆一大憾事。
我再說一遍，C 是結構化的匯編，下標基 0 是受到了 PDP-11 指令集的影響，更老的語言（比如 Fortran）都是基 1 的。
另外用 0/非 0 代表 false/true 也是 PDP-11 中 TST 指令和 Z 位的行為。
可能是這本書強調演算法的求學思想，所以從一更加符合數學的數組規定。
但是編程的時候，指針這個東西會經常用到，如果用a(o)作為第一個元素 那麼*a+n就等同於a(n) 比較方便
演算法導論上的這個問題呢，我覺得我比較同意樓上的看法，這個書上面的很多的程序並不是可以敲上去直接運行的，他只是偽代碼，思想而已，給人看的，人類的普遍思維是從1開始，那麼書頁就是從1開始了
說編程語言是給機器看而偽代碼是給人看的簡直是逗大家笑吧...編程語言設計出來就是給人看的....
另外從0開始在很多方便都極好....我覺得寫多代碼都能體會到吧..
幫算導洗地：
演算法導論通篇用的是偽代碼 是給人類閱讀理解的 不是設計給機器去運行的
而絕大多數情況下， index 從 1 開始更符合人類直覺（如果你對這點有異議請參考的答案 ）
但少數情況下， index 從 0 開始更符合人類直覺。例如書中 hashing 還有 FFT 那塊內容， index 是從 0 開始的。
其實寫幾天 Pascal 你就適應啦。。

B. 快速排序方法的時間復雜度為O(n^2）=n(n-1)/2.

1）對於你的問題簡單解釋如下：
理論計算機研究中，衡量演算法一般從兩個方面分析：時間復雜度和空間復雜度。空間復雜度跟時間復雜度是類似的，下面簡單解釋一下時間復雜度：返蘆察對於一個數據規模為n的問題，解決該問題的演算法所用時間可以用含有n的函數T(n)來表示。對於絕大多數情況，我們只需要了解演算法的一般性能而不考慮細節，也就是說，我們只關心函數T(n)的表達式的形式，而不關心表達式的常數系數等與數據規模沒有關系的量值。對於函數T(n)，我們又進一步將它簡化為O(n)，即只考慮演算法平均運行時間的「瓶頸」，也就是T(n)表達式中，關於變數n增長最快的哪一項。比如下面的代碼：
for(int i=1; i<=n*2; i++)
for(int j=1; j<=n; j++)
// do something here
那麼這個演算法的時間復雜度就是O(n^2)，因為它有兩層循環，每層循環的數據嘩消規模都是n。注意第一層循環（外循環）要迭代n*2次，則實際上T(n)=2*n*n，而對於O(n)來說，我們忽略了常數2，只保留了n^2。這就是大O記法的一個概括，並不精確。
對於時間復雜度的更精確、深入的解釋，可以自己查閱《演算法導論》第一章。

2）更正你的問題：快速排序演算法的時間復雜度應該為O(n lg n)。注意三種時間復雜度符號表示的不同意義！英文字母O代表的是平均運行時間，因此對於快速排序來說應該是O(n lg n)。而使用下界函數Omega或者上界函數Theta則分別表示演算法運行的最快和最慢漏茄時間。對於未使用隨機化的快速排序，理論上可以證明，存在某一方法構造出一組數據使快速排序「退化」成平方復雜度演算法即Theta(n^2)。但是對於其O(n)表示法應該為O(n^2)。

C. 對1000個數排序 只需顯示前十個數 用哪種排序演算法

#include "stdio.h"
#include<鋒渣慶string.h>梁缺
#include<math.h>
#include<algorithm>銀握
using namespace std;

int main(void)
{
int n=1000;
int a[1000],i;
for(i=0;i<n;i++)scanf("%d",&a[i]);
sort(a,a+n);
for(i=0;i<10;i++)printf("%d ",a[i]);
puts("");
return 0;
}

D. 各類排序演算法，實現對海量數據排序額，怎麼做

由於數據范圍在1000萬，因此我們需要一個O(n)時間效率的演算法，然而所有基於比較的演算法最快只能達到O(nlgn)的時間效率，因此，所有的基於比較的演算法都無法達到要求。而數的范圍僅僅是2000000之內的整數，因此能開數組記錄。
這里有一個不基於比較的排序，叫計數排序，具體代碼實現以及備註：

void CountingSort(int a[], int b[], int n)
{
int c[100001], i, max = -MaxInt; //c[i]記錄i出現的次數

memset(c, 0, sizeof(c));

for (i = 1; i <= n; i++)
{
c[a[i]]++;
if (a[i] > max)
max = a[i];
}

for (i = 1; i <= max; i++) //c[i]記錄i現在該出現的位置
{
c[i] += c[i - 1];
}

for (i = n; i >= 1; i--)
{
b[c[a[i]]] = a[i]; //排序
c[a[i]]--; //更新
}
}

E. 基於比較的排序演算法

    基於比較的排序演算法，應該是最符合人們直覺的方法。在各種演算法的技術書上，已經證明了基於比較的排序演算法的時間最優復雜度為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規則。

F. 快速排序方法的時間復雜度為O(n^2)=n(n-1)/2中O()是什麼意思

O(1): 表示演算法的運行時間為常量

O(n): 表示該演算法是線性演算法

O(㏒2n): 二分查找演算法

O(n2): 對數組進行排序的各種簡單演算法，例如直接插入排序的演算法。

O(n3): 做兩個n階矩陣的乘法運算

O(2n): 求具有n個元素集合的所有子集的演算法

O(n!): 求具有N個元素的全排列的演算法
O(n²)表示當n很大的時候，復雜度約等於Cn²，C是某個常數，簡單說就是當n足夠大的時候，n的線性增長，復雜度將沿平方增長。
一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。
一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時，T（n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n))
為演算法的漸進時間復雜度，簡稱時間復雜度。

G. 《演算法導論》（第三版）目錄

1.1 演算法

1.2 作為一種技術的演算法

2.1 插入排序

2.2 分析演算法

2.3 設計演算法

2.3.1 分治法

2.3.2 分析分治演算法

3.1 漸近記號

3.2 標准記號與常用函數

4.1 最大子數組問題

4.2 矩陣乘法的 Strassen 演算法

4.3 用代入法求解遞歸式

4.4 用遞歸樹方法求解遞歸式

4.5 用主方法求解遞歸式

*4.6 證明主定理

4.6.1 對 b 的冪證明主定理

4.6.2 向下取整和向上取整

5.1 僱傭問題

5.2 指示器隨機變數

5.3 隨機演算法

*5.4 概率分析和指示器隨機變數的進一步使用

5.4.1 生日悖論

5.4.2 球與箱子

5.4.3 特徵序列

5.4.4 在線僱傭問題

6.1 堆

6.2 維護堆的性質

6.3 建堆

6.4 堆排序演算法

6.5 優先隊列

7.1 快速排序的描述

7.2 快速排序的性能

7.3 快速排序的隨機化版本

7.4 快速排序分析

7.4.1 最壞情況分析

7.4.2 期望運行時間

8.1 排序演算法的下界

8.2 計數排序

8.3 基數排序

8.4 桶排序

9.1 最小值和最大值

9.2 期望為線性時間的選擇演算法

9.3 最壞情況為線性時間的選擇演算法

10.1 棧和隊列

10.2 鏈表

10.3 指針和對象的實現

10.4 有根樹的表示

11.1 直接定址表

11.2 散列表

11.3 散列函數

11.3.1 除法散列法

11.3.2 乘法散列法

*11.3.3 全域散列法

11.4 開放定址法

11.5 完全散列

12.1 什麼是二叉樹

12.2 查詢二叉搜索樹

12.3 插入和刪除

12.4 隨機構建二叉搜索樹

13.1 紅黑樹的性質

13.2 旋轉

13.3 插入

13.4 刪除

14.1 動態順序統計

14.2 如何擴張數據結構

14.3 區間樹

15.1 鋼條切割

15.2 矩陣鏈乘法

15.3 動態規劃原理

15.4 最長公共子序列

15.5 最優二叉搜索樹

16.1 活動選擇問題

16.2 貪心演算法原理

16.3 赫夫曼編碼

*16.4 擬陣和貪心演算法

*16.5 用擬陣求解任務調度問題

17.1 聚合分析

17.2 核演算法

17.3 勢能法

17.4 動態表

17.4.1 表擴張

17.4.2 表擴張和收縮

18.1 B 樹的定義

18.2 B 樹上的基本操作

18.3 從 B 樹上刪除關鍵字

19.1 斐波那契結構

19.2 可合並堆操作

19.3 關鍵字減值和刪除一個結點

19.4 最大度數的界

20.1 基本方法

20.2 遞歸結構

20.2.1 原型 van Emde Boas 結構

20.2.2 原型 van Emde Boas 結構上的操作

20.3 van Emde Boas 樹及其操作

20.3.1 van Emde Boas 樹

20.3.2 van Emde Boas 樹的操作

21.1 不相交集合的操作

21.2 不相交集合的鏈表表示

21.3 不相交集合森林

*21.4 帶路徑壓縮的按秩合並的分析

22.1 圖的表示

22.2 廣度優先搜索

22.3 深度優先搜索

22.4 拓撲排序

22.5 強連通分量

23.1 最小生成樹的形成

23.2 Kruskal 演算法和 Prim 演算法

24.1 Bellman-Ford 演算法

24.2 有向無環圖中的單源最短路徑問題

24.3 Dijkstra 演算法

24.4 差分約束和最短路徑

24.5 最短路徑性質的證明

25.1 最短路徑和矩陣乘法

25.2 Floyd-Warshall 演算法

25.3 用於稀疏圖的 Johnson 演算法

26.1 流網路

26.2 Ford-Fulkerson 方法

26.3 最大二分匹配

*26.4 推送-重貼標簽演算法

*26.5 前置重貼標簽演算法

27.1 動態多線程基礎

27.2 多線程矩陣乘法

27.3 多線程歸並排序

28.1 求解線性方程組

28.2 矩陣求逆

28.3 對稱正定矩陣和最小二乘逼近

29.1 標准型和鬆弛型

29.2 將問題表達為線性規劃

29.3 單純形演算法

29.4 對偶性

29.5 初始基本可行解

30.1 多項式的表示

30.2 DFT 和 FFT

30.3 高效 FFT 實現

31.1 基礎數論概念

31.2 最大公約數

31.3 模運算

31.4 求解模線性方程

31.5 中國余數定理

31.6 元素的冪

31.7 RSA 公鑰加密系統

*31.8 素數的測試

*31.9 整數的因子分解

32.1 樸素字元串匹配演算法

32.2 Rabin-Karp 演算法

32.3 利用有限自動機進行字元串匹配

32.4 Knuth-Morris-Pratt 演算法

33.1 線段的性質

33.2 確定任意一對線段是否相交

33.3 尋找凸包

33.4 尋找最近點對

34.1 多項式時間

34.2 多項式時間的驗證

34.3 NP 完全性與可歸約性

34.4 NP 完全性的證明

34.5 NP 完全問題

34.5.1 團問題

34.5.2 頂點覆蓋問題

34.5.3 哈密頓迴路問題

34.5.4 旅行商問題

34.5.5 子集和問題

35.1 頂點覆蓋問題

35.2 旅行商問題

35.2.1 滿足三角不等式的旅行商問題

35.2.2 一般旅行商問題

35.3 集合覆蓋問題

35.4 隨機化和線性規劃

35.5 子集和問題

A.1 求和公式及其性質

A.2 確定求和時間的界

B.1 集合

B.2 關系

B.3 函數

B.4 圖

B.5 樹

B.5.1 自由樹

B.5.2 有根樹和有序樹

B.5.3 二叉樹和位置樹

C.1 計數

C.2 概率

C.3 離散隨機變數

C.4 幾何分布與二項分布

C.5 二項分布的尾部

D.1 矩陣與矩陣運算

D.2 矩陣的基本性質

H. 如何從最大的N個數中選出最大或者最小的n個數

首先，我們假設n和N都是內存可容納的，也就是說N個數可以一次load到內存里存放在數組里（如果非要存在鏈表估計又是另一個challenging的問題了）。從最簡單的情況開始，如果n=1，那麼沒有任何疑惑，必須要進行N-1次的比較才能得到最大的那個數，直接遍歷N個數就可以了。如果n=2呢？當然，可以直接遍歷2遍N數組，第一遍得到最大數max1，但是在遍歷第二遍求第二大數max2的時候，每次都要判斷從N所取的元素的下標不等於max1的下標，這樣會大大增加比較次數。對此有一個解決辦法，可以以max1為分割點將N數組分成前後兩部分，然後分別遍歷這兩部分得到兩個最大數，然後二者取一得到max2。 也可以遍歷一遍就解決此問題，首先維護兩個元素max1，max2（max1=max2），取到N中的一個數以後，先和max1比，如果比max1大（則肯定比max2大），直接替換max1，否則再和max2比較確定是否替換max2。採用類似的方法，對於n=2，3，4一樣可以處理。這樣的演算法時間復雜度為O（nN）。當n越來越大的時候（不可能超過N/2，否則可以變成是找N-n個最小的數的對偶問題），這個演算法的效率會越來越差。但是在n比較小的時候（具體多小不好說），這個演算法由於簡單，不存在遞歸調用等系統損耗，實際效率應該很不錯. 堆：當n較大的時候採用什麼演算法呢？首先我們分析上面的演算法，當從N中取出一個新的數m的時候，它需要依次和max1，max2，max3max n比較，一直找到一個比m小的max x，就用m來替換max x，平均比較次數是n/2。可不可以用更少的比較次數來實現替換呢？最直觀的方法是，也就是網上文章比較推崇的堆。堆有這么一些好處：1.它是一個完全二叉樹，樹的深度是相同節點的二叉樹中最少的，維護效率較高；2.它可以通過數組來實現，而且父節點p與左右子節l，r點的數組下標的關系是s[l] = 2*s[p]+1和s[r] = 2*s[p]+2。在計算機中2*s[p]這樣的運算可以用一個左移1位操作來實現，十分高效。再加上數組可以隨機存取，效率也很高。3.堆的Extract操作，也就是將堆頂拿走並重新維護堆的時間復雜度是O（logn），這里n是堆的大小。 具體到我們的問題，如何具體實現呢？首先開辟一個大小為n的數組區A，從N中讀入n個數填入到A中，然後將A維護成一個小頂堆（即堆頂A[0]中存放的是A中最小的數）。然後從N中取出下一個數，即第n+1個數m，將m與堆頂A[0]比較，如果m<=A[0]，直接丟棄m。否則應該用m替換A[0]。但此時A的堆特性可能已被破壞，應該重新維護堆：從A[0]開始，將A[0]與左右子節點分別比較（特別注意，這里需要比較兩次才能確定最大數，在後面我會根據這個來和敗者樹比較），如果A[0]比左右子節點都小，則堆特性能夠保證，勿需繼續，否則如左（右）節點最大，則將A[0]與左（右）節點交換，並繼續維護左（右）子樹。依次執行，直到遍歷完N，堆中保留的n個數就是N中最大的n個數。 這都是堆排序的基本知識，唯一的trick就是維護一個小頂堆，而不是大頂堆。不明白的稍微想一下。維護一次堆的時間復雜度為O（logn），總體的復雜度是O（Nlogn）這樣一來，比起上面的O（nN），當n足夠大時，堆的效率肯定是要高一些的。當然，直接對N數組建堆，然後提取n次堆頂就能得到結果，而且其復雜度是O（nlogN）,當n不是特別小的時候這樣會快很多。但是對於online數據就沒辦法了，比如N不能一次load進內存，甚至是一個流，根本不知道N是多少。 敗者樹：有沒有別的演算法呢？我先來說一說敗者樹（loser tree）。也許有些人對loser tree不是很了解，其實它是一個比較經典的外部排序方法，也就是有x個已經排序好的文件，將其歸並為一個有序序列。敗者樹的思想咋一看有些繞，其實是為了減小比較次數。首先簡單介紹一下敗者樹：敗者樹的葉子節點是數據節點，然後兩兩分組（如果節點總數不是2的冪，可以用類似完全樹的結構構成樹），內部節點用來記錄左右子樹的優勝者中的敗者（注意記錄的是輸的那一方），而優勝者則往上傳遞繼續比較，一直到根節點。如果我們的優勝者是兩個數中較小的數，則根節點記錄的是最後一次比較中的敗者，也就是所有葉子節點中第二小的那個數，而最小的那個數記錄在一個獨立的變數中。這里要注意，內部節點不但要記錄敗者的數值，還要記錄對應的葉子節點。如果是用鏈表構成的樹，則內部節點需要有指針指向葉子節點。這里可以有一個trick，就是內部節點只記錄敗者對應的葉子節點，具體的數值可以在需要的時候間接訪問（這一方法在用數組來實現敗者樹時十分有用，後面我會講到）。關鍵的來了，當把最小值輸出後，最小值所對應的葉子節點需要變成一個新的數（或者改為無窮大，在文件歸並的時候表示文件已讀完）。接下來維護敗者樹，從更新的葉子節點網上，依次與內部節點比較，將敗者更新，勝者往上繼續比較。由於更新節點佔用的是之前的最小值的葉子節點，它往上一直到根節點的路徑與之前的最小值的路徑是完全相同的。內部節點記錄的敗者雖然稱為敗者，但卻是其所在子樹中最小的數。也就是說，只要與敗者比較得到的勝者，就是該子樹中最小的那個數（這里講得有點繞了，看不明白的還是找本書看吧，對照著圖比較容易理解）。 註：也可以直接對N構建敗者樹，但是敗者樹用數組實現時不能像堆一樣進行增量維護，當葉子節點的個數變動時需要完全重新構建整棵樹。為了方便比較堆和敗者樹的性能，後面的分析都是對n個數構建的堆和敗者樹來分析的。 總而言之，敗者樹在進行維護的時候，比較次數是logn+1。與堆不同的是，敗者樹是從下往上維護，每上一層，只需要和敗者節點比較一次即可。而堆在維護的時候是從上往下，每下一層，需要和左右子節點都比較，需要比較兩次。從這個角度，敗者樹比堆更優一些。但是，請注意但是，敗者樹每一次維護必定需要從葉子節點一直走到根節點，不可能中間停止；而堆維護時，有可能會在中間的某個層停止，不需要繼續往下。這樣一來，雖然每一層敗者樹需要的比較次數比堆少一倍，但是走的層數堆會比敗者樹少。具體少多少，從平均意義上到底哪一個的效率會更好一些？那我就不知道了，這個分析起來有點麻煩。感興趣的人可以嘗試一下，討論討論。但是至少說明了，也許堆並非是最優的。 具體到我們的問題。類似的方法，先構建一棵有n個葉子節點的敗者樹，勝出者w是n個中最小的那一個。從N中讀入一個新的數m後，和w比較，如果比w小，直接丟棄，否則用m替換w所在的葉子節點的值，然後維護該敗者樹。依次執行，直到遍歷完N，敗者樹中保留的n個數就是N中最大的n個數。時間復雜度也是O（Nlogn） 類快速排序方法： 快速排序大家大家都不陌生了。主要思想是找一個軸節點，將數列交換變成兩部分，一部分全都小於等於軸，另一部分全都大於等於軸，然後對兩部分遞歸處理。其平均時間復雜度是O（NlogN）。從中可以受到啟發，如果我們選擇的軸使得交換完的較大那一部分的數的個數j正好是n，不也就完成了在N個數中尋找n個最大的數的任務嗎？當然，軸也許不能選得這么恰好。可以這么分析，如果jn，則最大的n個數肯定在這j個數中，則問題變成在這j個數中找出n個最大的數；否則如果j<n，則這j個數肯定是n個最大的數的一部分，而剩下的j-n個數在小於等於軸的那一部分中，同樣可遞歸處理。 需要注意的是，這里的時間復雜度是平均意義上的，在最壞情況下，每次分割都分割成1：N-2，這種情況下的時間復雜度為O（n）。但是我們還有殺手鐧，可以有一個在最壞情況下時間復雜度為O（N）的演算法，這個演算法是在分割數列的時候保證會按照比較均勻的比例分割，at least 3n/10-6。具體細節我就不再說了，感興趣的人參考演算法導論（Introction to Algorithms 第二版第九章 Medians and Orders Statistics）。 還是那個結論，堆不見得會是最優的。 本文快要結束了，但是還有一個問題：如果N非常大，存放在磁碟上，不能一次裝載進內存呢？怎麼辦？對於介紹的Naive方法，堆，敗者樹等等，依然適用，需要注意的就是每次從磁碟上盡量多讀一些數到內存區，然後處理完之後再讀入一批。減少IO次數，自然能夠提高效率。而對於類快速排序方法，稍微要麻煩一些：分批讀入，假設是M個數，然後從這M個數中選出n個最大的數緩存起來，直到所有的N個數都分批處理完之後，再將各批次緩存的n個數合並起來再進行一次類快速排序得到最終的n個最大的數就可以了。在運行過程中，如果緩存數太多，可以不斷地將多個緩存合並，保留這些緩存中最大的n個數即可。由於類快速排序的時間復雜度是O（N），這樣分批處理再合並的辦法，依然有極大的可能會比堆和敗者樹更優。當然，在空間上會佔用較多的內存。 總結：對於這個問題，我想了很多，但是覺得還有一些地方可以繼續深挖：1. 堆和敗者樹到底哪一個更優？可以通過理論分析，也可以通過實驗來比較。也許會有人覺得這個很無聊；2. 有沒有近似的演算法或者概率演算法來解決這個問題？我對這方面實在不熟悉，如果有人有想法的話可以一塊交流。如果有分析錯誤或遺漏的地方，請告知，我不怕丟人，呵呵！最後請時刻謹記，時間復雜度不等於實際的運行時間，一個常數因子很大的O（logN）演算法也許會比常數因子小的O（N）演算法慢很多。所以說，n和N的具體值，以及編程實現的質量，都會影響到實際效率。

I. 快速排序法 平均情況時間復雜度

快速森世排序時間復雜度穗洞可以此族肢寫成
T(n)=2T(n/2)+n,這個求解就是T(n)=nlogn

J. 《演算法導論》（原書第二版）。這本書裡面的程序是用什麼寫的是java嗎

這本書的程序是用偽代碼加英文注釋寫的，學過C/C++/JAVA的都能看懂。

原書摘錄如下（快速排序）：
QUICKSORT'(A,p,r)
while p<r
do △ Partition and sort left subarray.
q <- PARTITION(A,p,r)
QUICKSORT'(A,p,q-1)
p <- q+1