Java的快速排序怎么写
时间: 2023-08-31 20:33:41 浏览: 45
### 回答1:
Java中的快速排序可以使用以下代码实现:
public class QuickSort {
public static void quickSort(int[] arr, int start, int end) {
int partition = partition(arr, start, end);
if(partition-1>start) {
quickSort(arr, start, partition - 1);
}
if(partition+1<end) {
quickSort(arr, partition + 1, end);
}
}
public static int partition(int[] arr, int start, int end) {
int pivot = arr[end];
for(int i=start; i<end; i++) {
if(arr[i]<pivot) {
int temp= arr[start];
arr[start]=arr[i];
arr[i]=temp;
start++;
}
}
int temp = arr[start];
arr[start] = pivot;
arr[end] = temp;
return start;
}
}
### 回答2:
快速排序是一种常见的排序算法,它通过选择一个基准元素,将待排序的序列分成两个子序列,使得左边的元素都小于或等于基准元素,右边的元素都大于或等于基准元素,然后递归地对子序列进行排序,最终得到有序序列。
下面是使用Java实现快速排序的示例代码:
```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]; // 选择第一个元素作为基准元素
int left = low + 1; // 左指针
int right = high; // 右指针
while (left <= right) {
// 找到左边比基准元素大的元素
while (left <= right && arr[left] <= pivot) {
left++;
}
// 找到右边比基准元素小的元素
while (left <= right && arr[right] > pivot) {
right--;
}
// 如果左指针小于右指针,则交换这两个元素
if (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
// 将基准元素放到正确的位置上
int temp = arr[low];
arr[low] = arr[right];
arr[right] = temp;
return right; // 返回基准元素的索引
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println("排序后的数组:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
```
运行以上代码,输出结果为:1 5 7 8 9 10,表示数组已经按照从小到大的顺序排序好了。
### 回答3:
快速排序是一种常用的排序算法,其基本原理是选择一个元素作为基准,将数组分为两部分,较小的元素放在基准的左边,较大的元素放在基准的右边,再递归地对左右两部分进行快速排序。
以下是使用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); // 对右子数组进行快速排序
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[low]; // 选取第一个元素作为基准
int i = low, j = high;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i++] = arr[j];
}
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
}
arr[i] = pivot;
return i;
}
public static void main(String[] args) {
int[] arr = {8, 3, 2, 9, 7, 1, 5, 4, 6};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组为:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
这段代码实现了快速排序的逻辑。`quickSort`方法是快速排序的入口,它将数组分为两部分,并递归地对左右两部分进行排序。`partition`方法是分割数组的过程,选取第一个元素作为基准,通过移动左右指针来找到基准的最终位置,并将数组分割成两部分。
在`main`方法中,我们初始化一个整数数组,并调用`quickSort`方法对数组进行排序。最后,打印排序后的数组。
快速排序的时间复杂度为O(nlogn),是一种高效的排序算法。