用java实现快速排序
时间: 2023-08-19 13:17:06 浏览: 149
### 回答1:
快速排序是一种分治算法,它的基本思想是通过一趟排序将待排序的记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录继续进行排序,以达到整个序列有序的目的。
下面是一个用 Java 实现快速排序的示例代码:
```
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 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;
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 4, 7, 6, 1, 3, 8};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // 输出:[1, 2, 3, 4, 5, 6, 7, 8, 9]
}
}
```
在这段代码中,`quickSort` 方法是快速排序的主函数,它通过递归来实现分治。`partition` 方法是用来划分数组的,它通过挖坑填数的方式将数组划分成两部分,其中左边的数字都小于等于右边的数字。`sw
### 回答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);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low + 1;
int j = high;
while (i <= j) {
while (i <= j && arr[i] < pivot) {
i++;
}
while (i <= j && arr[j] > pivot) {
j--;
}
if (i <= j) {
swap(arr, i, j);
}
}
swap(arr, low, j);
return j;
}
public 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 = {5, 2, 8, 9, 1, 3};
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
该代码中的`quickSort`方法是入口方法,用于调用`partition`方法并进行递归。`partition`方法是快速排序的核心,它选取一个基准值(这里选择最低位的元素)并通过交换元素的方式将小于基准值的放在左边,大于基准值的放在右边,最后返回基准值的索引。`swap`方法用于交换数组中两个元素的位置。在`main`方法中,我们定义了一个待排序的数组并调用`quickSort`方法来进行排序,最后输出排序后的结果。
### 回答3:
快速排序是一种高效的排序算法,它通过将待排序序列分成两部分,分别对两部分进行排序,最后将两部分合并起来,从而完成排序的过程。
快速排序使用了分治的思想,它的核心操作是选择一个基准元素(通常选择序列的第一个元素),然后将序列分成比基准元素小和比基准元素大的两部分。接着,对这两部分分别进行快速排序,直到每个部分只有一个元素或者为空为止。最后,将两部分合并起来,即可得到排好序的序列。
下面是用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); // 对右子序列进行快速排序
}
}
// 划分操作
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 = {6, 8, 3, 2, 9, 2, 1, 7};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序结果:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
上述代码中,首先定义了一个`quickSort`方法,该方法接受一个数组、低位索引和高位索引作为参数。在该方法中,通过`partition`方法将数组划分为两部分,再对这两部分进行递归调用,直到每个部分只有一个元素或者为空为止。
`partition`方法是快速排序的核心操作,它选择了第一个元素作为基准元素,然后通过双指针的方式将整个数组划分为两部分。最后,将基准元素放到最终位置,并返回基准元素的索引。
在`main`方法中,我们可以测试快速排序的实现。将一个无序数组传入`quickSort`方法,最后输出排好序的数组。
快速排序的时间复杂度为O(nlogn),是一种非常高效的排序算法。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)