给我写个快速排序的Java代码
时间: 2023-09-11 21:05:13 浏览: 50
### 回答1:
好的,以下是快速排序的Java代码:
```
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
}
private 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;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
```
这是一个基于递归的快速排序算法,它的时间复杂度为O(nlogn)。
### 回答2:
快速排序是一种经典的排序算法,它通过分治的策略将待排序数组分成两个子数组,然后分别对这两个子数组进行排序,最终将排好序的子数组合并起来。下面是一个使用Java实现的快速排序代码:
```java
public class QuickSort {
public static void main(String[] args) {
int[] arr = {9, 5, 7, 4, 2, 8, 1, 10, 6, 3};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
while (low < high) {
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
}
```
上述代码中,首先定义了一个`quickSort`方法来进行递归的快速排序。其中`low`表示待排序数组的起始位置,`high`表示结束位置。在每次递归中,通过调用`partition`方法来确定一个基准点`pivot`,将数组分为左子数组和右子数组。然后再对左右子数组进行递归排序。
`partition`方法通过将小于基准点的元素移到左边,大于基准点的元素移到右边,最终将基准点放到正确的位置上。这里使用了双指针的方法来实现。
### 回答3:
下面是一个使用快速排序算法的Java代码:
```java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1); // 对左侧子数组进行快速排序
quickSort(arr, pivotIndex + 1, high); // 对右侧子数组进行快速排序
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 将最右边的元素设置为pivot
int i = low - 1; // 定义一个指针,初始指向low的前一个位置
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high); // 将pivot放到正确的位置上
return i + 1; // 返回pivot的索引
}
private 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, 3, 2, 8, 7, 1};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
这个快速排序的实现使用了递归来对数组进行排序。首先,我们选择一个基准元素(pivot),将数组分为两部分,左边的元素小于基准元素,右边的元素大于基准元素。然后,对左右两部分分别进行递归排序,直到整个数组有序。最后,我们通过交换元素的方式来完成分区过程,即将比pivot小的元素交换到左边,比pivot大的元素交换到右边。