写一个快速排序代码使用java
时间: 2024-05-19 10:13:18 浏览: 11
以下是使用Java编写的快速排序代码:
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 2, 6, 1, 3, 9};
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 pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(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;
}
}
在这个代码中,我们使用了递归的方式实现了快速排序。首先我们选择一个元素作为枢轴(pivot),然后将数组分成两个部分,一部分比pivot小,一部分比pivot大。然后递归地对这两个部分进行快速排序,直到整个数组有序。在partition方法中,我们使用了双指针的方式,i表示小于pivot的元素的右边界,j表示当前扫描到的元素。如果当前元素小于pivot,我们将i右移一位,并且将当前元素和i指向的元素进行交换,确保i右边的元素都比pivot大。最后将pivot和i+1指向的元素进行交换,完成一次partition操作。