用java语言写出两种快速排序的方法
时间: 2023-06-12 14:03:49 浏览: 53
快速排序是一种高效的排序算法,以下是两种使用 Java 语言实现的快速排序方法:
1. 普通快速排序
```java
public class QuickSort {
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);
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left + 1;
int j = right;
while (true) {
while (i <= j && arr[i] < pivot) {
i++;
}
while (i <= j && arr[j] >= pivot) {
j--;
}
if (i > j) {
break;
}
swap(arr, i, j);
}
swap(arr, left, j);
return j;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
2. 三路快速排序
```java
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = arr[left];
int lt = left + 1;
int gt = right;
int i = left + 1;
while (i <= gt) {
if (arr[i] < pivot) {
swap(arr, i, lt);
i++;
lt++;
} else if (arr[i] > pivot) {
swap(arr, i, gt);
gt--;
} else {
i++;
}
}
swap(arr, left, lt - 1);
quickSort(arr, left, lt - 2);
quickSort(arr, gt + 1, right);
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
以上是两种常用的快速排序算法,其中三路快速排序在处理大量重复元素的情况下更为高效。