快速排序演算法速度

① 什麼排序的速度（時間復雜度）最快

從時間復雜度看，所有內部排序方法可以分為兩類。

1.插入排序 選擇排序 起泡排序
其時間復雜度為O(n2)；

2.堆排序 快速排序 歸並排序
其時間復雜度為O(nlog2n)。

這是就平均情況而言的，如果從最好的情況考慮，
則插入排序和起泡排序的時間復雜度最好，為O(n)，
而其他演算法的最好情況同平均情況大致相同。

如果從最壞的情況考慮，快速排序的時間復雜度為O(n2)，插入排序和起泡排序雖然同平均情況相同，但系數大約增加一倍，運行速度降低一半，而選擇排序、堆排序和歸並排序則影響不大。

總之，
在平均情況下，快速排序最快；
在最好情況下，插入排序和起泡排序最快；
在最壞情況下，堆排序和歸並排序最快。

② 什麼情況下使用快速排序比較快

在分區時兩個子分區最平衡時。
因為兩個子分區大小不可能同時大於n/2，所以一個分區大小為n/2的下界，另一個分區大小為n/2的上界加1時，快速排序的運行速度最快。
這時，表達其運行時間的遞歸式為
T(n) <= 2T(n/2) + O(n)
根據定理
T(n) =
if n = 1 , then O(n)
if n > 1, then 2T(n/2) + O(n)
的解為T(n) = O(nlgn)
由於在每一層遞歸上，劃分的兩邊都是對稱的。所以，從漸進意義上來看，演算法運行得最快。

③ 希爾排序和快速排序哪個快

希爾排序時間復雜度是O(n^(1.3-2))，空間復雜度為常數階O(1)。希爾排序沒有時間復雜度為O(n(logn))的快速排序演算法快 ，因此對中等大小規模表現良好，但對規模非常大的數據排序不是最優選擇，總之比一般O(n^2 )復雜度的演算法快得多。希爾排序(Shell Sort)是插入排序的一種，它是針對直接插入排序演算法的改進。

概念及其介紹：

希爾排序又稱縮小增量排序，因 DL.Shell 於 1959 年提出而得名。它通過比較相距一定間隔的元素來進行，各趟比較所用的距離隨著演算法的進行而減小，直到只比較相鄰元素的最後一趟排序為止。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個文件恰被分成一組，演算法便終止。

④ 快速排序演算法

快速排序（Quicksort）是對冒泡排序的一種改進。

然後，左邊和右邊的數據可以獨立排序。對於左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。

重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成後，整個數組的排序也就完成了。

快速排序演算法通過多次比較和交換來實現排序，其排序流程如下：

(1)首先設定一個分界值，通過該分界值將數組分成左右兩部分。

(2)將大於或等於分界值的數據集中到數組右邊，小於分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小於或等於分界值，而右邊部分中各元素都大於或等於分界值。

⑤ 快速排序演算法

快速排序演算法是冒泡排序演算法的一種改進

快速排序演算法通過多次比較和交換來實現排序，其排序流程如下：

1、首先設定一個分界值，通過該分界值將數組分成左右兩部分；

2、將大於等於分界值的數據集中到數組右邊，小於分界值的數據集中到數組的左邊；

3、採用遞歸分別多左右集合進行排序;

4、當左右兩部分數據都排序完成後，整個數組的排序就完成了

⑥ 在各類演算法中那種演算法排序是最快的

說句實話，沒有最快這一說。

1. 如果不在乎浪費空間，應該是桶排序最快

2. 如果整體基本有序，插入排序最快

3. 如果考慮綜合情況，快速排序更加實用常見（希爾排序、堆排序等各種排序也各有優劣）

4. 一般情況下，冒泡這種排序僅僅是名字起的有趣罷了，不太好用

⑦ 快速排序法

快速排序（Quicksort）是對冒泡排序的一種改進。[1]

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。[1]

中文名
快速排序演算法
外文名
quick sort
別名
快速排序
提出者
C. A. R. Hoare
提出時間
1960年
快速
導航
排序步驟

程序調用舉例

示例代碼

性能分析
排序流程
快速排序演算法通過多次比較和交換來實現排序，其排序流程如下：[2]
(1)首先設定一個分界值，通過該分界值將數組分成左右兩部分。[2]
(2)將大於或等於分界值的數據集中到數組右邊，小於分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小於或等於分界值，而右邊部分中各元素都大於或等於分界值。[2]
(3)然後，左邊和右邊的數據可以獨立排序。對於左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。[2]
(4)重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成後，整個數組的排序也就完成了。[2]
排序步驟
原理
設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選

快排圖
用數組的第一個數）作為關鍵數據，然後將所有比它小的數都放到它左邊，所有比它大的數都放到它右邊，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩定的排序演算法，也就是說，多個相同的值的相對位置也許會在演算法結束時產生變動。[1]
一趟快速排序的演算法是：[1]
1）設置兩個變數i、j，排序開始的時候：i=0，j=N-1；[1]
2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；[1]
3）從j開始向前搜索，即由後開始向前搜索(j--)，找到第一個小於key的值A[j]，將A[j]和A[i]的值交換；[1]
4）從i開始向後搜索，即由前開始向後搜索(i++)，找到第一個大於key的A[i]，將A[i]和A[j]的值交換；[1]
5）重復第3、4步，直到i==j； (3,4步中，沒找到符合條件的值，即3中A[j]不小於key,4中A[i]不大於key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束）。[1]
排序演示
假設一開始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。
此時，ref=5，i=1，j=11，從後往前找，第一個比5小的數是x8=2，因此序列為：2，3，7，6，4，1，0，5，9，10，8。
此時i=1，j=8，從前往後找，第一個比5大的數是x3=7，因此序列為：2，3，5，6，4，1，0，7，9，10，8。
此時，i=3，j=8，從第8位往前找，第一個比5小的數是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。

⑧ 快速排序方法在任何情況下均可以得到最快的排序效率，對嗎

要排序的數據已基本有序的情況下。

快速排序的基本思想是以基準元素為中心，將待排序表分成兩個子表，然後繼續對子表進行劃分，直到所有子表的長度為1。

快速排序第一趟的結果是：將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小。

(8)快速排序演算法速度擴展閱讀：

快速排序法性能分析：

快速排序的一次劃分演算法從兩頭交替搜索，直到low和high重合，因此其時間復雜度是O(n)；而整個快速排序演算法的時間復雜度與劃分的趟數有關。

理想的情況是，每次劃分所選擇的中間數恰好將當前序列幾乎等分，經過log2n趟劃分，便可得到長度為1的子表。這樣，整個演算法的時間復雜度為O(nlog2n)。

⑨ 快速排序法 pascal

快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一不部分的所有數據都要小，然後再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一躺快速排序。一躺快速排序的演算法是：

1）、設置兩個變數I、J，排序開始的時候I：=1，J：=N；

2）以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]；

3）、從J開始向前搜索，即由後開始向前搜索（J：=J-1），找到第一個小於X的值，兩者交換；

4）、從I開始向後搜索，即由前開始向後搜索（I：=I+1），找到第一個大於X的值，兩者交換；

5）、重復第3、4步，直到I>j；

詳細過程舉例如下：
原序： [26 5 37 1 61 11 59 15 48 19]
一： [19 5 15 1 11] 26 [59 61 48 37]
二： [11 5 15 1] 19 26 [59 61 48 37]
三： [1 5] 11 [15] 19 26 [59 61 48 37]
四： 1 5 11 [15] 19 26 [59 61 48 37]
五： 1 5 11 15 19 26 [59 61 48 37]
六： 1 5 11 15 19 26 [37 48] 59 [61]
七： 1 5 11 15 19 26 37 48 59 [61]
八： 1 5 11 15 19 26 37 48 59 61

快速排序法是所有排序方法中速度最快、效率最高的方法。程序如下：
var a:array[0..10] of integer；
n:integer;
procere qsort(l,r:longint);{r，l表示集合的左右邊界，即把第r到第l個數進行排序}
var i,j,m:longint;
begin
m:=a[l];{標准數}
i:=l; {I，J為指針}
j:=r;
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then begin
a[0]:=a[i];
a[i]:=a[j];
a[j]:=a[0];
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j); {如果集合中不止一個數則進入下一層遞歸，l，J為新邊界}
if i<rthen qsort(i,r); {如果集合中不止一個數則進入下一層遞歸，i，r為新邊界}
end;
begin
for n:=1 to 10 do read(a[n]);
qsort(1,10);
for n:=1 to 10 do write(a[n]:4);
end.

⑩ 選擇排序，快速排序，冒泡排序，堆排序，插入排序，基排序的程序的運行速度

分析如下：
冒泡排序：在最優情況下只需要經過n-1次比較即可得出結果，（這個最優情況那就是序列己是正序，從100K的正序結果可以看出結果正是如此），但在最壞情況下，即倒序（或一個較小值在最後），下沉演算法將需要n(n-1)/2次比較。所以一般情況下，特別是在逆序時，它很不理想。它是對數據有序性非常敏感的排序演算法。

冒泡排序2：它是冒泡排序的改良（一次下沉再一次上浮），最優情況和最壞情況與冒泡排序差不多，但是一般情況下它要好過冒泡排序，它一次下沉，再一次上浮，這樣避免了因一個數的逆序，而造成巨大的比較。如（2,3,4,…,n-1,n,1），用冒泡排序需要n(n-1)/2次比較，而此排序只要3輪,共比較(n-1)+(n-2)+(n-3)次，第一輪1將上移一位，第二輪1將移到首位，第三輪將發現無數據交換，序列有序而結束。但它同樣是一個對數據有序性非常敏感的排序演算法，只適合於數據基本有序的排序。

快速排序：它同樣是冒泡排序的改進，它通過一次交換能消除多個逆序，這樣可以減少逆序時所消耗的掃描和數據交換次數。在最優情況下，它的排序時間復雜度為O(nlog2n)。即每次劃分序列時，能均勻分成兩個子串。但最差情況下它的時間復雜度將是O(n^2)。即每次劃分子串時，一串為空，另一串為m-1（程序中的100K正序和逆序就正是這樣，如果程序中採用每次取序列中部數據作為劃分點，那將在正序和逆時達到最優）。從100K中正序的結果上看「快速排序」會比「冒泡排序」更慢，這主要是「冒泡排序」中採用了提前結束排序的方法。有的書上這解釋「快速排序」，在理論上講，如果每次能均勻劃分序列，它將是最快的排序演算法，因此稱它作快速排序。雖然很難均勻劃分序列，但就平均性能而言，它仍是基於關鍵字比較的內部排序演算法中速度最快者。

直接選擇排序：簡單的選擇排序，它的比較次數一定：n(n-1)/2。也因此無論在序列何種情況下，它都不會有優秀的表現（從上100K的正序和反序數據可以發現它耗時相差不多，相差的只是數據移動時間），可見對數據的有序性不敏感。它雖然比較次數多，但它的數據交換量卻很少。所以我們將發現它在一般情況下將快於冒泡排序。

堆排序：由於它在直接選擇排序的基礎上利用了比較結果形成。效率提高很大。它完成排序的總比較次數為O(nlog2n)。它是對數據的有序性不敏感的一種演算法。但堆排序將需要做兩個步驟：－是建堆，二是排序（調整堆）。所以一般在小規模的序列中不合適，但對於較大的序列，將表現出優越的性能。

直接插入排序：簡單的插入排序，每次比較後最多移掉一個逆序，因此與冒泡排序的效率相同。但它在速度上還是要高點，這是因為在冒泡排序下是進行值交換，而在插入排序下是值移動，所以直接插入排序將要優於冒泡排序。直接插入法也是一種對數據的有序性非常敏感的一種演算法。在有序情況下只需要經過n-1次比較，在最壞情況下，將需要n(n-1)/2次比較。

希爾排序：增量的選擇將影響希爾排序的效率。但是無論怎樣選擇增量，最後一定要使增量為1，進行一次直接插入排序。但它相對於直接插入排序，由於在子表中每進行一次比較，就可能移去整個經性表中的多個逆序，從而改善了整個排序性能。希爾排序算是一種基於插入排序的演算法，所以對數據有序敏感。

歸並排序：歸並排序是一種非就地排序，將需要與待排序序列一樣多的輔助空間。在使用它對兩個己有序的序列歸並，將有無比的優勢。其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。對數據的有序性不敏感。若數據節點數據量大，那將不適合。但可改造成索引操作，效果將非常出色。

基數排序：在程序中採用的是以數值的十進制位分解，然後對空間採用一次性分配，因此它需要較多的輔助空間(10*n+10), （但我們可以進行其它分解，如以一個位元組分解，空間採用鏈表將只需輔助空間n+256）。基數排序的時間是線性的(即O(n))。由此可見，基數排序非常吸引人，但它也不是就地排序，若節點數據量大時宜改為索引排序。但基數排序有個前提，要關鍵字能象整型、字元串這樣能分解，若是浮點型那就不行了。

按平均時間將排序分為類：
(1) 平方階(O(n2))排序
各類簡單排序，例如直接插入、直接選擇和冒泡排序；
(2) 線性對數階(O(nlog2n))排序
如快速排序、堆排序和歸並排序；
(3) O(n1+§))排序
§是介於0和1之間的常數。希爾排序便是一種；
(4) 線性階(O(n))排序
本程序中的基數排序，此外還有桶、箱排序。

排序方法的選擇

因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法很重要
(1)若n較小，可採用直接插入或直接選擇排序。
當記錄規模較小時，直接插入排序較好，它會比選擇更少的比較次數；
但當記錄規模較大時，因為直接選擇移動的記錄數少於直接插人，所以宜用選直接選擇排序。
這兩種都是穩定排序演算法。
(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜(這里的隨機是指基準取值的隨機，原因見上的快速排序分析)；這里快速排序演算法將不穩定。
(3)若n較大，則應採用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸並排序序。
快速排序是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
堆排序雖不會出現快速排序可能出現的最壞情況。但它需要建堆的過程。這兩種排序都是不穩定的。
歸並排序是穩定的排序演算法，但它有一定數量的數據移動，所以我們可能過與插入排序組合，先獲得一定長度的序列，然後再合並，在效率上將有所提高。
(4)特殊的箱排序、基數排序
它們都是一種穩定的排序演算法，但有一定的局限性：
1、關鍵字可分解。
2、記錄的關鍵字位數較少，如果密集更好
3、如果是數字時，最好是無符號的，否則將增加相應的映射復雜度，可先將其正負分開排序。
事實上各種排序方法個有優缺點適用於不同的場合：
排序（Sorting)
插入排序（insertion sort）:直接插入排序 希爾排序（shell's sort）(縮小增量排序Diminishing increment sort)
交換排序：冒泡排序（bubble sort）快速排序（quick sort）
選擇排序:直接選擇排序（straight selection sort），堆排序；
歸並排序（merge sort）：
分配排序：箱排序（Bin sort）,基數排序（radix sort）
更多的自己研究一下。

排序方法的選取主要考慮演算法的性能與資源佔用。也就是速度和佔用的存儲空間。
希望對你有所幫助！