先决条件： 尾声消除
null
在里面 快速排序 ，分区函数已经就位，但我们需要额外的空间来进行递归函数调用。快速排序的一个简单实现对自身进行两次调用，在最坏的情况下，需要函数调用堆栈上的O（n）空间。
最坏的情况是，选定的轴总是分割数组，使一部分有0个元素，而另一部分有n-1个元素。例如，在下面的代码中，如果我们选择最后一个元素作为轴心，我们得到排序数组的最坏情况（参见 这 （用于可视化）
C
/* A Simple implementation of QuickSort that makes two two recursive calls. */ 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); } } // See below link for complete running code |
JAVA
// A Simple implementation of QuickSort that // makes two recursive calls. 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); } } // This code is contributed by rutvik_56 |
Python3
# Python3 program for the above approach def quickSort(arr, low, high): if (low < high): # pi is partitioning index, arr[p] is now # at right place pi = partition(arr, low, high) # Separately sort elements before # partition and after partition quickSort(arr, low, pi - 1 ) quickSort(arr, pi + 1 , high) # This code is contributed by sanjoy_62 |
C#
// A Simple implementation of QuickSort that // makes two recursive calls. 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); } } // This code is contributed by pratham76. |
Javascript
<script> // A Simple implementation of QuickSort that // makes two recursive calls. function quickSort(arr , low , high) { if (low < high) { // pi is partitioning index, arr[p] is // now at right place var pi = partition(arr, low, high); // Separately sort elements before // partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } // This code is contributed by umadevi9616. </script> |
我们能减少函数调用堆栈的辅助空间吗？ 我们可以将辅助空间限制为O（logn）。这个想法是基于 尾声消除 .如图所示 以前的职位 ，我们可以转换代码，使其进行一次递归调用。例如，在下面的代码中，我们将上面的代码转换为使用while循环，并减少了递归调用的数量。
C
/* QuickSort after tail call elimination using while loop */ void quickSort( int arr[], int low, int high) { while (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); low = pi+1; } } // See below link for complete running code |
JAVA
/* QuickSort after tail call elimination using while loop */ static void quickSort( int arr[], int low, int high) { while (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 ); low = pi+ 1 ; } } // See below link for complete running code // This code is contributed by gauravrajput1 |
Python3
# QuickSort after tail call elimination using while loop ''' def quickSort(arr, low, high): while (low < high): # pi is partitioning index, arr[p] is now # at right place ''' pi = partition(arr, low, high) # Separately sort elements before # partition and after partition quickSort(arr, low, pi - 1 ) low = pi + 1 # See below link for complete running code # https:#ide.geeksforgeeks.org/qrlM31 # This code is contributed by gauravrajput1 |
C#
/* QuickSort after tail call elimination using while loop */ static void quickSort( int []arr, int low, int high) { while (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); low = pi+1; } } // See below link for complete running code // This code contributed by gauravrajput1 |
Javascript
<script> /* QuickSort after tail call elimination using while loop */ function quickSort(arr , low , high) { while (low < high) { /* pi is partitioning index, arr[p] is now at right place */ var pi = partition(arr, low, high); // Separately sort elements before // partition and after partition quickSort(arr, low, pi - 1); low = pi+1; } } // See below link for complete running code // This code is contributed by gauravrajput1 </script> |
虽然我们减少了递归调用的数量，但在最坏的情况下，上面的代码仍然可以使用O（n）辅助空间。在最坏的情况下，数组的划分方式可能是第一部分始终有n-1个元素。例如，当最后一个元素被选为轴，数组按递增顺序排序时，可能会发生这种情况。
我们可以优化上面的代码，只对分区后的较小部分进行递归调用。下面是这个想法的实现。
进一步优化：
C
/* This QuickSort requires O(Log n) auxiliary space in worst case. */ void quickSort( int arr[], int low, int high) { while (low < high) { /* pi is partitioning index, arr[p] is now at right place */ int pi = partition(arr, low, high); // If left part is smaller, then recur for left // part and handle right part iteratively if (pi - low < high - pi) { quickSort(arr, low, pi - 1); low = pi + 1; } // Else recur for right part else { quickSort(arr, pi + 1, high); high = pi - 1; } } } // See below link for complete running code |
JAVA
/* This QuickSort requires O(Log n) auxiliary space in worst case. */ static void quickSort( int arr[], int low, int high) { while (low < high) { /* pi is partitioning index, arr[p] is now at right place */ int pi = partition(arr, low, high); // If left part is smaller, then recur for left // part and handle right part iteratively if (pi - low < high - pi) { quickSort(arr, low, pi - 1 ); low = pi + 1 ; } // Else recur for right part else { quickSort(arr, pi + 1 , high); high = pi - 1 ; } } } // See below link for complete running code // This code is contributed by gauravrajput1 |
Python3
''' This QuickSort requires O(Log n) auxiliary space in worst case. ''' def quickSort(arr, low, high) { while (low < high): ''' pi is partitioning index, arr[p] is now at right place ''' pi = partition(arr, low, high); # If left part is smaller, then recur for left # part and handle right part iteratively if (pi - low < high - pi): quickSort(arr, low, pi - 1 ); low = pi + 1 ; # Else recur for right part else : quickSort(arr, pi + 1 , high); high = pi - 1 ; # See below link for complete running code # https:#ide.geeksforgeeks.org/LHxwPk # This code is contributed by gauravrajput1 |
C#
/* This QuickSort requires O(Log n) auxiliary space in worst case. */ static void quickSort( int []arr, int low, int high) { while (low < high) { /* pi is partitioning index, arr[p] is now at right place */ int pi = partition(arr, low, high); // If left part is smaller, then recur for left // part and handle right part iteratively if (pi - low < high - pi) { quickSort(arr, low, pi - 1); low = pi + 1; } // Else recur for right part else { quickSort(arr, pi + 1, high); high = pi - 1; } } } // See below link for complete running code // This code is contributed by gauravrajput1 |
Javascript
<script> /* This QuickSort requires O(Log n) auxiliary space in worst case. */ function quickSort(arr , low , high) { while (low < high) { /* pi is partitioning index, arr[p] is now at right place */ var pi = partition(arr, low, high); // If left part is smaller, then recur for left // part and handle right part iteratively if (pi - low < high - pi) { quickSort(arr, low, pi - 1); low = pi + 1; } // Else recur for right part else { quickSort(arr, pi + 1, high); high = pi - 1; } } } // See below link for complete running code // This code contributed by gauravrajput1 </script> |
在上面的代码中，如果左半部分变小，那么我们对左半部分进行递归调用。其他的都是正确的部分。在最坏的情况下（对于空间），当所有递归调用中的两部分大小相等时，我们使用O（logn）额外空间。
参考： http://www.cs.nthu.edu.tw/~wkhon/algo08教程/tutorial2b。pdf
本文由 德拉杰·贾因 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
