java的快速排序怎么写
时间: 2023-09-17 08:05:55 浏览: 52
### 回答1:
Java中的快速排序代码如下:
```
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] nums = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
quickSort(nums, 0, nums.length - 1);
System.out.println(Arrays.toString(nums));
}
public static void quickSort(int[] nums, int left, int right) {
if (left < right) {
int pivotIndex = partition(nums, left, right);
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
}
}
public static int partition(int[] nums, int left, int right) {
int pivot = nums[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (nums[j] < pivot) {
i++;
swap(nums, i, j);
}
}
swap(nums, i + 1, right);
return i + 1;
}
public static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
```
快速排序是一种分治算法,它通过不断选取枢轴(pivot)将原数组分为两个子数组,然后递归地对子数组进行排序,直到所有子数组都有序为止。
该代码实现了快速排序的基本流程,其中`quickSort`函数实现了递归调用,`partition`函数实现了对数组的划分。
### 回答2:
快速排序是一种常用的排序算法,其基本思想是通过分治的思想将待排序的数组分为两部分,然后分别对这两部分进行递归排序。下面是Java中实现快速排序的示例代码:
```java
public class QuickSort {
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
int pivot = partition(array, low, high); // 划分操作,将数组分为左右两部分
quickSort(array, low, pivot - 1); // 递归排序左子数组
quickSort(array, pivot + 1, high); // 递归排序右子数组
}
}
private static int partition(int[] array, int low, int high) {
int pivot = array[low]; // 选取第一个元素作为基准值
while (low < high) {
while (low < high && array[high] >= pivot) {
high--;
}
array[low] = array[high]; // 将比基准值小的元素放到左边
while (low < high && array[low] <= pivot) {
low++;
}
array[high] = array[low]; // 将比基准值大的元素放到右边
}
array[low] = pivot; // 将基准值放到正确位置
return low; // 返回基准值的位置
}
public static void main(String[] args) {
int[] array = {6, 5, 3, 8, 1, 9, 2, 7, 4};
quickSort(array, 0, array.length - 1);
for (int num : array) {
System.out.print(num + " ");
}
}
}
```
上述代码中,快速排序的主要逻辑在`quickSort()`和`partition()`两个方法中。`quickSort()`方法用于递归地对数组进行排序,`partition()`方法则是进行划分操作,将数组分为两部分。在划分过程中,选取第一个元素作为基准值,然后通过两个指针`low`和`high`从左右两端向中间扫描,将比基准值小的元素放到左边,将比基准值大的元素放到右边,直到`low`和`high`相遇。最后将基准值放到正确的位置上,然后对左右两个子数组进行递归排序。
以上是快速排序的一个基本实现,其时间复杂度为O(nlogn),是一种高效的排序算法。
### 回答3:
快速排序是一种常用的排序算法,其基本思想是通过将数组分割成较小的部分,并对这些部分进行递归排序来达到整体有序的目的。下面是一个用Java实现快速排序的示例:
```java
public class QuickSort {
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;
}
public static void main(String[] args) {
int[] arr = {4, 2, 6, 8, 3, 1, 5, 7};
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
上述代码中,我们首先定义了一个`quickSort`方法来执行快速排序。在此方法中,我们首先判断左下标是否小于右下标,如果成立,则获取分区点的位置`partitionIndex`,然后递归调用`quickSort`方法分别对分区点左侧和右侧的子数组进行排序。
在`partition`方法中,我们选择最右侧的元素作为分区点`pivot`,然后使用两个指针`i`和`j`,从左到右遍历数组元素,如果当前元素小于等于分区点的值,就将其和`i`指针所指的元素交换位置。最后,将分区点和`i`指针所指的元素交换位置,并返回`i + 1`作为新的分区点的位置。
最后,我们在`main`方法中定义一个数组`arr`并调用`quickSort`方法进行排序,然后输出排序结果。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)