Java Quicksort:新手指南

陶有为 65 0

将头围在快速排序排序算法上可能很困难。它不像插入排序或冒泡排序那样直观。

快速排序是对较小列表进行排序的有效方法。在本指南中,我们将讨论如何在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)。当枢轴元素是列表中的最大或最小项时,就会发生这种情况。

结论

快速排序算法是对列表进行排序的有效方法。尽管它在较大列表上的性能不超过合并排序,但在较小列表上使用时功能强大。

快速排序是使用递归函数实现的。这是一个反复调用自身的函数,直到问题解决为止。

标签: Java学习 Java

发表评论 (已有0条评论)

还木有评论哦,快来抢沙发吧~