java的快速排序怎么写
时间: 2023-09-08 07:04:56 浏览: 43
### 回答1:
Java的快速排序实现方式如下:
```
public static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length == 0)
return;
if (low >= high)
return;
// 挑选基准元素
int middle = low + (high - low) / 2;
int pivot = arr[middle];
// 将小于等于基准的元素移到左边,大于基准的元素移到右边
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--;
}
}
// 递归排序左半边
if (low < j)
quickSort(arr, low, j);
// 递归排序右半边
if (high > i)
quickSort(arr, i, high);
}
```
请注意,这只是一种快速排序的实现,有其他不同的写法。
### 回答2:
快速排序是一种常用的排序算法,也是Java语言中常用的排序算法之一。下面是一个用Java实现快速排序的示例代码:
```
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length == 0) {
return;
}
if (low >= high) {
return;
}
// 选择中间元素作为基准值
int middle = low + (high - low) / 2;
int pivot = arr[middle];
// 分割数组,小于基准值的放在左边,大于基准值的放在右边
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--;
}
}
// 递归排序左右两个子数组
if (low < j) {
quickSort(arr, low, j);
}
if (high > i) {
quickSort(arr, i, high);
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 9, 1, 3};
int low = 0;
int high = arr.length - 1;
quickSort(arr, low, high);
System.out.println("排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
快速排序的基本思想是通过一趟排序将数组分成两个部分,其中一部分的所有元素都小于另一部分的所有元素,然后再分别对这两个部分进行递归排序,最终得到有序的结果。通过不断地将基准值与其他元素进行比较和交换位置,最终实现排序。
### 回答3:
快速排序是一种高效的排序算法,它基于分治的思想。下面是一个使用Java编写的快速排序算法示例:
```java
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
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);
}
}
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;
}
}
```
快速排序算法的核心是`quickSort`方法和`partition`方法。`quickSort`方法用于递归地对左右两个子数组进行排序,直到子数组的长度为1。`partition`方法用于选择一个枢纽元素(这里选择最右边的元素),并将数组划分为两个部分,左边的部分小于枢纽元素,右边的部分大于枢纽元素。然后将枢纽元素放到合适的位置,使得枢纽元素左边的元素都小于它,右边的元素都大于它。
上述代码实现了快速排序算法,并对输入数组进行排序。输出结果为`2 3 4 5 8`,表示数组已经按升序排序完成。快速排序算法的平均时间复杂度为O(nlogn),是常用的排序算法之一。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![xlsm](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)