java快速排序怎么写
时间: 2023-08-31 12:37:14 浏览: 67
### 回答1:
快速排序的算法步骤如下:
1. 选择一个基准元素,通常选择第一个元素或者最后一个元素。
2. 通过一趟排序讲待排序列分割成两部分,其中一部分的所有元素均比基准元素小,另一部分的所有元素均比基准元素大。
3. 此时基准元素在其排好序后的正确位置。
4. 然后分别对这两部分用同样的方法继续进行排序,直到整个序列有序。
### 回答2:
快速排序是一种常用的排序算法,它基于分治的思想。下面是一个用Java实现快速排序的简单示例:
```java
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 1, 6, 9, 4, 7};
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 pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 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++;
// 交换元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换枢纽元素
int temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
return i + 1;
}
}
```
以上代码实现了快速排序的基本逻辑。首先使用`quickSort`方法进行递归调用,分别处理左右两个子数组。其中,`partition`方法用于确定枢纽元素,并将小于枢纽元素的元素放在左侧,大于枢纽元素的元素放在右侧。然后对左右子数组再次使用递归调用进行排序。重复这个过程,直到子数组长度为1,即已完成排序。
在上述示例中,原始数组为`{5, 2, 8, 3, 1, 6, 9, 4, 7}`。输出结果为`排序结果:1 2 3 4 5 6 7 8 9`,说明快速排序正常工作。
### 回答3:
快速排序是一种常用的排序算法,其基本思想是通过对数组不断地进行划分、比较和交换,从而达到排序的目的。
下面是一个用Java实现快速排序的示例:
```
public class QuickSort {
public void quickSort(int[] nums, int left, int right) {
if (left < right) {
int pivot = partition(nums, left, right); // 将数组划分为两个部分,返回划分点的下标
quickSort(nums, left, pivot - 1); // 对划分的左半部分进行递归排序
quickSort(nums, pivot + 1, right); // 对划分的右半部分进行递归排序
}
}
private int partition(int[] nums, int left, int right) {
int pivot = nums[right]; // 取数组最后一个元素作为划分点
int i = left - 1; // 初始时,i指向最左边的元素的前一位
for (int j = left; j < right; j++) {
if (nums[j] < pivot) {
i++;
swap(nums, i, j); // 将比划分点小的元素交换到左边
}
}
swap(nums, i + 1, right); // 将划分点放到正确的位置上
return i + 1; // 返回划分点的下标
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
public class Main {
public static void main(String[] args) {
int[] nums = {5, 2, 9, 3, 7, 1, 8, 6, 4};
QuickSort quickSort = new QuickSort();
quickSort.quickSort(nums, 0, nums.length - 1);
for (int num : nums) {
System.out.print(num + " ");
}
}
}
```
以上是一个简单的快速排序的实现。通过递归地对数组划分和排序,确保每次划分点的左侧都是比它小的元素,右侧都是比它大的元素,最终得到一个有序的数组。快速排序的时间复杂度为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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)