快速排序（Quick Sort）是計算機科學(xué)與技術(shù)領(lǐng)域中非常經(jīng)典的一種排序算法，由C. A. R. Hoare在1960年提出。它應(yīng)用分治思想進(jìn)行排序，通過對數(shù)據(jù)進(jìn)行分區(qū)操作，并遞歸地對分區(qū)后的子序列進(jìn)行排序，從而達(dá)到整個序列有序的目的。

基本思想

快速排序的核心思想是在待排序序列中選擇一個基準(zhǔn)值（pivot），然后將小于基準(zhǔn)值的元素放在基準(zhǔn)值的左邊，大于基準(zhǔn)值的元素放在基準(zhǔn)值的右邊，這樣就找到了基準(zhǔn)值在數(shù)組中的正確位置。之后，再分別對基準(zhǔn)值左右兩邊的子序列進(jìn)行同樣的操作，直到整個序列有序。

排序流程

快速排序算法通過多次比較和交換來實現(xiàn)排序，其排序流程大致如下：

1. 選擇基準(zhǔn)值：在待排序序列中選取一個元素作為基準(zhǔn)值。
2. 分區(qū)操作：通過一趟排序?qū)⒋判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另一部分的所有數(shù)據(jù)要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。
3. 遞歸排序：對基準(zhǔn)值左右兩邊的子序列遞歸地執(zhí)行上述分區(qū)操作，直到子序列的長度為1或0，即已經(jīng)有序。

排序步驟

以數(shù)組為例，快速排序的詳細(xì)步驟可以歸納為：

1. 設(shè)置兩個指針：通常設(shè)置兩個指針i和j，分別指向序列的起始位置和末尾位置。
2. 選擇基準(zhǔn)值：可以選擇序列的第一個元素作為基準(zhǔn)值，也可以采用其他策略選擇基準(zhǔn)值。
3. 分區(qū)操作：
   • 從后往前搜索（j--），找到第一個小于基準(zhǔn)值的元素A[j]，將其與A[i]交換。
   • 從前往后搜索（i++），找到第一個大于基準(zhǔn)值的元素A[i]，將其與A[j]交換。
   • 重復(fù)上述步驟，直到i和j相遇，此時基準(zhǔn)值就位于其最終位置。
4. 遞歸排序：對基準(zhǔn)值左邊的子序列和右邊的子序列分別進(jìn)行快速排序。

性能分析

• 時間復(fù)雜度：快速排序的平均時間復(fù)雜度為O(n log n)，但在最壞情況下（如輸入序列已經(jīng)有序或接近有序），時間復(fù)雜度會退化到O(n^2)。這通常是由于基準(zhǔn)值選擇不當(dāng)導(dǎo)致的。
• 空間復(fù)雜度：快速排序的空間復(fù)雜度主要取決于遞歸的深度。在最好的情況下，遞歸深度為logn，空間復(fù)雜度為O(logn)。但在最壞情況下，遞歸深度可能達(dá)到n，空間復(fù)雜度為O(n)。然而，由于快速排序是原地排序（in-place sort），除了遞歸所需的棧空間外，不需要額外的存儲空間，因此可以認(rèn)為其空間復(fù)雜度是O(logn)（不考慮遞歸棧）。

注意事項

• 快速排序不是一種穩(wěn)定的排序算法，即相同的元素在排序后可能會改變它們之間的相對位置。
• 快速排序的性能受到基準(zhǔn)值選擇策略的影響，因此在實際應(yīng)用中需要選擇合適的基準(zhǔn)值選擇策略以提高排序效率。

隨機值

在快速排序中，選擇基準(zhǔn)值（pivot）的策略對算法的性能有著顯著的影響。傳統(tǒng)的快速排序?qū)崿F(xiàn)可能會選擇序列的第一個、最后一個或中間元素作為基準(zhǔn)值，但這些策略在某些情況下（如輸入序列已經(jīng)部分或完全有序）可能導(dǎo)致算法性能退化到O(n^2)。

為了避免這種情況，一種常用的改進(jìn)方法是隨機選擇基準(zhǔn)值。通過隨機選擇基準(zhǔn)值，可以大大減少算法陷入最壞情況的可能性，從而提高算法的平均性能。

隨機選擇基準(zhǔn)值的步驟

1. 生成隨機數(shù)：首先，生成一個隨機數(shù)randIdx，該隨機數(shù)的范圍是0到n-1（其中n是序列的長度）。

2. 選擇基準(zhǔn)值：然后，將randIdx對應(yīng)的元素選為基準(zhǔn)值。這通常涉及到將基準(zhǔn)值元素與序列的某個位置（如第一個或最后一個位置）的元素進(jìn)行交換，以便于后續(xù)的分區(qū)操作。

3. 進(jìn)行分區(qū)：使用選定的基準(zhǔn)值對序列進(jìn)行分區(qū)操作，將小于基準(zhǔn)值的元素放在基準(zhǔn)值的左邊，大于基準(zhǔn)值的元素放在基準(zhǔn)值的右邊。

4. 遞歸排序：對基準(zhǔn)值左邊和右邊的子序列遞歸地執(zhí)行上述過程，直到子序列的長度為0或1。

優(yōu)點

• 減少最壞情況的發(fā)生：隨機選擇基準(zhǔn)值可以顯著降低算法陷入最壞情況（即每次分區(qū)都只得到一個空子序列）的可能性。

• 提高平均性能：通過隨機化，算法的平均性能更加穩(wěn)定，不易受到輸入數(shù)據(jù)的影響。

注意事項

• 隨機數(shù)的生成：在生成隨機數(shù)時，需要確保隨機數(shù)生成器的質(zhì)量，以避免產(chǎn)生可預(yù)測的序列。

• 實現(xiàn)復(fù)雜度：雖然隨機選擇基準(zhǔn)值可以提高性能，但它也增加了實現(xiàn)的復(fù)雜度。特別是在多線程或并行快速排序的實現(xiàn)中，需要更加小心地處理隨機數(shù)的生成和基準(zhǔn)值的選擇。

• 內(nèi)存和性能權(quán)衡：在某些情況下，為了生成隨機數(shù)和進(jìn)行交換操作，可能會引入額外的內(nèi)存訪問和計算開銷。然而，這些開銷通常遠(yuǎn)小于因避免最壞情況而獲得的性能提升。

912. 排序數(shù)組

給你一個整數(shù)數(shù)組?nums，請你將該數(shù)組升序排列。

示例 1：

輸入：nums = [5,2,3,1]
輸出：[1,2,3,5]

示例2：

輸入：nums = [5,1,1,2,0,0]
輸出：[0,0,1,1,2,5]

提示：

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

若令第一個值為基準(zhǔn)元素，提交會顯示不通過（超時）

class Solution {
public:void quicksort( vector<int>& nums ,int i,int j){if(i<j){   int l=i,r=j;int plt=nums[l];while(l<r){while (l < r && nums[r] >= plt) r--;while (l < r && nums[l] <= plt) l++;if(l<r){swap(nums[l],nums[r]);}}swap(nums[l],nums[i]);quicksort(nums,i,r-1);quicksort(nums,l+1,j);}}vector<int> sortArray(vector<int>& nums) {int i=0;int j=nums.size()-1;quicksort(nums,i,j);return nums;}
};

基準(zhǔn)值采用隨機值，可以通過

class Solution {
public:void quicksort( vector<int>& nums ,int i,int j){if(i<j){   int l=i,r=j;int x = rand() % (r - l + 1) + l; // 基于隨機的原則swap(nums[l], nums[x]);int plt=nums[l];while(l<r){while (l < r && nums[r] >= plt) r--;while (l < r && nums[l] <= plt) l++;if(l<r){swap(nums[l],nums[r]);}}swap(nums[l],nums[i]);quicksort(nums,i,r-1);quicksort(nums,l+1,j);}}vector<int> sortArray(vector<int>& nums) {int i=0;int j=nums.size()-1;quicksort(nums,i,j);return nums;}
};