用java写一个快速排序
时间: 2023-05-24 20:04:01 浏览: 73
用java实现快速排序
好的,下面给出用Java实现的快速排序算法:
```java
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
private static int partition(int[] arr, int left, int right) {
int pivotValue = arr[left];
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivotValue) {
j--;
}
arr[i] = arr[j];
while (i < j && arr[i] <= pivotValue) {
i++;
}
arr[j] = arr[i];
}
arr[i] = pivotValue;
return i;
}
```
以上就是快速排序算法的Java实现,其中 `quickSort` 方法是递归实现的快速排序,而 `partition` 方法则是划分数组的过程。在这个过程中,我们选择数组的第一个元素作为基准值,然后从数组的两端分别向中间扫描,将比基准值小的元素移到左边,将比基准值大的元素移到右边,最后将基准值插入到数组的中间位置。
需要注意的是,这个实现会修改原数组,如果不想修改原数组,可以使用一份拷贝来进行排序。
测试代码:
```java
int[] arr = {5, 8, 1, 3, 9, 6};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
```
输出结果:
```
[1, 3, 5, 6, 8, 9]
```
阅读全文