快速排序-yiteyi-C++库

喜欢合并排序，快速排序是一种分而治之的算法。它选择一个元素作为枢轴，并围绕拾取的枢轴对给定数组进行分区。有许多不同版本的快速排序以不同的方式选择pivot。

null

始终选择第一个元素作为轴心。
始终选择最后一个元素作为轴心（如下所示）
选择一个随机元素作为轴心。
选择中间带作为轴心。

快速排序的关键过程是分区（）。分区的目标是，给定一个数组和数组的一个元素x作为轴心，将x放在排序数组中的正确位置，将所有较小的元素（小于x）放在x之前，将所有较大的元素（大于x）放在x之后。所有这些都应该在线性时间内完成。

递归快速排序函数的伪代码：

/* low  --> Starting index,  high  --> Ending index */quickSort(arr[], low, high){    if (low < high)    {        /* pi is partitioning index, arr[pi] is now           at right place */        pi = partition(arr, low, high);        quickSort(arr, low, pi - 1);  // Before pi        quickSort(arr, pi + 1, high); // After pi    }}

quicksort

划分算法 有很多方法可以进行分区，下面的伪代码采用CLRS手册中给出的方法。逻辑很简单，我们从最左边的元素开始，跟踪较小（或等于）元素的索引，如i。在遍历时，如果我们找到一个较小的元素，我们将当前元素与arr[i]交换。否则我们忽略当前元素。

/* low  --> Starting index,  high  --> Ending index */quickSort(arr[], low, high){    if (low < high)    {        /* pi is partitioning index, arr[pi] is now           at right place */        pi = partition(arr, low, high);        quickSort(arr, low, pi - 1);  // Before pi        quickSort(arr, pi + 1, high); // After pi    }}

分区（）的伪代码

/* This function takes last element as pivot, places   the pivot element at its correct position in sorted    array, and places all smaller (smaller than pivot)   to left of pivot and all greater elements to right   of pivot */partition (arr[], low, high){    // pivot (Element to be placed at right position)    pivot = arr[high];       i = (low - 1)  // Index of smaller element and indicates the                    // right position of pivot found so far    for (j = low; j <= high- 1; j++)    {        // If current element is smaller than the pivot        if (arr[j] < pivot)        {            i++;    // increment index of smaller element            swap arr[i] and arr[j]        }    }    swap arr[i + 1] and arr[high])    return (i + 1)}

分区（）的图示：

arr[] = {10, 80, 30, 90, 40, 50, 70}Indexes:  0   1   2   3   4   5   6 low = 0, high =  6, pivot = arr[h] = 70Initialize index of smaller element, i = -1Traverse elements from j = low to high-1j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])i = 0 arr[] = {10, 80, 30, 90, 40, 50, 70} // No change as i and j                                      // are samej = 1 : Since arr[j] > pivot, do nothing// No change in i and arr[]j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])i = 1arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30 j = 3 : Since arr[j] > pivot, do nothing// No change in i and arr[]j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])i = 2arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swappedj = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j] i = 3 arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped We come out of loop because j is now equal to high-1.Finally we place pivot at correct position by swappingarr[i+1] and arr[high] (or pivot) arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 and 70 Swapped Now 70 is at its correct place. All elements smaller than70 are before it and all elements greater than 70 are afterit.

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

实施： 以下是快速排序的实现：

C++14

                         /* C++ implementation of QuickSort */                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // A utility function to swap two elements                       
                         void                                     swap(                                     int                                     * a,                                     int                                     * b)                       
                         {                       
                                                 int                                     t = *a;                       
                                                 *a = *b;                       
                                                 *b = t;                       
                         }                       
           
                         /* This function takes last element as pivot, places                       
                         the pivot element at its correct position in sorted                       
                         array, and places all smaller (smaller than pivot)                       
                         to left of pivot and all greater elements to right                       
                         of pivot */                       
                         int                                     partition (                                     int                                     arr[],                                     int                                     low,                                     int                                     high)                       
                         {                       
                                                 int                                     pivot = arr[high];                                     // pivot                       
                                                 int                                     i = (low - 1);                                     // Index of smaller element and indicates the right position of pivot found so far                       
           
                                                 for                                     (                                     int                                     j = low; j <= high - 1; j++)                       
                                                 {                       
                                                 // If current element is smaller than the pivot                       
                                                 if                                     (arr[j] < pivot)                       
                                                 {                       
                                                 i++;                                     // increment index of smaller element                       
                                                 swap(&arr[i], &arr[j]);                       
                                                 }                       
                                                 }                       
                                                 swap(&arr[i + 1], &arr[high]);                       
                                                 return                                     (i + 1);                       
                         }                       
           
                         /* The main function that implements QuickSort                       
                         arr[] --> Array to be sorted,                       
                         low --> Starting index,                       
                         high --> Ending index */                       
                         void                                     quickSort(                                     int                                     arr[],                                     int                                     low,                                     int                                     high)                       
                         {                       
                                                 if                                     (low < high)                       
                                                 {                       
                                                 /* pi is partitioning index, arr[p] is now                       
                                                 at right place */                       
                                                 int                                     pi = partition(arr, low, high);                       
           
                                                 // Separately sort elements before                       
                                                 // partition and after partition                       
                                                 quickSort(arr, low, pi - 1);                       
                                                 quickSort(arr, pi + 1, high);                       
                                                 }                       
                         }                       
           
                         /* Function to print an array */                       
                         void                                     printArray(                                     int                                     arr[],                                     int                                     size)                       
                         {                       
                                                 int                                     i;                       
                                                 for                                     (i = 0; i < size; i++)                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
                                                 cout << endl;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {10, 7, 8, 9, 1, 5};                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 quickSort(arr, 0, n - 1);                       
                                                 cout <<                                     "Sorted array: "                                     ;                       
                                                 printArray(arr, n);                       
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by rathbhupendra                       

JAVA

                         // Java implementation of QuickSort                       
                         import                                     java.io.*;                       
           
                         class                                     GFG{                       
                                   
                         // A utility function to swap two elements                       
                         static                                     void                                     swap(                                     int                                     [] arr,                                     int                                     i,                                     int                                     j)                       
                         {                       
                                                 int                                     temp = arr[i];                       
                                                 arr[i] = arr[j];                       
                                                 arr[j] = temp;                       
                         }                       
           
                         /* This function takes last element as pivot, places                       
                                                 the pivot element at its correct position in sorted                       
                                                 array, and places all smaller (smaller than pivot)                       
                                                 to left of pivot and all greater elements to right                       
                                                 of pivot */                       
                         static                                     int                                     partition(                                     int                                     [] arr,                                     int                                     low,                                     int                                     high)                       
                         {                       
                                   
                                                 // pivot                       
                                                 int                                     pivot = arr[high];                       
                                   
                                                 // Index of smaller element and                       
                                                 // indicates the right position                       
                                                 // of pivot found so far                       
                                                 int                                     i = (low -                                     1                                     );                       
           
                                                 for                                     (                                     int                                     j = low; j <= high -                                     1                                     ; j++)                       
                                                 {                       
                                   
                                                 // If current element is smaller                       
                                                 // than the pivot                       
                                                 if                                     (arr[j] < pivot)                       
                                                 {                       
                                   
                                                 // Increment index of                       
                                                 // smaller element                       
                                                 i++;                       
                                                 swap(arr, i, j);                       
                                                 }                       
                                                 }                       
                                                 swap(arr, i +                                     1                                     , high);                       
                                                 return                                     (i +                                     1                                     );                       
                         }                       
           
                         /* The main function that implements QuickSort                       
                                                 arr[] --> Array to be sorted,                       
                                                 low --> Starting index,                       
                                                 high --> Ending index                       
                                                 */                       
                         static                                     void                                     quickSort(                                     int                                     [] arr,                                     int                                     low,                                     int                                     high)                       
                         {                       
                                                 if                                     (low < high)                       
                                                 {                       
                                   
                                                 // pi is partitioning index, arr[p]                       
                                                 // is now at right place                       
                                                 int                                     pi = partition(arr, low, high);                       
           
                                                 // Separately sort elements before                       
                                                 // partition and after partition                       
                                                 quickSort(arr, low, pi -                                     1                                     );                       
                                                 quickSort(arr, pi +                                     1                                     , high);                       
                                                 }                       
                         }                       
           
                         // Function to print an array                       
                         static                                     void                                     printArray(                                     int                                     [] arr,                                     int                                     size)                       
                         {                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < size; i++)                       
                                                 System.out.print(arr[i] +                                     " "                                     );                       
                                   
                                                 System.out.println();                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     [] arr = {                                     10                                     ,                                     7                                     ,                                     8                                     ,                                     9                                     ,                                     1                                     ,                                     5                                     };                       
                                                 int                                     n = arr.length;                       
                                   
                                                 quickSort(arr,                                     0                                     , n -                                     1                                     );                       
                                                 System.out.println(                                     "Sorted array: "                                     );                       
                                                 printArray(arr, n);                       
                         }                       
                         }                       
           
                         // This code is contributed by Ayush Choudhary                       

Python3

                         # Python3 implementation of QuickSort                       
           
                         # This Function handles sorting part of quick sort                       
                         # start and end points to first and last element of                       
                         # an array respectively                       
                         def                                     partition(start, end, array):                       
                                   
                                                 # Initializing pivot's index to start                       
                                                 pivot_index                                     =                                     start                       
                                                 pivot                                     =                                     array[pivot_index]                       
                                   
                                                 # This loop runs till start pointer crosses                       
                                                 # end pointer, and when it does we swap the                       
                                                 # pivot with element on end pointer                       
                                                 while                                     start < end:                       
                                   
                                                 # Increment the start pointer till it finds an                       
                                                 # element greater than  pivot                       
                                                 while                                     start <                                     len                                     (array)                                     and                                     array[start] <                                     =                                     pivot:                       
                                                 start                                     +                                     =                                     1                       
                                   
                                                 # Decrement the end pointer till it finds an                       
                                                 # element less than pivot                       
                                                 while                                     array[end] > pivot:                       
                                                 end                                     -                                     =                                     1                       
                                   
                                                 # If start and end have not crossed each other,                       
                                                 # swap the numbers on start and end                       
                                                 if                                     (start < end):                       
                                                 array[start], array[end]                                     =                                     array[end], array[start]                       
                                   
                                                 # Swap pivot element with element on end pointer.                       
                                                 # This puts pivot on its correct sorted place.                       
                                                 array[end], array[pivot_index]                                     =                                     array[pivot_index], array[end]                       
                                   
                                                 # Returning end pointer to divide the array into 2                       
                                                 return                                     end                       
                                   
                         # The main function that implements QuickSort                       
                         def                                     quick_sort(start, end, array):                       
                                   
                                                 if                                     (start < end):                       
                                   
                                                 # p is partitioning index, array[p]                       
                                                 # is at right place                       
                                                 p                                     =                                     partition(start, end, array)                       
                                   
                                                 # Sort elements before partition                       
                                                 # and after partition                       
                                                 quick_sort(start, p                                     -                                     1                                     , array)                       
                                                 quick_sort(p                                     +                                     1                                     , end, array)                       
                                   
                         # Driver code                       
                         array                                     =                                     [                                     10                                     ,                                     7                                     ,                                     8                                     ,                                     9                                     ,                                     1                                     ,                                     5                                     ]                       
                         quick_sort(                                     0                                     ,                                     len                                     (array)                                     -                                     1                                     , array)                       
           
                         print                                     (f                                     'Sorted array: {array}'                                     )                       
                                   
                         # This code is contributed by Adnan Aliakbar                       

Javascript

                         <script>                       
                         // Javascript implementation of QuickSort                       
           
           
                         // A utility function to swap two elements                       
                         function                                     swap(arr, i, j) {                       
                                                 let temp = arr[i];                       
                                                 arr[i] = arr[j];                       
                                                 arr[j] = temp;                       
                         }                       
           
                         /* This function takes last element as pivot, places                       
                                                 the pivot element at its correct position in sorted                       
                                                 array, and places all smaller (smaller than pivot)                       
                                                 to left of pivot and all greater elements to right                       
                                                 of pivot */                       
                         function                                     partition(arr, low, high) {                       
           
                                                 // pivot                       
                                                 let pivot = arr[high];                       
           
                                                 // Index of smaller element and                       
                                                 // indicates the right position                       
                                                 // of pivot found so far                       
                                                 let i = (low - 1);                       
           
                                                 for                                     (let j = low; j <= high - 1; j++) {                       
           
                                                 // If current element is smaller                       
                                                 // than the pivot                       
                                                 if                                     (arr[j] < pivot) {                       
           
                                                 // Increment index of                       
                                                 // smaller element                       
                                                 i++;                       
                                                 swap(arr, i, j);                       
                                                 }                       
                                                 }                       
                                                 swap(arr, i + 1, high);                       
                                                 return                                     (i + 1);                       
                         }                       
           
                         /* The main function that implements QuickSort                       
                                                 arr[] --> Array to be sorted,                       
                                                 low --> Starting index,                       
                                                 high --> Ending index                       
                                                 */                       
                         function                                     quickSort(arr, low, high) {                       
                                                 if                                     (low < high) {                       
           
                                                 // pi is partitioning index, arr[p]                       
                                                 // is now at right place                       
                                                 let pi = partition(arr, low, high);                       
           
                                                 // Separately sort elements before                       
                                                 // partition and after partition                       
                                                 quickSort(arr, low, pi - 1);                       
                                                 quickSort(arr, pi + 1, high);                       
                                                 }                       
                         }                       
           
                         // Function to print an array                       
                         function                                     printArray(arr, size) {                       
                                                 for                                     (let i = 0; i < size; i++)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
           
                                                 document.write(                                     "<br>"                                     );                       
                         }                       
           
                         // Driver Code                       
           
                         let arr = [10, 7, 8, 9, 1, 5];                       
                         let n = arr.length;                       
           
                         quickSort(arr, 0, n - 1);                       
                         document.write(                                     "Sorted array: <br>"                                     );                       
                         printArray(arr, n);                       
           
                         // This code is contributed by Saurabh Jaiswal                       
                         </script>                       

输出

Sorted array: 1 5 7 8 9 10

快速排序分析 一般来说，快速排序所花费的时间可以写成如下。

 T(n) = T(k) + T(n-k-1) + (n)

前两项用于两个递归调用，最后一项用于分区进程。k是小于枢轴的元素数。快速排序所需的时间取决于输入数组和分区策略。以下是三个案例。

最坏情况： 最坏的情况是，分区过程总是选择最大或最小的元素作为轴心。如果我们考虑上一个元素总是被选择为枢轴的分区策略，则最坏的情况将发生在数组按增加或减少顺序排序时。以下是最坏情况的重现。

 T(n) = T(0) + T(n-1) + (n)which is equivalent to  T(n) = T(n-1) + (n)

上述复发的解决方案是 $heta$ （n） ^2. ).

最佳案例： 最好的情况是，分区过程总是选择中间元素作为轴心。以下是最佳情况下的复发。

 T(n) = 2T(n/2) + (n)

上述复发的解决方案是 $heta$ （nLogn）。可以使用的情况2解决主定理 .

一般情况： 要进行一般案例分析，我们需要考虑数组的所有可能排列，计算每个排列看起来不容易的时间。 . 通过考虑分区将O（n/9）个元素放在一个集合中，将O（9n/10）个元素放在另一个集合中的情况，我们可以了解平均情况。以下是本病例的复发情况。

 T(n) = T(n/9) + T(9n/10) + (n)

上述循环的解也是O（nLogn）尽管快速排序最糟糕的时间复杂度是O（n ^2. )这比许多其他排序算法都好，比如合并排序和堆排序，QuickSort在实践中更快，因为它的内部循环可以在大多数体系结构和大多数真实数据中有效地实现。通过改变枢轴的选择，可以以不同的方式实现快速排序，因此对于给定类型的数据，最坏的情况很少发生。然而，当数据庞大且存储在外部存储器中时，通常认为合并排序更好。

这是快速排序 稳定的 ? 默认实现不稳定。然而，通过将索引作为比较参数，任何排序算法都可以保持稳定。

这是快速排序 到位 ? 根据就地算法的广泛定义，它符合就地排序算法的条件，因为它只使用额外的空间来存储递归函数调用，而不用于操作输入。

什么是三向快速排序？ 在简单的快速排序算法中，我们选择一个元素作为pivot，围绕pivot对数组进行分区，并在pivot的左侧和右侧重现子数组。考虑一个具有许多冗余元素的数组。例如，{1,4,2,4,2,4,1,2,4,1,2,2,2,2,4,1,4,4}。如果在简单快速排序中选择4作为轴心，我们只修复一个4，并递归处理剩余的事件。在三向快速排序中，数组arr[l..r]分为三部分： a） arr[l..i]元素小于枢轴。 b） arr[i+1..j-1]元素等于枢轴。 c） arr[j..r]元素大于枢轴。看见这用于实施。

如何实现链表的快速排序？ 单链表上的快速排序双链表上的快速排序

我们可以迭代地实现快速排序吗？ 是的，请参考迭代快速排序 .

为什么对于排序数组，快速排序优于合并排序 一般形式的快速排序是就地排序（即不需要任何额外存储），而合并排序需要O（N）额外存储，N表示可能非常昂贵的数组大小。分配和取消分配用于合并排序的额外空间会增加算法的运行时间。比较平均复杂度，我们发现这两种类型的排序都有O（NlogN）平均复杂度，但常数不同。对于阵列，由于使用了额外的O（N）存储空间，合并排序会丢失。快速排序的大多数实际实现都使用随机版本。随机版本的时间复杂度预计为O（nLogn）。最坏的情况在随机化版本中也是可能的，但最坏的情况不会出现在特定的模式（如排序数组）中，随机化快速排序在实践中效果很好。快速排序也是一种缓存友好的排序算法，因为它在用于数组时具有良好的引用局部性。快速排序也是尾部递归的，因此进行了尾部调用优化。

为什么对于链表，MergeSort比QuickSort更受欢迎？ 对于链表，情况不同主要是因为数组和链表的内存分配不同。与数组不同，链表节点在内存中可能不相邻。与数组不同，在链表中，我们可以在O（1）额外空间和O（1）时间中插入项。因此，合并排序的合并操作可以在不为链表留出额外空间的情况下实现。在数组中，我们可以进行随机访问，因为元素在内存中是连续的。假设我们有一个整数（4字节）数组A，A[0]的地址为x，那么要访问A[i]，我们可以直接访问（x+i*4）处的内存。与数组不同，我们不能在链表中进行随机访问。快速排序需要大量此类访问。在链表中，为了访问第i个索引，我们必须将每个节点从头部移动到第i个节点，因为我们没有连续的内存块。因此，快速排序的开销会增加。合并排序按顺序访问数据，对随机访问的需求较低。

如何优化快速排序，以便在最坏的情况下占用O（logn）额外的空间？ 请看快速排序尾部调用优化（将最坏情况下的空间减少到日志n）

快照：

scene00865 scene01369