Java中的快速排序

下面的文章《Java 中的快速排序》提供了 Java 中快速排序算法的概述。快速排序算法是一种高效的排序算法，与合并排序算法类似。这是用于实时排序目的的常用算法之一。该算法最坏情况时间复杂度为 O(n^2)，平均情况时间复杂度为 O(n log n)，最好情况时间复杂度为 O(n log n)。

空间复杂度为 O(n log n)，其中 n 是输入的大小。排序过程涉及输入的分区、递归迭代以及为每个递归标记关键元素。该算法中的排序类型涉及以迭代方式比较相邻元素。

开始您的免费软件开发课程

网络开发、编程语言、软件测试及其他

Java 中的快速排序是如何工作的？

快速排序算法可以在 Java 中实现，方法是形成伪代码，并以有效的方式设计和遵循一系列步骤。

• 快速排序算法的主要原理是基于分而治之的方法，也是一种高效的排序算法。
• 输入数组被划分为子数组，划分基于枢轴元素，即中心元素。主元元素两侧的子数组是实际进行排序的主要区域。
• 中心主元元素是将数组分为两个分区的基础，其中左半部分数组元素小于主元元素，右半部分数组元素大于主元元素。
• 在考虑主元元素之前，它可以是数组元素中的任何元素。为了便于理解，通常将其视为中间的或第一个或最后一个。主元元素可以是任意数组元素中的随机元素。
• 在我们的示例中，数组的最后一个元素被视为枢轴元素，其中子数组的划分从数组的右端开始。
• 最后，排序过程完成后，枢轴元素将处于其实际排序位置，其中排序的主要过程在于排序算法的分区逻辑。
• 算法的效率取决于子数组的大小以及它们的平衡方式。子数组越不平衡，时间复杂度就越高，导致最坏情况的复杂度。
• 以随机方式选择主元元素在许多情况下会产生最佳时间复杂度，而不是选择特定的开始、结束或中间索引作为主元元素。

用 Java 实现快速排序的示例

QuickSort算法已使用Java编程语言实现如下，输出代码已显示在代码下方。

• 代码最初使用 QuickSortAlgo() 方法获取输入，并以数组、初始索引和最终索引（即数组的长度）作为参数。
• 调用quickSortAlgo()方法后，它会检查初始索引是否小于最终索引，然后调用arrayPartition()方法获取枢轴元素值。
• 分区元素包含根据枢轴元素周围的元素值排列较小和较大元素的逻辑。
• 执行分区方法后得到主元索引后，会递归调用quickSortAlgo()方法，直到所有子数组完成分区和排序。
• 在分区逻辑中，最后一个元素被指定为枢轴元素，并且第一个元素与枢轴元素进行比较，即根据元素的大小进行交换。
• 这个递归过程会发生，直到数组的所有元素都被分区和排序，最终结果是组合的排序数组。
• 仅当元素小于或等于主元元素时，才会在 for 循环迭代内交换元素。
• 完成迭代过程后，交换最后一个元素，即将枢轴元素值移至左侧，从而进行新的分区，并以递归的形式重复相同的过程，从而产生一系列对不同可能的分区进行排序操作，作为给定数组元素的子数组的形成。
• 下面的代码可以在任何IDE上运行，并且可以通过更改main()中的数组值来验证输出。 main 方法仅用于获取控制台中的输出。作为Java编码标准的一部分，下面可以删除main方法，并可以创建一个对象，并且可以通过将它们设为非静态来调用以下方法。

快速排序算法的Java代码实现

以下是代码实现：

代码：

/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm {
public static void main(String[] args) {
int[] array = { 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 };
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) {
System.out.print(ar + " ");
}
}
public static int arrayPartition(int[] array, int start, int end) {
int pivot = array[end];
int i = (start - 1);
for (int ele = start; ele < end; ele++) {
if (array[ele] <= pivot) {
i++;
int swap = array[i];
array[i] = array[ele];
array[ele] = swap;
}
}
// Swapping the elements
int swap = array[i + 1];
array[i + 1] = array[end];
array[end] = swap;
return i + 1;
}
public static void quickSortAlgo(int[] arrayTobeSorted, int start, int end) {
if (start < end) {
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
}
}
}

输出：

结论

与其他排序技术相比，快速排序算法很高效，但不太稳定。当重复元素数量较多时，快速排序算法的效率会下降，这是一个缺点。此快速排序算法优化了空间复杂度。

以上是Java中的快速排序的详细内容。更多信息请关注PHP中文网其他相关文章！