java的快速排序怎么写?
时间: 2023-09-17 19:06:24 浏览: 77
### 回答1:
快速排序是一种分治的排序算法,它将一个数组分成两个子数组,左边的子数组的元素都比右边的子数组的元素小,然后对左右两个子数组分别递归地调用快速排序。
以下是Java实现的快速排序代码示例:
```
public class QuickSort {
public static void quickSort(int[] array, int start, int end) {
if (start < end) {
int pivotIndex = partition(array, start, end);
quickSort(array, start, pivotIndex - 1);
quickSort(array, pivotIndex + 1, end);
}
}
private static int partition(int[] array, int start, int end) {
int pivot = array[end];
int i = start - 1;
for (int j = start; j < end; j++) {
if (array[j] <= pivot) {
i++;
swap(array, i, j);
}
}
swap(array, i + 1, end);
return i + 1;
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
```
使用时,调用`QuickSort.quickSort(array, 0, array.length - 1)`即可将数组`array`排序。
### 回答2:
在Java中,快速排序算法的实现步骤如下:
1. 首先,选择数组中的一个元素作为基准值(pivot)。
2. 将数组分为两部分,一部分包含小于等于基准值的元素,另一部分包含大于基准值的元素(通常称为划分过程)。
3. 对两个子数组分别递归地应用快速排序算法,直到每个子数组的长度为1或0时停止递归。
4. 将排序后的子数组重新合并,得到最终排序好的数组。
以下是一个使用递归方式实现的快速排序的Java代码示例:
```java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIdx = partition(arr, low, high); // 划分数组,获取基准值的索引位置
quickSort(arr, low, pivotIdx - 1); // 递归排序基准值左边的子数组
quickSort(arr, pivotIdx + 1, high); // 递归排序基准值右边的子数组
}
}
public static int partition(int[] arr, int low, int high) {
int pivotValue = arr[high]; // 选择数组最后一个元素作为基准值
int i = low - 1; // 记录小于等于基准值的元素应该放置的位置
for (int j = low; j < high; j++) {
if (arr[j] <= pivotValue) {
i++;
swap(arr, i, j); // 将小于等于基准值的元素交换到左侧
}
}
swap(arr, i + 1, high); // 将基准值交换到合适的位置
return i + 1;
}
public static void swap(int[] arr, int idx1, int idx2) {
int temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
}
```
可以使用以下代码进行测试:
```java
public class Main {
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 7};
QuickSort.quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
这样就可以实现快速排序算法并得到排序后的数组。
### 回答3:
快速排序(QuickSort)是一种基于分治思想的排序算法,其核心idea是选择一个基准元素,通过一轮排序将数组分割成两个子数组,其中一个子数组中的元素都小于基准元素,另一个子数组中的元素都大于等于基准元素。然后递归地对这两个子数组进行排序,直到子数组的长度为0或1,排序完成。
下面是用Java语言实现快速排序的代码:
```
public static void quickSort(int[] array, int left, int right) {
if (left < right) {
int pivot = partition(array, left, right); // 调用partition函数获取基准元素的位置
quickSort(array, left, pivot - 1); // 对基准元素左边的子数组进行排序
quickSort(array, pivot + 1, right); // 对基准元素右边的子数组进行排序
}
}
public static int partition(int[] array, int left, int right) {
int pivot = array[left]; // 选择第一个元素作为基准元素
int i = left, j = right;
while (i < j) {
while (i < j && array[j] >= pivot) {
j--; // 从右侧找到第一个小于基准元素的位置
}
if (i < j) {
array[i] = array[j]; // 将找到的小于基准元素的值放到左侧
i++;
}
while (i < j && array[i] < pivot) {
i++; // 从左侧找到第一个大于等于基准元素的位置
}
if (i < j) {
array[j] = array[i]; // 将找到的大于等于基准元素的值放到右侧
j--;
}
}
array[i] = pivot; // 将基准元素放到正确的位置
return i;
}
// 测试示例
public static void main(String[] args) {
int[] array = {5, 6, 2, 8, 1, 9, 3, 7, 4};
quickSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array)); // 输出:[1, 2, 3, 4, 5, 6, 7, 8, 9]
}
```
以上是一个简单的快速排序实现,通过递归的方式对左右子数组进行排序,直到子数组的长度为0或1时排序完成。在partition函数中,通过设置一个基准元素来分割数组,并通过双指针在数组中遍历,不断交换元素,将小于基准元素和大于等于基准元素的元素分别放到数组的左右两侧。最后,将基准元素放到正确的位置上,完成一轮排序。