排序演算法最差

❶ 快速排序法的平均時間復雜度和最壞時間復雜度分別是多少

快速排序的平均時間復雜度和最壞時間復雜度分別是O(nlgn)、O(n^2)。

當排序已經成為基本有序狀態時，快速排序退化為O(n^2)，一般情況下，排序為指數復雜度。

快速排序最差情況遞歸調用棧高度O(n)，平均情況遞歸調用棧高度O(logn)，而不管哪種情況棧的每一層處理時間都是O(n)，所以，平均情況（最佳情況也是平均情況）的時間復雜度O(nlogn)，最差情況的時間復雜度為O(n^2)。

(1)排序演算法最差擴展閱讀

快速排序是C.R.A.Hoare於1962年提出的一種劃分交換排序，它採用了一種分治的策略，通常稱其為分治法。快速排序演算法通過多次比較和交換來實現排序，其排序流程如下：

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

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

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

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

❷ 在排序演算法中，哪個排序演算法的時間復雜度最差為什麼

這個不一定,要看數據內容.如果是特殊數據會導致一些演算法退化.綜合來看應該是基數最快,選擇最慢吧(你說的選擇是冒泡排序吧)

❸ 以下排序演算法最壞情況下時間復雜度最低的是 A.冒泡排序 B.插入 C.選擇 D.快排

在冒泡排序，插入排序，選擇排序，快速排序中，在最最壞情況下，快速排序的時間復雜為O(n2) ，插入排序O(n2)，選擇排序O(n2)，冒泡排序O(n2)。所以ABCD時間復雜度是一樣的。

知識拓展：

在快速排序演算法中，最為關鍵的就是選取一個基值，將數組分為大於基值以及小於基值兩部分，並返回基值所以在位置以利用於遞歸劃分。

對數組a，設需要劃分的其中一段為a[p]~a[r]，我們期待的結果是得到一個q，其中p<=q<=r，使得a[p]~a[q-1]<=a[q]<=a[q+1]~a[r]，這個時候原先的一段數組被分成了三部分。

首先，設基值為這段數組的最後一個元素a[r]，我們希望最後得到的結果是a[r]現在對應的值在演算法結束後可以排在比他大和小的兩部分的中間愛。

然後令i=p-1; j=p，當發現有a[j]>x時，j繼續前進，不需要任何移動。當發現a[j]<=x時，我們需要將這個元素放到小於基值的一邊，於是將i自加1，並交換此時a[i]，與a[j]的元素，然後j自加1。這個時候i指向的是比基值小的那段數據的最後一個元素，j指向的是第一個還沒有判斷的剩餘元素。

上面一步不斷循環直到j指向了r，此時只剩下r沒有和基值判斷了，而a[r]本來就是基值，而除了a[r]以外，a[p]~a[i]是小於基值的部分，a[i+1]~a[r-1]是大於基值的部分，所以此時只需交換a[i+1]和a[r]即可。

由於對數組a從頭到尾掃描一次就可以得到結果，因此這一部分演算法復雜度為o(n)