java的快速排序怎么写
时间: 2023-09-10 16:04:50 浏览: 85
### 回答1:
Java 快速排序的代码实现如下:
```
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 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;
}
}
```
代码中定义了三个函数:quickSort,partition 和 swap。
- `quickSort` 函数是主要的排序递归函数,它不断递归地将数组分成两个部分,直到每个部分只剩下一个元素为止。
- `partition` 函数负责把数组分成两个部分,左边的部分元素都小于等于 pivot,右边的部分元素都大于 pivot。
- `swap` 函数用于交换数组中两个元素的位置。
### 回答2:
快速排序(Quick Sort)是一种高效的排序算法,通过将数组分成较小和较大的两个子数组,递归地对子数组进行排序,最终得到整个数组有序。以下是一个使用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 = {8, 3, 9, 6, 1, 4, 2, 7, 5};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序结果:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
以上代码实现了快速排序算法。首先定义了`quickSort`方法来执行快速排序,该方法接受数组、起始索引和终止索引作为参数。在`quickSort`方法中,首先进行判断,如果起始索引小于终止索引,则执行以下步骤:
- 调用`partition`方法获取基准元素的索引。
- 对基准元素左侧的子数组进行递归调用快速排序(即`quickSort(arr, low, pivot - 1)`)。
- 对基准元素右侧的子数组进行递归调用快速排序(即`quickSort(arr, pivot + 1, high)`)。
`partition`方法用于划分数组,接受数组和起始、终止索引作为参数。在`partition`方法中,首先取第一个元素为基准元素,并使用两个指针从数组的两端开始移动,直到指针相遇。在移动指针的过程中,根据指针所指元素与基准元素的大小关系,将比基准元素小的元素放到基准元素的左侧,将比基准元素大的元素放到基准元素的右侧。最后将基准元素放到最终位置,并返回基准元素的索引。
在`main`方法中,定义了一个测试数组,并通过调用`quickSort`方法进行快速排序。最后输出排序结果。
### 回答3:
快速排序是一种常用的排序算法,它通过选择一个基准元素,将数据分为两个子序列,然后对子序列分别进行递归排序,最终将整个序列有序排列。下面是一个简单的Java实现快速排序的代码:
```
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high); // 划分数组,并获取基准元素所在位置
quickSort(arr, low, pivotIndex - 1); // 对左子序列进行排序
quickSort(arr, pivotIndex + 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 = { 6, 1, 3, 8, 4, 2, 9, 5, 7 };
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
在快速排序中,通过划分数组并选择基准元素的方法将数据分为两个部分。然后,通过递归调用对左右子序列进行排序,最终完成整个数组的排序。在划分数组的过程中,通过两个指针分别从数组的两端向中间移动,找到需要交换的元素,并将它们进行交换。最后,将基准元素放在最终位置,返回基准元素所在的位置。通过不断递归调用划分和排序的过程,最终完成整个数组的排序。
阅读全文