将头围在快速排序排序算法上可能很困难。它不像插入排序或冒泡排序那样直观。
快速排序是对较小列表进行排序的有效方法。在本指南中，我们将讨论如何在Java中构建快速排序。我们将逐步介绍一个示例快速排序，以帮助您入门。
什么是Java Quicksort？
快速排序是一种排序算法，它将数组放入子数组中，然后递归调用这些子数组来排序列表中的每个元素。
慢一点！在快速排序中，我们首先选择一个称为枢轴的数字。我们将此枢纽号码与列表中的每个号码进行比较。
如果某项大于枢轴，则将其移至枢轴的右侧；否则，它会移到左侧。然后，将大于和小于枢轴的所有项目分为两个列表。重复排序算法，直到每个项目至少成为枢轴一次。
快速排序比其他排序更高级。仅当您对递归和更基本的排序算法有很好的了解时，才最好尝试这种排序。
当排序较小的数组时，快速排序比合并排序更有效。在较大的数组上，合并排序更为有效。
Quicksort如何工作？
在不首先学习算法的情况下，我们无法开始编写Java快速排序。我们将逐步进行，以便您可以继续进行。
快速排序的第一步是从数组中选择枢轴。为了方便起见，我们将选择列表中的最后一项作为枢轴。枢轴可以是数组中的任何项目。
快速排序使用递归算法。这是因为每个列表都被划分为执行相同快速排序的子列表。由于快速排序使用递归，因此它们使用分而治之的方法对列表进行排序。
基于每个数字相对于枢轴数字的值对初始列表进行排序。接下来，将其分为子数组。然后，使用递归函数对这些子数组进行相同的排序算法。这就是征服步骤进入的地方。
如何构建Java Quicksort
现在您已经熟悉了快速排序的工作原理，我们可以讨论如何在Java中实现它。我们将从导入Arrays库并为我们的代码定义一个类开始：
import java.util.Arrays;
class QuickSort {
}
Arrays库允许我们打印出数组的值。接下来，我们将定义一个称为“ prepare”的函数。此功能将根据元素相对于轴的值来移动元素。此过程称为准备或分区数据。
大于枢轴的元素将移至枢轴的右侧。小于枢轴的元素将向左移动。
int prepare(int numbers[], int low, int high) {
int pivot = numbers[high];
int item = low - 1;
for (int i = low; i < high; i++) {
if (numbers[i] <= pivot) {
item++;
int swap = numbers[item];
numbers[item] = numbers[i];
numbers[i] = swap;
}
}
int swap = numbers[item + 1];
numbers[item + 1] = numbers[high];
numbers[high] = swap;
return (item + 1);
}
我们首先定义枢轴号。此数字等于我们列表中的最后一项。接下来，我们使用for循环遍历“数字”列表中的每个项目。如果数字小于枢轴，则将其移动到枢轴号之后。否则，该编号将移动到枢轴编号之前。
我们还没有完成。此功能仅准备我们的数据。我们仍然需要执行实际的排序。让我们为我们的排序定义一个新函数：
void sorting(int numbers[], int low, int high) {
if (low < high) {
int pivot = prepare(numbers, low, high);
sorting(numbers, low, pivot - 1);
sorting(numbers, pivot + 1, high);
}
}
只要“ low”的值小于“ high”，我们的sorting（）方法的内容就会运行。这样可以确保我们的排序算法在列表进行排序时停止。
该sorting()函数调用我们的prepare()函数来准备数组。接下来，它再次调用自身两次。第一次调用sorting（）对列表的下半部分进行排序。第二次，sorting（）对列表的上半部分进行排序。
直到列表中的每个项目都被排序为止。因为sorting（）函数调用自身，所以它被视为递归函数。
最后一步是编写一个调用我们的sorting（）函数的主程序：
public static void main(String args[]) {
int[] numbers = { 12, 8, 3, 1, 0, 5 };
int to_sort = numbers.length;
QuickSort new_sort = new QuickSort();
new_sort.sorting(numbers, 0, to_sort - 1);
System.out.println(Arrays.toString(numbers));
}
我们定义了一个名为“数字”的变量，其中包含要排序的数字列表。我们使用.length方法来计算此列表的长度。接下来，我们初始化QuickSort类的新实例。然后，我们调用sorting（）方法对数字列表进行排序。
“ to_sort – 1”被指定为sorting（）函数中的高值。这是因为列表是从0开始索引的，所以我们需要从列表的长度中减去1，这样我们就不会尝试对不存在的值进行排序。
接下来，我们将排序后的数组打印到控制台。该Arrays.toString()方法将“数字”的值转换为Java可以打印到控制台的字符串。
让我们一起运行我们的代码：
[0, 1, 3, 5, 8, 12]
我们的清单已经排序！
复杂度审查
我们还没有完成。在得出结论之前，我们必须回顾快速排序算法的复杂性。在最佳和平均情况下，快速排序的执行效率为O（n * log n）。
在最坏的情况下，快速排序的执行效率为O（n ^ 2）。当枢轴元素是列表中的最大或最小项时，就会发生这种情况。
结论
快速排序算法是对列表进行排序的有效方法。尽管它在较大列表上的性能不超过合并排序，但在较小列表上使用时功能强大。
快速排序是使用递归函数实现的。这是一个反复调用自身的函数，直到问题解决为止。
评论列表 (0)