java实现一个快速排序
时间: 2023-06-29 14:09:43 浏览: 49
快速排序(Quicksort)是一种常用的排序算法,基于分治的思想,它的基本思路是:选择一个基准元素并将序列分为两部分,一部分比基准元素小,另一部分比基准元素大,然后递归地对这两部分分别进行快速排序。
以下是使用 Java 实现快速排序的示例代码:
```java
public class QuickSort {
public static void sort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
sort(arr, left, pivotIndex - 1);
sort(arr, pivotIndex + 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;
}
public static void main(String[] args) {
int[] arr = {5, 2, 6, 9, 1, 4, 8, 3, 7};
sort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
```
在上面的示例代码中,`sort()` 方法接收一个整型数组和数组的左右边界作为参数,递归地对数组进行快速排序。`partition()` 方法通过选择最右边的元素作为基准元素,将数组分为两部分,并返回基准元素的位置。`swap()` 方法用于交换数组中的元素。在 `main()` 方法中,我们创建了一个整型数组并对其进行排序,最后输出排序后的结果。