请说明快速排序算法的原理,简述快速排序算法

　　1.原理介绍快速排序是一种排序算法，比选择性排序快很多。它主要基于“分而治之”的思想对集合进行排序。本文将对该算法进行分析。

　　2.分而治之(DC) DC的思想主要是指利用递归不断缩小要处理问题的规模，最终使问题变得容易解决。使用DC解决问题的过程包括两个步骤。

　　(1)找出递归的终止条件，该条件必须尽可能简单(称为基线

　　条件)。

　　(2)不断分解问题(或缩小规模)，直到满足递归终止条件(称为归纳条件)。

　　为了便于理解，举个例子。

　　假设有一个数组A=[2，4，6]。如果你想计算一个的所有元素的和，你可以用两种方法。

　　遍历a，把结果一个一个加起来。利用DC思想，通过不断缩小集合的规模，最后把每次递归的结果加起来。该过程如下

　　代码如下：

　　//利用dc的思想计算一个数组元素的和func Sum(ints[]int)int { iflen(ints)==1 {//当集合中只有一个元素时，返回结果return ints[0]} subrar:=ints[1:]//每有一次递归，传递一个和的集合个数就比上一个少一个元素。

　　确定递归的终止条件：对于排序操作，如果数组为空或者只包含一个元素，那么只需要不排序就原样返回数组。因此，空数组或只有一个元素可以用作循环结束的条件。

　　如果不满足递归终止条件，您需要分解数组并执行以下操作，直到满足递归终止条件。

　　2.1.从数组中选择一个元素。这个元素称为参考值。

　　2.2.将数组分成两个子数组：小于参考值的元素和大于参考值的元素。

　　2.3.对步骤2中生成的两个子数组进行快速排序操作。

　　假设你要对[2，1，3，5，4]进行排序，选择3作为参考值，那么过程大致如下：

　　对于快速排序，在基线条件下，我证明了该算法对于空数组或包含

　　元素数组起作用。在归纳条件下，如果快速排序适用于包含一个元素的数组，它也适用于包含两个元素的数组。如果它适用于包含两个元素的数组，那么它也适用于包含三个元素的数组，依此类推。因此，可以看出快速排序适用于任何长度的数组。

　　4.运行时间分析。快速排序的平均运行时间复杂度为O(n log n)，但在最坏的情况下，其复杂度将为O(n ^ 2)。下面分析两个案例。

　　4.1最坏的情况我们来看看最坏的情况会在什么时候发生。考虑以下顺序：

　　快速排序的性能很大程度上取决于您选择的基准值。假设你总是使用第一个元素作为参考值，你必须

　　阵列是有序的。因为快速排序并不检查输入数组是否有序，仍然尝试排序，这需要N层的运算，每层需要比较N个数。所以算法的复杂度是O (n 2)

　　4.2在最佳情况下，考虑以下顺序：

　　该图也对有序数组进行排序，但每次都选择中间的元素作为参考值。此时，递归次数变为3次(logN)，每次需要比较N个元素，因此算法复杂度为O(n log n)。

　　5.代码实现为了简单演示，代码总是选择第一个元素作为基准值。

　　Python版本：

　　def quick sort(array):if len(array)2:返回array else:pivot=array[0]less=[I for I in array[1:]if I=pivot]greater=[I for I in array[1:]I pivot]返回快速排序(less) [pivot]快速排序(greater)打印快速排序([3，5，6，2，6，2])总结DC会逐步分解问题当使用DC处理列表时，基线条件可能是一个空数组或者只包含一个元素。

　　素数元素的数组。快速排序的平均运行时间为O(n log n)。数组排序时，总是选择第一个元素作为参考值，快速排序会是最坏的情况；当数组排序时，中间的元素总是被选为参考值，快速排序将是最好的情况。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。