1.
快速排序-時空複雜度：
快速排序每次將待排序陣列分為兩個部分，在理想狀況下，每一次都將待排序陣列劃分成等長兩個部分，則需要logn次劃分。
而在最壞情況下，即陣列已經有序或大致有序的情況下，每次劃分只能減少一個元素，快速排序將不幸退化為氣泡排序，所以快速排序時間複雜度下界為O(nlogn)，最壞情況為O(n^2)。在實際應用中，快速排序的平均時間複雜度為O(nlogn)。
快速排序在對序列的操作過程中只需花費常數級的空間。空間複雜度S(1)。
但需要注意遞迴棧上需要花費最少logn最多n的空間。
2.快速排序-隨機化演算法：
快速排序的實現需要消耗遞迴棧的空間，而大多數情況下都會透過使用系統遞迴棧來完成遞迴求解。在元素數量較大時，對系統棧的頻繁存取會影響到排序的效率。
一種常見的辦法是設定一個閾值，在每次遞迴求解中，如果元素總數不足這個閾值，則放棄快速排序，呼叫一個簡單的排序過程完成該子序列的排序。這樣的方法減少了對系統遞迴棧的頻繁存取，節省了時間的消費。
一般的經驗表明，閾值取一個較小的值，排序演算法採用選擇、插入等緊湊、簡潔的排序。一個可以參考的具體方案：閾值T=10，排序演算法用選擇排序。
閾值不要太大，否則省下的存取系統棧的時間，將會被簡單排序演算法較多的時間花費所抵消。
另一個可以參考的方法，是自行建棧模擬遞迴過程。但實際經驗表明，收效明顯不如設定閾值。
3.快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。這樣在陣列已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的最佳化方法是隨機化演算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴於輸入資料，而是由於隨機函式取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對於絕大多數輸入資料達到O(nlogn)的期望時間複雜度。一位前輩做出了一個精闢的總結：“隨機化快速排序可以滿足一個人一輩子的人品需求。”
隨機化快速排序的唯一缺點在於，一旦輸入資料中有很多的相同資料，隨機化的效果將直接減弱。對於極限情況，即對於n個相同的數排序，隨機化快速排序的時間複雜度將毫無疑問的降低到O(n^2)。解決方法是用一種方法進行掃描，使沒有交換的情況下主元保留在原位置。
4.設要排序的陣列是A[0]……A[N-1]，首先任意選取一個數據（通常選用第一個資料）作為關鍵資料，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。一趟快速排序的演算法是：
1）設定兩個變數I、J，排序開始的時候：I=0，J=N-1；
2）以第一個陣列元素作為關鍵資料，賦值給key，即 key=A[0]；
3）從J開始向前搜尋，即由後開始向前搜尋（J=J-1），找到第一個小於key的值A[J]，並與A[I]交換；
4）從I開始向後搜尋，即由前開始向後搜尋（I=I+1），找到第一個大於key的A[I]，與A[J]交換；
5）重複第3、4、5步，直到 I=J； (3,4步是在程式中沒找到時候j=j-1，i=i+1。找到並交換的時候i， j指標位置不變。另外當i=j這過程一定正好是i+或j+完成的最後另迴圈結束)
例如：待排序的陣列A的值分別是：（初始關鍵資料：X=49） 注意關鍵X永遠不變，永遠是和X進行比較，無論在什麼位子，最後的目的就是把X放在中間，小的放前面大的放後面。
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：
49 38 65 97 76 13 27
進行第一次交換後： 27 38 65 97 76 13 49
( 按照演算法的第三步從後面開始找)
進行第二次交換後： 27 38 49 97 76 13 65
( 按照演算法的第四步從前面開始找>X的值，65>49,兩者交換，此時：I=3 )
進行第三次交換後： 27 38 13 97 76 49 65
( 按照演算法的第五步將又一次執行演算法的第三步從後開始找
進行第四次交換後： 27 38 13 49 76 97 65
( 按照演算法的第四步從前面開始找大於X的值，97>49,兩者交換，此時：I=4,J=6 )
此時再執行第三步的時候就發現I=J，從而結束一趟快速排序，那麼經過一趟快速排序之後的結果是：27 38 13 49 76 97 65，即所以大於49的數全部在49的後面，所以小於49的數全部在49的前面。
快速排序就是遞迴呼叫此過程——在以49為中點分割這個資料序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部資料序列的快速排序，最後把此資料序列變成一個有序的序列，根據這種思想對於上述陣列A的快速排序的全過程如圖6所示：
初始狀態 {49 38 65 97 76 13 27}
進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65}
分別對前後兩部分進行快速排序 {27 38 13} 經第三步和第四步交換後變成 {13 27 38} 完成排序。
{76 97 65} 經第三步和第四步交換後變成 {65 76 97} 完成排序。
1.
快速排序-時空複雜度：
快速排序每次將待排序陣列分為兩個部分，在理想狀況下，每一次都將待排序陣列劃分成等長兩個部分，則需要logn次劃分。
而在最壞情況下，即陣列已經有序或大致有序的情況下，每次劃分只能減少一個元素，快速排序將不幸退化為氣泡排序，所以快速排序時間複雜度下界為O(nlogn)，最壞情況為O(n^2)。在實際應用中，快速排序的平均時間複雜度為O(nlogn)。
快速排序在對序列的操作過程中只需花費常數級的空間。空間複雜度S(1)。
但需要注意遞迴棧上需要花費最少logn最多n的空間。
2.快速排序-隨機化演算法：
快速排序的實現需要消耗遞迴棧的空間，而大多數情況下都會透過使用系統遞迴棧來完成遞迴求解。在元素數量較大時，對系統棧的頻繁存取會影響到排序的效率。
一種常見的辦法是設定一個閾值，在每次遞迴求解中，如果元素總數不足這個閾值，則放棄快速排序，呼叫一個簡單的排序過程完成該子序列的排序。這樣的方法減少了對系統遞迴棧的頻繁存取，節省了時間的消費。
一般的經驗表明，閾值取一個較小的值，排序演算法採用選擇、插入等緊湊、簡潔的排序。一個可以參考的具體方案：閾值T=10，排序演算法用選擇排序。
閾值不要太大，否則省下的存取系統棧的時間，將會被簡單排序演算法較多的時間花費所抵消。
另一個可以參考的方法，是自行建棧模擬遞迴過程。但實際經驗表明，收效明顯不如設定閾值。
3.快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。這樣在陣列已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的最佳化方法是隨機化演算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴於輸入資料，而是由於隨機函式取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對於絕大多數輸入資料達到O(nlogn)的期望時間複雜度。一位前輩做出了一個精闢的總結：“隨機化快速排序可以滿足一個人一輩子的人品需求。”
隨機化快速排序的唯一缺點在於，一旦輸入資料中有很多的相同資料，隨機化的效果將直接減弱。對於極限情況，即對於n個相同的數排序，隨機化快速排序的時間複雜度將毫無疑問的降低到O(n^2)。解決方法是用一種方法進行掃描，使沒有交換的情況下主元保留在原位置。
4.設要排序的陣列是A[0]……A[N-1]，首先任意選取一個數據（通常選用第一個資料）作為關鍵資料，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。一趟快速排序的演算法是：
1）設定兩個變數I、J，排序開始的時候：I=0，J=N-1；
2）以第一個陣列元素作為關鍵資料，賦值給key，即 key=A[0]；
3）從J開始向前搜尋，即由後開始向前搜尋（J=J-1），找到第一個小於key的值A[J]，並與A[I]交換；
4）從I開始向後搜尋，即由前開始向後搜尋（I=I+1），找到第一個大於key的A[I]，與A[J]交換；
5）重複第3、4、5步，直到 I=J； (3,4步是在程式中沒找到時候j=j-1，i=i+1。找到並交換的時候i， j指標位置不變。另外當i=j這過程一定正好是i+或j+完成的最後另迴圈結束)
例如：待排序的陣列A的值分別是：（初始關鍵資料：X=49） 注意關鍵X永遠不變，永遠是和X進行比較，無論在什麼位子，最後的目的就是把X放在中間，小的放前面大的放後面。
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：
49 38 65 97 76 13 27
進行第一次交換後： 27 38 65 97 76 13 49
( 按照演算法的第三步從後面開始找)
進行第二次交換後： 27 38 49 97 76 13 65
( 按照演算法的第四步從前面開始找>X的值，65>49,兩者交換，此時：I=3 )
進行第三次交換後： 27 38 13 97 76 49 65
( 按照演算法的第五步將又一次執行演算法的第三步從後開始找
進行第四次交換後： 27 38 13 49 76 97 65
( 按照演算法的第四步從前面開始找大於X的值，97>49,兩者交換，此時：I=4,J=6 )
此時再執行第三步的時候就發現I=J，從而結束一趟快速排序，那麼經過一趟快速排序之後的結果是：27 38 13 49 76 97 65，即所以大於49的數全部在49的後面，所以小於49的數全部在49的前面。
快速排序就是遞迴呼叫此過程——在以49為中點分割這個資料序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部資料序列的快速排序，最後把此資料序列變成一個有序的序列，根據這種思想對於上述陣列A的快速排序的全過程如圖6所示：
初始狀態 {49 38 65 97 76 13 27}
進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65}
分別對前後兩部分進行快速排序 {27 38 13} 經第三步和第四步交換後變成 {13 27 38} 完成排序。
{76 97 65} 經第三步和第四步交換後變成 {65 76 97} 完成排序。