用java写一个快速排序
时间: 2023-09-12 14:05:04 浏览: 49
### 回答1:
好的,这是一个简单的 Java 实现快速排序的代码:
```java
public class QuickSort {
public static void main(String[] args) {
int[] arr = { 3, 7, 1, 4, 6, 2, 9, 8, 5 };
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int index = partition(arr, low, high);
quickSort(arr, low, index - 1);
quickSort(arr, index + 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;
}
}
```
快速排序的思路是:选取一个基准元素,将数组分为左右两个部分,左边的元素均小于基准元素,右边的元素均大于基准元素,然后对左右两个部分分别进行递归排序,直至整个数组有序。这个实现中,我们选取了数组的第一个元素作为基准元素,然后使用两个指针从两端向中间移动,不断交换元素,最终完成一轮划分。
### 回答2:
快速排序是一种常用的排序算法,其基本思想是通过选定一个基准元素,将待排序数组分成两个子数组,其中一个子数组的元素均比基准元素小,另一个子数组的元素均比基准元素大。然后递归对子数组进行排序,最终得到有序数组。
下面是用Java实现快速排序的代码:
```java
public class QuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
quickSortHelper(arr, 0, arr.length - 1);
}
private static void quickSortHelper(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivotIndex = partition(arr, left, right);
quickSortHelper(arr, left, pivotIndex - 1);
quickSortHelper(arr, pivotIndex + 1, right);
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left + 1;
int j = right;
while (i <= j) {
if (arr[i] <= pivot) {
i++;
} else if (arr[j] >= pivot) {
j--;
} else {
swap(arr, i, j);
i++;
j--;
}
}
swap(arr, left, j);
return j;
}
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, 2, 5, 1, 7, 4, 8, 3, 6};
quickSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
以上代码通过递归和分治思想实现了快速排序。在`quickSort`方法中,首先判断输入数组是否为空或长度为0,若是则直接返回;否则调用`quickSortHelper`方法进行排序。在`quickSortHelper`方法中,选定基准元素并进行分区操作,然后递归对分区后的子数组进行排序。`partition`方法用于实现分区操作,选取基准元素后,通过双指针从左右两侧向中间扫描,交换不符合要求的元素,最终返回分区位置。`swap`方法用于交换数组中两个元素的位置。最后在`main`方法中测试排序结果。
以上就是用Java编写快速排序的实现。
### 回答3:
快速排序是一种常用的排序算法,在Java中可以使用递归来实现。下面是使用Java编写的快速排序算法:
```java
public class QuickSort {
public static void main(String[] args) {
int[] nums = {6, 9, 3, 1, 7};
quickSort(nums, 0, nums.length - 1);
System.out.println("排序结果:");
for (int num : nums) {
System.out.print(num + " ");
}
}
public static void quickSort(int[] nums, int left, int right) {
if (left < right) {
int partitionIndex = partition(nums, left, right); // 划分数组并获取划分点的位置
quickSort(nums, left, partitionIndex - 1); // 对划分点左边的子数组进行快速排序
quickSort(nums, partitionIndex + 1, right); // 对划分点右边的子数组进行快速排序
}
}
public static int partition(int[] nums, int left, int right) {
int pivot = nums[right]; // 选择最右边的元素作为划分点
int i = left - 1; // 记录小于划分点的索引
for (int j = left; j < right; j++) {
if (nums[j] < pivot) {
i++;
swap(nums, i, j); // 将小于划分点的元素交换到左侧
}
}
swap(nums, i + 1, right); // 将划分点交换到正确的位置
return i + 1; // 返回划分点的位置
}
public static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
```
以上是使用Java编写的快速排序算法。首先定义了`quickSort`方法作为入口,它接受一个整数数组和左右边界。在`quickSort`方法中,使用`partition`方法来划分数组,并对划分点左右的子数组进行递归调用。`partition`方法选择最右边的元素作为划分点,然后使用"双指针"法将小于划分点的元素移到左侧。最后,将划分点交换到正确的位置,并返回划分点的位置。排序完成后,输出排序结果。
运行上述代码,输出结果为:"排序结果:1 3 6 7 9",表示数组已经按升序排序。