快速排序 java代码
时间: 2023-09-23 22:02:30 浏览: 20
以下是一种快速排序的 Java 代码实现:
```java
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 7, 6, 1, 8, 4};
quickSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void quickSort(int[] arr, int start, int end) {
if (start < end) {
int partitionIndex = partition(arr, start, end);
quickSort(arr, start, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, end);
}
}
public static int partition(int[] arr, int start, int end) {
int pivot = arr[end];
int i = start - 1;
for (int j = start; j < end; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, end);
return i + 1;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
这个实现使用了递归和原地排序的思想,其中 `quickSort` 方法是主要的排序方法,它接受要排序的数组以及数组的起始和结束索引。如果起始索引小于结束索引,就找到数组的中心元素(通过 `partition` 方法),然后递归地对中心元素左边和右边的子数组进行排序。 `partition` 方法使用了双指针的思想,将数组分为两部分,左边部分的元素都小于或等于中心元素,右边部分的元素都大于中心元素。最后,交换中心元素和右部分的第一个元素。 `swap` 方法用于交换数组中的两个元素。