帮我写一个快速排序,用Java
时间: 2023-08-28 14:17:31 浏览: 58
### 回答1:
好的,以下是一个快速排序的Java代码:
```
import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] arr, int start, int end) {
if (start < end) {
int partitionIndex = partition(arr, start, end);
quickSort(arr, start, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, end);
}
}
private static int partition(int[] arr, int start, int end) {
int pivot = arr[end];
int i = start - 1;
for (int j = start; j < end; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, end);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}
```
希望这个代码对你有帮助!
### 回答2:
下面是一个使用Java实现的快速排序算法:
```
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 7, 6, 3};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组:" + Arrays.toString(arr));
}
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); // 对基准元素的右边子数组进行快速排序
}
}
public static int partition(int[] arr, int left, int right) {
int pivotIndex = left; // 将最左边的元素作为基准元素
int pivot = arr[left];
while (left < right) {
// 从右边开始找到第一个小于基准元素的数
while (left < right && arr[right] >= pivot) {
right--;
}
// 将小于基准元素的数放到左边
if (left < right) {
arr[left] = arr[right];
left++;
}
// 从左边开始找到第一个大于基准元素的数
while (left < right && arr[left] <= pivot) {
left++;
}
// 将大于基准元素的数放到右边
if (left < right) {
arr[right] = arr[left];
right--;
}
}
// 将基准元素放到最终位置
arr[left] = pivot;
return left; // 返回基准元素的索引
}
}
```
快速排序是一种基于分治的排序算法。它选择一个基准元素,将数组中小于基准元素的数放在基准元素的左边,大于基准元素的数放在基准元素的右边,然后再对左右两边的子数组进行递归排序,最终得到有序的数组。快速排序具有平均时间复杂度为O(nlogn),是一种高效的排序算法。
### 回答3:
当然可以!下面是一个使用Java编写的快速排序算法:
```java
public class QuickSort {
public static void main(String[] args) {
int[] nums = {5, 2, 8, 7, 1, 3};
quickSort(nums, 0, nums.length - 1);
System.out.println("排序后的数组:");
for (int num : nums) {
System.out.print(num + " ");
}
}
public static void quickSort(int[] nums, int low, int high) {
if (low < high) {
int pivotIndex = partition(nums, low, high);
quickSort(nums, low, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, high);
}
}
public static int partition(int[] nums, int low, int high) {
int pivot = nums[low];
int i = low + 1;
int j = high;
while (i <= j) {
if (nums[i] <= pivot) {
i++;
} else if (nums[j] > pivot) {
j--;
} else {
swap(nums, i, j);
}
}
swap(nums, low, j);
return j;
}
public static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
```
这个程序会输出排序后的数组:1 2 3 5 7 8。快速排序的时间复杂度为O(nlogn),对于大型数据集非常高效。