用java写一个快速排序
时间: 2024-03-09 18:18:19 浏览: 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);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int index = partition(arr, left, right);
quickSort(arr, left, index - 1);
quickSort(arr, index + 1, right);
}
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
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()`函数使用最右边的元素作为枢纽元素(pivot),并将数组中的元素分为两个部分,一部分小于枢纽元素,一部分大于枢纽元素。我们使用`i`变量来追踪小于枢纽元素的子数组的末尾。遍历整个数组,如果当前元素小于枢纽元素,则将其交换到小于枢纽元素的子数组的末尾。最后,我们将枢纽元素放在小于枢纽元素的子数组的末尾,并返回该位置。
在`swap()`函数中,我们简单地交换两个元素的位置。最后,在`main()`函数中,我们定义了一个测试数组,并对其执行`quickSort()`函数。