快速排序java
时间: 2023-06-21 17:07:34 浏览: 43
以下是Java中的快速排序算法实现:
```java
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 6, 8, 1, 7};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
}
public static int partition(int[] arr, int left, int right) {
// 将数组的第一个元素作为基准值
int pivot = arr[left];
int i = left;
int j = right;
while (i < j) {
// 从右侧开始找到第一个比基准值小的元素
while (i < j && arr[j] >= pivot) {
j--;
}
// 从左侧开始找到第一个比基准值大的元素
while (i < j && arr[i] <= pivot) {
i++;
}
// 如果i < j,则交换这两个元素
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将基准值与i位置的元素交换
arr[left] = arr[i];
arr[i] = pivot;
return i;
}
}
```
在快速排序中,我们首先选择一个基准值,通常选择第一个元素。然后,我们将数组分为两部分:左边的部分包含所有小于基准值的元素,右边的部分包含所有大于基准值的元素。我们递归地将左半部分和右半部分排序,直到整个数组都被排序。