java实线快速排序算法
时间: 2023-06-21 17:10:22 浏览: 53
快速排序(Quicksort)是一种常用的基于比较的排序算法,它的核心思想是通过分治的方式将待排序序列分成小的子序列,然后对每个子序列进行排序,最终合并成完整的有序序列。
在Java中,快速排序的实现代码如下:
```java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
while (low < high) {
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
public static void main(String[] args) {
int[] arr = {3, 1, 7, 5, 2, 4, 9, 6, 8};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
```
其中,`quickSort` 方法是排序的入口方法,它接受一个待排序的数组 `arr`,以及数组的起始下标 `low` 和终止下标 `high`,表示待排序序列的区间范围。在 `quickSort` 方法中,首先通过调用 `partition` 方法将待排序序列分成两个子序列,然后递归地对每个子序列进行排序,最终完成整个排序过程。
`partition` 方法是快速排序的核心方法,它接受一个待排序的数组 `arr`,以及数组的起始下标 `low` 和终止下标 `high`,表示待排序序列的区间范围。在 `partition` 方法中,首先选取序列的第一个元素作为基准元素 `pivot`,然后通过指针 `low` 和 `high` 分别从序列的两端向中间扫描,找到两个需要交换的元素,并将它们交换位置,直到指针 `low` 和 `high` 相遇为止。最后,将基准元素 `pivot` 与指针 `low` 指向的元素交换位置,并返回指针 `low` 的值作为基准元素的最终位置。
在 `main` 方法中,我们先定义一个待排序的数组 `arr`,然后调用 `quickSort` 方法对数组进行排序,并使用 `Arrays.toString` 方法将排序后的数组转换成字符串形式输出。