java实现快速排序算法
时间: 2023-07-03 15:31:18 浏览: 45
好的,以下是 Java 实现快速排序算法的代码:
```java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = { 10, 7, 8, 9, 1, 5 };
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println(Arrays.toString(arr));
}
}
```
在这个实现中,我们使用递归的方式来实现快速排序算法。我们首先选择一个元素作为枢轴元素(在这个实现中,我们选择最后一个元素作为枢轴元素),并将数组分为两个子数组:小于枢轴元素的元素和大于枢轴元素的元素。
然后,我们递归地对两个子数组进行快速排序,直到整个数组被排序。在每个递归步骤中,我们使用 `partition()` 方法来分割数组,并返回枢轴元素的索引。
在 `partition()` 方法中,我们使用了两个指针来遍历数组,`i` 用于追踪小于枢轴元素的元素的位置,`j` 用于迭代数组。如果 `arr[j]` 小于枢轴元素,则将 `arr[j]` 和 `arr[i]` 交换位置,并将 `i` 增加 1。
最后,我们将枢轴元素与 `arr[i+1]` 交换位置,以便将枢轴元素放到正确的位置上。这样,我们就完成了一次分割操作。