Java 中的快速排序

快速排序是一种利用分治技术的排序算法。它选择一个基准元素，并将其放在已排序数组的适当位置。

分治是一种将算法分解为子问题，然后解决子问题，最后将结果组合起来以解决原始问题的技术。

• 划分：在划分中，首先选择一个基准元素。然后，将数组划分为两个子数组，使得左子数组中的每个元素都小于或等于基准元素，而右子数组中的每个元素都大于基准元素。
• 征服：使用快速排序递归地对两个子数组进行排序。
• 合并：合并已排序的数组

快速排序的步骤

步骤 1：选择基准元素。通常，选择第一个、最后一个或中间元素作为基准元素。

步骤 2：进行数组划分。为此，围绕基准元素重新排列数组中的元素。划分后，基准元素左侧的元素（左子数组）小于基准元素，基准元素右侧的元素（右子数组）大于基准元素。

步骤 3：对左子数组和右子数组重复上述步骤。这可以通过递归完成。当子数组只剩一个元素时，递归停止。因为单个元素已经排序。

算法

快速排序算法的工作原理

实现快速排序的简单步骤如下。

步骤 1：选择基准元素。通常，选择第一个、最后一个或中间元素作为基准元素。在本例中，我们取最后一个元素作为基准。另外，取两个指针 j 和 k，其中 j 的值为 -1，k 指向数组的第 0 个索引。移动 j 指针，使得 j 指针指向的元素以及 j 指针左侧的元素都小于基准元素。

步骤 2：将 a[k]（值为 19）与基准元素进行比较。我们看到 a[k] > 基准元素。因此，将 k 增加 1。现在，k 指向第 1 个索引。

步骤 3：将 a[k]（值为 4）与基准元素进行比较。我们看到 a[k] < 基准元素。因此，将 j 增加 1。现在，j 指向第 0 个索引。

步骤 4：交换 a[j] 和 a[k]，并将 k 增加 1。现在，k 指向第 2 个索引。

步骤 5：将 a[k]（值为 13）与基准元素进行比较。我们看到 a[k] < 基准元素。因此，将 j 增加 1。现在，j 指向第 1 个索引。

步骤 6：交换 a[j] 和 a[k]，并将 k 增加 1。现在，k 指向第 3 个索引。

步骤 7：将 a[k]（值为 18）与基准元素进行比较。我们看到 a[k] > 基准元素。因此，将 k 增加 1。现在，k 指向第 4 个索引。

步骤 8：将 a[k]（值为 10）与基准元素进行比较。我们看到 a[k] < 基准元素。因此，将 j 增加 1。现在，j 指向第 2 个索引。

步骤 9：交换 a[j] 和 a[k]，并将 k 增加 1。现在，k 指向第 5 个索引。

步骤 10：将 a[k]（值为 10）与基准元素进行比较。我们看到 a[k] < 基准元素。因此，将 j 增加 1。现在，j 指向第 3 个索引。

步骤 11：交换 a[j] 和 a[k]，并将 k 增加 1。现在，k 指向第 6 个索引。

步骤 12：将 a[k]（值为 15）与基准元素进行比较。我们看到 a[k] < 基准元素。因此，将 j 增加 1。现在，j 指向第 4 个索引。

步骤 13：交换 a[j] 和 a[k]。由于 k 指向最后一个元素，因此进一步的检查和交换在此停止。请注意，j 索引左侧的所有元素以及 j 索引处的元素都小于基准元素。

步骤 14：将 a[j + 1] 与基准元素交换（交换 18 和 17）。

我们看到基准元素已放置在已排序数组的正确位置。

步骤 15：根据基准元素将数组划分为左子数组和右子数组。位于基准元素左侧的元素属于左子数组，位于基准元素右侧的元素属于右子数组。

步骤 16：对左子数组和右子数组重复所有步骤。

Java 中快速排序的实现

让我们来看一下 Java 中的快速排序程序。

输出

 
The array before sorting is: 
10 7 8 9 1 5 
The array after sorting is: 
1 5 7 8 9 10

时间复杂度：程序的 O(n log n)。这是因为基准元素将数组分成两个相等的部分。

空间复杂度：平均情况下，对于递归栈，程序的空间复杂度为 O(log n)；在最坏情况下，由于深度递归，空间复杂度为 O(n)。

快速排序的优点

• 实践中速度快：对于大多数输入，与归并排序和堆排序相比，性能更好。
• 原地排序：只需要少量、恒定的额外内存。
• 尾部递归：可以由编译器优化以提高效率。
• 广泛用于库：在许多标准库中使用（例如，C，Java 的双基准快速排序用于原始数组）。

快速排序的缺点

• 最坏情况时间复杂度为 O(n²)：当基准选择不佳时发生（例如，已排序的数组）。
• 不稳定：排序后，相等的元素可能无法保留其原始顺序。
• 递归：如果没有适当的基准或递归深度处理，可能会导致大数组出现堆栈溢出。

结论

由于其速度和简单性，快速排序是最广泛使用和最高效的排序算法之一。其原地排序能力与分治方法的结合，使其适用于内存受限的系统和大型数据集。