快速排序算法 · Programiz 中文系列教程

# 快速排序算法 > 原文： [https://www.programiz.com/dsa/quick-sort](https://www.programiz.com/dsa/quick-sort) #### 在本教程中，您將學習快速排序的工作原理。此外，您還將找到 C，C++ Python 和 Java 中快速排序的工作示例。快速排序是一種基于分治方法的算法，其中將數組拆分為子數組，然后遞歸調用這些子數組以對元素進行排序。 * * * ## 快速排序如何工作？ 1. 從數組中選擇樞軸元素。您可以從數組中選擇任何元素作為樞軸元素。在這里，我們將數組的最右邊（即最后一個元素）作為樞軸元素。 ![Quick Sort Steps](https://img.kancloud.cn/c6/ea/c6eab7ea8c35f8d0ceb14ea2802fa9b0_1020x196.png "Selection of rightmost element") 選擇樞軸元素 2. 小于樞軸元素的元素放在左側，大于樞軸元素的元素放在右側。 ![Quick Sort Steps](https://img.kancloud.cn/94/36/9436e60d67cfdeb5496bbc1e822aa750_1020x196.png "pivoting") 將所有較小的元素放在樞軸元素的左側，將較大的元素放在右側。 1. 指針固定在樞軸元件上。將樞軸元素與從第一個索引開始的元素進行比較。如果達到大于樞軸元素的元素，則為該元素設置第二個指針。 2. 現在，將樞軸元素與其他元素（第三個指針）進行比較。如果到達的元素小于樞軸元素，則將較小的元素替換為較早找到的較大的元素。 ![Quick Sort Steps](https://img.kancloud.cn/fd/d8/fdd8fa6a4275941a36f826079c4418a6_1090x1244.png "comparison") 樞軸元素與其他元素的比較 3. 該過程一直進行到到達倒數第二個元素為止。最后，將樞軸元素與第二個指針交換。 ![Quick Sort Steps](https://img.kancloud.cn/b7/a1/b7a12ebfbb753aa2959270d3f82e22c7_1020x1098.png "swapping") 與第二個指針交換樞軸元素 3. 再次分別為左子部分和右子部分選擇了樞軸元素。在這些子部件中，樞軸元件放置在正確的位置。然后，重復步驟 2。 ![Quick Sort Steps](https://img.kancloud.cn/92/1e/921e153a62a74132d62df4307b713605_982x788.png "Quick Sort Steps") 在每一半中選擇樞軸元素，然后使用遞歸將其放置在正確的位置 4. 將子部分再次劃分為較小的子部分，直到每個子部分由單個元素形成。 5. 至此，該數組已經排序。 * * * **快速排序使用遞歸對子部分進行排序。** 在[分治法](/dsa/divide-and-conquer)的基礎上，快速排序算法可以解釋為： * **劃分** 將數組劃分為以樞軸為分割點的子部分。小于樞軸的元素放置在樞軸的左側，大于樞軸的元素放置在右側。 * **解決** 左子部分和右子部分再次通過選擇樞軸元素進行劃分。這可以通過將子部分遞歸傳遞到算法中來實現。 * **合并** 此步驟在快速排序中不起作用。該數組已在解決步驟的末尾排序。您可以在以下插圖的幫助下了解快速排序的工作方式。 ![Quick Sort Steps](https://img.kancloud.cn/c1/28/c128ad0f4882b511d4bc1905c333da68_2088x938.png "Quick Sort first half") 使用遞歸對樞軸左側的元素進行排序 ![Quick Sort Steps](https://img.kancloud.cn/57/91/5791404a634bc234fb1662bd05ac5692_2088x1192.png "Quick Sort second half") 使用遞歸對樞軸右側的元素進行排序 * * * ## 快速排序算法 ``` quickSort(array, leftmostIndex, rightmostIndex) if (leftmostIndex < rightmostIndex) pivotIndex <- partition(array,leftmostIndex, rightmostIndex) quickSort(array, leftmostIndex, pivotIndex) quickSort(array, pivotIndex + 1, rightmostIndex) partition(array, leftmostIndex, rightmostIndex) set rightmostIndex as pivotIndex storeIndex <- leftmostIndex - 1 for i <- leftmostIndex + 1 to rightmostIndex if element[i] < pivotElement swap element[i] and element[storeIndex] storeIndex++ swap pivotElement and element[storeIndex+1] return storeIndex + 1 ``` * * * ## Python，Java 和 C/C++ 示例 ```py # Quick sort in Python # Function to partition the array on the basis of pivot element def partition(array, low, high): # Select the pivot element pivot = array[high] i = low - 1 # Put the elements smaller than pivot on the left and greater #than pivot on the right of pivot for j in range(low, high): if array[j] <= pivot: i = i + 1 (array[i], array[j]) = (array[j], array[i]) (array[i + 1], array[high]) = (array[high], array[i + 1]) return i + 1 def quickSort(array, low, high): if low < high: # Select pivot position and put all the elements smaller # than pivot on left and greater than pivot on right pi = partition(array, low, high) # Sort the elements on the left of pivot quickSort(array, low, pi - 1) # Sort the elements on the right of pivot quickSort(array, pi + 1, high) data = [8, 7, 2, 1, 0, 9, 6] size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data) ``` ```java // Quick sort in Java import java.util.Arrays; class QuickSort { // Function to partition the array on the basis of pivot element int partition(int array[], int low, int high) { // Select the pivot element int pivot = array[high]; int i = (low - 1); // Put the elements smaller than pivot on the left and // greater than pivot on the right of pivot for (int j = low; j < high; j++) { if (array[j] <= pivot) { i++; int temp = array[i]; array[i] = array[j]; array[j] = temp; } } int temp = array[i + 1]; array[i + 1] = array[high]; array[high] = temp; return (i + 1); } void quickSort(int array[], int low, int high) { if (low < high) { // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); } } // Driver code public static void main(String args[]) { int[] data = { 8, 7, 2, 1, 0, 9, 6 }; int size = data.length; QuickSort qs = new QuickSort(); qs.quickSort(data, 0, size - 1); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); } } ``` ```c // Quick sort in C #include <stdio.h> // Function to swap position of elements void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } // Function to partition the array on the basis of pivot element int partition(int array[], int low, int high) { // Select the pivot element int pivot = array[high]; int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) { if (array[j] <= pivot) { i++; swap(&array[i], &array[j]); } } swap(&array[i + 1], &array[high]); return (i + 1); } void quickSort(int array[], int low, int high) { if (low < high) { // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); } } // Function to print eklements of an array void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("\n"); } // Driver code int main() { int data[] = {8, 7, 2, 1, 0, 9, 6}; int n = sizeof(data) / sizeof(data[0]); quickSort(data, 0, n - 1); printf("Sorted array in ascending order: \n"); printArray(data, n); } ``` ```cpp // Quick sort in C++ #include <iostream> using namespace std; // Function to swap position of elements void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } // Function to print eklements of an array void printArray(int array[], int size) { int i; for (i = 0; i < size; i++) cout << array[i] << " "; cout << endl; } // Function to partition the array on the basis of pivot element int partition(int array[], int low, int high) { // Select the pivot element int pivot = array[high]; int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) { if (array[j] <= pivot) { i++; swap(&array[i], &array[j]); } } printArray(array, 7); cout << "........\n"; swap(&array[i + 1], &array[high]); return (i + 1); } void quickSort(int array[], int low, int high) { if (low < high) { // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); } } // Driver code int main() { int data[] = {8, 7, 6, 1, 0, 9, 2}; int n = sizeof(data) / sizeof(data[0]); quickSort(data, 0, n - 1); cout << "Sorted array in ascending order: \n"; printArray(data, n); } ``` * * * ## 快速排序的復雜度 **時間復雜度** * **最壞情況的復雜度【大 O】** ：`O(n^2)` 當拾取的樞軸元素為最大或最小元素時，會發生這種情況。這種情況導致樞軸元素位于已排序數組的最末端的情況。一個子數組始終為空，而另一個子數組包含`n - 1`元素。因此，僅在此子數組上調用快速排序。但是，快速排序算法對于分散的數據透視表具有更好的性能。 * **最佳情況復雜度【大 Ω】** ：`O(n*log n)` 當樞軸元素始終是中間元素或靠近中間元素時，會發生這種情況。 * **平均病例復雜度【大 θ】** ：`O(n*log n)` 當不出現上述條件時發生。 **空間復雜度** 快速排序的空間復雜度為`O(log n)`。 * * * ## 快速排序應用快速排序在以下情況下實現 * 編程語言適合遞歸 * 時間復雜度很重要 * 空間復雜度很重要