Java快速排序法

　　Java排名有很多种类型，我以前学过归并排序法和冒泡排序法,Java选择排序法等待相关知识。今天带你去学习排名中的另一个。——　java快速排序法的内容。

　　由于排序过程需要将每个值移动到排序后数组的最终位置，我们可以朝一个方向努力，即将单个值移动到其最终位置。这个想法是一种快速的排序方法

　　，这也是java快速排序法的基础。

　　发现未排序数组中的一个值(如最左边的值)(称为中心点(pivot))正确位置的一种方法是重新排序值，使所有较小的值都出现在中心点的左侧，而所有较大的值都出现在其右侧。这里有一种划分数据的方法。它返回最初位于最左边的最终位置：

　　索引left 数组两端(如下图所示)开始right 并且彼此靠近移动，直到它们重合为止。该中心点，即数组中最左边的位置，索引为left。left左侧的所有值都小于中心点，而right右侧的所有值都大于中心点。主循环的每一步都比较左右值。如果顺序错误，每当交换发生时，交换位置指向中心点值的索引(left和right)就会交替。非中心点数值在任何情况下都会向另一端移动。因为每执行一步， left和right将在n步内相互靠近，left right相等 ，它们都指向中心点值的当前位置。因为只有较小的值出现在中心点的左侧，较大的值在右侧，最后的中心点必须在其最终位置。在下图中，正确位置的值用阴影表示。

　　图：基于中心点数值的数组数值分割40(用阴影表示)。图中的每一步都描述了if语句在partition方法中执行后的数据状态。

　　由于中心点将较大的值与较小的值隔离，我们知道在最终结果中，中心点的另一侧将出现这些值中没有值。这表明规模可以是n的排序问题被分解为两个规模为n/2的排序问题。为了完成排序，只需要将中心点左右的值递归地排序：

　　图:快速排序分析:最左边的值(画圆的中心点)用于将值放置在最后的正确位置(用阴影表示)，并将数组分为两部分:小值和大值。分割的递归执行构成java快速排序。

　　当然，实际上，数值的分割并不总是理想的(见上图中的数值)4的放置)，但经过仔细分析，虽然有这样的存在“糟糕”快速排序的时间复杂度仍然只有 O(nlogn)。

　　当用java当快速排序法对排序值或反向排序值进行排序时，结果令人失望。这是因为所选的中心点值(在这里，也就是最左边的值)的最终位置是在值的一端或另一端。这样，规模就会变大n的问题减少到n-1的问题(而不是n/2)，排序过程需要O(n)遍O(n)步分割。时间的复杂性是 O(n^2)，因为接近排序的值很常见，所以有必要避免这样的结果。

　　请注意，您不必选择最左边的值。如果你想找到中间值的正确位置，数据的其他排列将导致算法的退化。简单来说，对于任何特殊或确定性的分割技术，都有导致退化的数据排列方法。因此，获得更可接受性能的关键是使用一种不确定的分割技术，可以将随机选择的值放置在正确的位置。当然，数据本身是有序的，选择的中心点位置会导致退化，这是罕见的。排序算法在同一组数据上连续运行，几乎不可能表现出相同的行为。因此，尽管在最坏情况下时间的复杂性仍然是O(n^2)，但时间的复杂性是O(nlogn)。以上

　　内容是Java快速排序法的介绍，相信大家都在学习后对java快速排序法有一定的了解，但并非所有情况下都适合使用java快速排序法，当排序中可以使用的额外存储空间非常小时，java快速排序法是不同时使用随机访问结构的好方法，快速排序法不是合适的选择。所以我希望你能在这篇文章的基础上学习其他东西java培训课程根据不同情况选择最合适的相关排序方法的内容java排序法。