在本教程中，我們將詳細探討 QuickSort 算法，重點是它的 Java 實現。我們還將討論它的優缺點，然后分析它的時間復雜度。

快速排序算法

快速排序是一種排序算法，它利用了分而治之的原則。 它的平均復雜度為O(n log n)，是最常用的排序算法之一，尤其是對于大數據量。

重要的是要記住快速排序不是一種穩定的算法。 穩定排序算法是一種算法，其中具有相同值的元素在排序輸出中的出現順序與在輸入列表中出現的順序相同。

輸入列表被稱為樞軸的元素分為兩個子列表;一個子列表的元素小于樞軸，另一個子列表的元素大于樞軸。這個過程對每個子列表重復。

最后，所有排序的子列表合并形成最終輸出。

1.算法步驟

我們從列表中選擇一個元素，稱為樞軸。我們將使用它將列表分成兩個子列表。

我們對樞軸周圍的所有元素重新排序——值較小的元素放在它之前，所有大于樞軸的元素放在它之后。在這一步之后，樞軸處于其最終位置。這是重要的分區步驟。

我們將上述步驟遞歸地應用于樞軸左側和右側的兩個子列表。

正如我們所見，快速排序自然是一種遞歸算法，就像所有分而治之的方法一樣。

讓我們舉一個簡單的例子，以便更好地理解這個算法。

Arr[] = {5, 9, 4, 6, 5, 3}

為簡單起見，假設我們選擇 5 作為支點

我們首先將所有小于 5 的元素放在數組的第一個位置：{3, 4, 5, 6, 5, 9}

然后我們將對左子數組 {3,4} 重復它，以 3 作為樞軸

沒有小于3的元素

我們對樞軸右側的子數組應用快速排序，即{4}

該子數組僅包含一個已排序元素

我們繼續原始數組的右邊部分，{6,5,9}，直到我們得到最終的有序數組

2.選擇最佳樞軸

快速排序的關鍵是選擇最佳支點。中間元素當然是最好的，因為它將列表分成兩個相等的子列表。

但是從無序列表中找到中間元素既困難又耗時，這就是為什么我們將第一個元素、最后一個元素、中值或任何其他隨機元素作為樞軸。

Java實現

第一個方法是quickSort()，它將要排序的數組、第一個和最后一個索引作為參數。首先，我們檢查索引并僅在仍有要排序的元素時繼續。

我們得到排序后的樞軸的索引，并使用它遞歸調用partition()方法，參數與quickSort()方法相同，但索引不同：

public void quickSort(int arr[], int begin, int end) {
    if (begin < end) {
        int partitionIndex = partition(arr, begin, end);
        quickSort(arr, begin, partitionIndex-1);
        quickSort(arr, partitionIndex+1, end);
    }
}

讓我們繼續partition()方法。為簡單起見，此函數將最后一個元素作為樞軸。然后，檢查每個元素，如果它的值更小，則在樞軸之前交換它。

到分區結束時，所有小于樞軸的元素都在它的左側，所有大于樞軸的元素都在它的右側。樞軸位于其最終排序位置，函數返回此位置：

private int partition(int arr[], int begin, int end) {
    int pivot = arr[end];
    int i = (begin-1);
    for (int j = begin; j < end; j++) {
        if (arr[j] <= pivot) {
            i++;
            int swapTemp = arr[i];
            arr[i] = arr[j];
            arr[j] = swapTemp;
        }
    }
    int swapTemp = arr[i+1];
    arr[i+1] = arr[end];
    arr[end] = swapTemp;
    return i+1;
}

算法分析

1.時間復雜度

在最好的情況下，算法會將列表分成兩個大小相等的子列表。因此，完整的n大小列表的第一次迭代需要O(n)。用n/2 個元素對剩余的兩個子列表進行排序需要2*O(n/2)個。因此，快速排序算法的復雜度為O(n log n)。

在最壞的情況下，算法將在每次迭代中只選擇一個元素，因此O(n) + O(n-1) + … + O(1)，等于O(n 2 )。

平均而言，QuickSort 的復雜度為O(n log n)，因此適用于大數據量。

2.快速排序與合并排序

讓我們討論在哪些情況下我們應該選擇 QuickSort 而不是 MergeSort。

盡管 Quicksort 和 Mergesort 的平均時間復雜度為O(n log n)，但 Quicksort 是首選算法，因為它的空間復雜度為O(log(n)) 。另一方面，合并排序需要O(n)額外的存儲空間，這使得數組非常昂貴。

快速排序的操作需要訪問不同的索引，但是這種訪問在鏈表中是不可能的，因為沒有連續的塊;因此，要訪問一個元素，我們必須從鏈表的開頭遍歷每個節點。此外，Mergesort 的實現無需為LinkedLists 提供額外空間。

在這種情況下，通常首選快速排序和合并排序的開銷增加。