用Java写一个快速排序
时间: 2023-05-28 20:01:16 浏览: 45
以下是Java语言实现快速排序的代码:
``` java
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[] { 5, 1, 9, 3, 7, 4, 8, 6, 2 };
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 pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
}
public static int partition(int[] arr, int left, int right) {
int pivotIndex = left + (right - left) / 2;
int pivotValue = arr[pivotIndex];
int i = left;
int j = right;
while (i <= j) {
while (arr[i] < pivotValue) {
i++;
}
while (arr[j] > pivotValue) {
j--;
}
if (i <= j) {
swap(arr, i, j);
i++;
j--;
}
}
return i;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
解释:快速排序使用分治法来进行排序,首先选取一个基准点(pivot),然后把数组分为两个部分,左边部分的元素值不超过基准点,右边部分的元素值超过等于基准点。然后对左右两部分分别进行递归排序,最终得到有序的数组。
在实现中,我们定义了一个`quickSort`方法,它接受数组、左右边界作为参数。如果左下标小于右下标,则进行分治排序。在分治中,我们定义了一个`partition`方法,它接受数组和左右边界作为参数,它使用基准点来划分数组,并返回基准点位置。在`partition`方法中,我们首先选用中间位置的值作为基准点,然后用两个指针(i和j)进行扫描,将比基准点小的值交换到左边,将比基准点大的值交换到右边,最终返回基准点的位置。在交换时,我们定义了一个`swap`方法,它用于交换数组中的两个值。
最后在main函数中测试我们的快速排序的实现代码。