用java写快速排序
时间: 2023-09-07 08:04:56 浏览: 101
### 回答1:
快速排序是一种分治算法,它将一个数组分成两个子数组,左边的子数组中的元素都比右边的小。
```java
import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length == 0)
return;
if (low >= high)
return;
// pick the pivot
int middle = low + (high - low) / 2;
int pivot = arr[middle];
// make left < pivot and right > pivot
int i = low, j = high;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// recursively sort two sub parts
if (low < j)
quickSort(arr, low, j);
if (high > i)
quickSort(arr, i, high);
}
public static void main(String[] args) {
int[] arr = { 3, 2, 1, 4, 5 };
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
```
### 回答2:
快速排序是一种常见的排序算法,它通过选择一个基准元素将数组分成两个子数组,然后对子数组进行递归排序,最后将排序好的子数组合并起来。
以下是使用Java编写的快速排序算法的示例代码:
```java
public class QuickSort {
public static void main(String[] args) {
int[] array = { 5, 3, 8, 4, 2 };
quickSort(array, 0, array.length - 1);
System.out.println("排序结果:");
for (int num : array) {
System.out.print(num + " ");
}
}
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
int pivotIndex = partition(array, low, high); // 将数组划分为两个子数组
quickSort(array, low, pivotIndex - 1); // 对左子数组进行递归排序
quickSort(array, pivotIndex + 1, high); // 对右子数组进行递归排序
}
}
public static int partition(int[] array, int low, int high) {
int pivot = array[high]; // 选择最后一个元素作为基准元素
int i = low - 1;
for (int j = low; j < high; j++) {
if (array[j] < pivot) {
i++;
swap(array, i, j); // 交换元素
}
}
swap(array, i + 1, high); // 将基准元素放到合适的位置
return i + 1;
}
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
```
以上代码首先通过`quickSort`方法进行快速排序,划分子数组的过程在`partition`方法中完成。排序结束后,会输出排序结果。
快速排序是一种高效的排序算法,平均时间复杂度为O(nlogn)。通过选择合适的基准元素,可以进一步提高排序效率。
### 回答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[(low + high) / 2];
int i = low - 1; // i指向小于基准元素的位置
for (int j = low; j <= high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j); // 将小于基准元素的元素交换到前面
}
}
swap(arr, i + 1, high); // 将基准元素交换到正确的位置
return i + 1; // 返回基准元素的位置
}
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 = {4, 2, 9, 6, 1, 7, 5};
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " "); // 输出排序后的数组
}
}
}
```
以上代码中的`quickSort`函数是快速排序的入口函数,通过传入待排序数组和数组的起始位置和终止位置来实现快速排序。`partition`函数用于划分数组,并返回基准元素的位置。`swap`函数用于交换数组中的两个元素。在`main`函数中,我们对一个示例数组进行排序,并输出结果。