Java中的快速排序算法

java中的快速排序，也称为分区交换排序，是一种分而治之的排序算法。快速排序是最好地利用 CPU 缓存的算法的一个很好的例子，因为它具有分而治之的性质。快速排序算法是最常用的排序算法之一，尤其是对大型列表进行排序，并且大多数编程语言都实现了它。快速排序算法将原始数据分为两部分：单独排序，然后合并产生排序数据。

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

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

让我们考虑数组 {8, 6, 3, 4, 9, 2, 1, 7} 需要使用快速排序进行排序。

实现快速排序算法的步骤

1.从数组中选择一个名为“枢轴”的元素。一般情况下，选择中间的元素作为枢轴。让我们以 4 为基准。

2.将数组重新排列为两部分，使得小于主元的元素出现在主元之前，大于主元的元素出现在主元之后。遵循以下步骤：

• 选取最左边的元素，即8；由于4是枢轴，而8比4大，所以8需要移到4的右侧；在右侧，我们保留 7，因为它大于 4，并选择 1 与 8 交换，因此交换后数组变为： 1,6,3,4,9,2,8,7
• 选取左下一个元素，即 6；由于4是枢轴，并且6比4大，所以6需要移到4的右侧；在右侧，我们保留 7,8，因为它们大于 4，并选择 2 与 6 交换，因此交换后数组变为：1,2,3,4,9,6,8,7
• 现在，由于主元左侧的所有元素都小于主元，并且主元右侧的所有元素都大于主元，因此我们以 4 作为主元。

3.对左子数组（元素少于主元的数组）和右子数组（元素多于主元的数组）递归应用步骤 1 和 2。如果数组仅包含一个或零个元素，则该数组被视为分类数组。

实现快速排序算法的程序

这是一个使用快速排序算法对整数数组进行排序的 java 程序。

代码：

import java.lang.*;
import java.util.*;
public class Main {
private int array[];
private int length;
public void sort(int[] inputArrayArr) {
if (inputArrayArr == null || inputArrayArr.length == 0) {
return;
}
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
}
private void performQuickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two subarrays
while (i <= j) {
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
}
private void swapNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String args[]){
Main quickSort = new Main();
int[] inputArray = {8,6,3,4,9,2,1,7};
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
}
}

输出：

快速排序算法的优点

以下是快速排序算法的优点：

• 优秀的引用局部性：引用局部性是处理器在短时间内重复访问同一内存位置的能力。 Java 中的快速排序由于缓存未命中次数极少而提供了出色的引用局部性，这在现代架构中对于性能至关重要。
• 快速排序是可并行的：一旦完成将数组划分为较小区域的初始步骤，所有单独的子数组都可以并行独立排序。由于这个原因，快速排序性能更好。

快速排序的复杂度分析

快速排序是一种快速尾递归算法，遵循分治原则。以下是最佳、平均和最坏情况下的复杂度分析：

• 最佳情况复杂度：如果数组或列表包含 n 个元素，则第一次运行将需要 O(n)。现在对剩余的两个子数组进行排序需要 2*O (n/2)。由此得出最好情况下复杂度为 O(n logn) 的结论。
• 平均情况复杂度：快速排序的平均情况为 O (n log n)。
• 最坏情况复杂性：选择第一个或最后一个会导致近排序或近逆排序数据的最坏情况性能。快速排序在最坏的情况下执行 O(n^2)。

 在 Java 中，数组。 Sort() 方法使用快速排序算法对数组进行排序。

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