java的快速排序怎么写?
时间: 2023-09-04 13:04:06 浏览: 116
### 回答1:
Java的快速排序实现方法如下:
```
public class QuickSort {
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length-1);
System.out.println("排序后的数组:");
for (int i : arr) {
System.out.print(i + " ");
}
}
private static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length == 0)
return;
if (low >= high)
return;
// 指定基准数
int middle = low + (high - low) / 2;
int pivot = arr[middle];
int i = low, j = high;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (low < j)
quickSort(arr, low, j);
if (high > i)
quickSort(arr, i, high);
}
}
```
### 回答2:
快速排序(Quicksort)是一种常用的排序算法,它的基本思想是通过分治法将待排序的序列分成两个子序列,再对这两个子序列递归地进行排序,最终将整个序列有序。
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); // 对右子序列递归排序
}
}
public 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 = { 9, 5, 2, 7, 1, 6, 3, 8, 4 };
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
以上代码中,`quickSort`方法实现了快速排序的递归操作。`partition`方法则用于划分数组,选择一个枢纽元(这里选择的是第一个元素),将小于枢纽元的元素移到枢纽元的低位,将大于枢纽元的元素移到枢纽元的高位。最后,将枢纽元放入最终位置,然后返回枢纽元的下标。
在`main`方法中,我们可以调用`quickSort`方法对一个整型数组进行排序。
### 回答3:
快速排序是一种常见的排序算法,基于分治思想。下面是一个简单的Java实现:
```java
public class QuickSort {
public static void main(String[] args) {
int[] arr = {9, 5, 7, 4, 2, 8, 1, 6, 3};
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
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);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = pivot;
return i;
}
}
```
以上代码首先定义了快速排序的入口函数`quickSort`,接受待排序数组、低位索引和高位索引作为参数。在`quickSort`函数中,首先判断低位索引是否小于高位索引,若成立,则调用`partition`函数确定基准元素的位置,并对基准元素的左侧和右侧进行递归调用`quickSort`函数。
`partition`函数定义了基准元素的选择和划分子数组的过程。首先选取低位索引对应的元素作为基准元素,然后定义两个指针`i`和`j`分别指向低位索引和高位索引。接下来,在两个指针相遇之前,`i`指针从左向右寻找第一个大于基准元素的元素,`j`指针从右向左寻找第一个小于基准元素的元素。若找到了这样的元素,则将它们交换位置。重复执行上述过程直到`i`指针和`j`指针相遇。最后,将基准元素放置在最终位置,并返回基准元素的索引。
以上是快速排序的一个简单实现,但并不是最优的实现方式。实际应用中,还可以通过优化选取基准元素的策略、使用随机化策略和三数取中法以及使用尾递归等方式来提高算法的性能。