在本教程中，我們將詳細探討 QuickSort 算法，重點是它的 Java 實現(xiàn)。我們還將討論它的優(yōu)缺點，然后分析它的時間復(fù)雜度。

快速排序算法

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

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

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

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

1.算法步驟

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

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

我們將上述步驟遞歸地應(yīng)用于樞軸左側(cè)和右側(cè)的兩個子列表。

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

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

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

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

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

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

沒有小于3的元素

我們對樞軸右側(cè)的子數(shù)組應(yīng)用快速排序，即{4}

該子數(shù)組僅包含一個已排序元素

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

2.選擇最佳樞軸

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

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

Java實現(xiàn)

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

我們得到排序后的樞軸的索引，并使用它遞歸調(diào)用partition()方法，參數(shù)與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);
    }
}

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

到分區(qū)結(jié)束時，所有小于樞軸的元素都在它的左側(cè)，所有大于樞軸的元素都在它的右側(cè)。樞軸位于其最終排序位置，函數(shù)返回此位置：

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.時間復(fù)雜度

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

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

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

2.快速排序與合并排序

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

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

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

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