Java代码实现快速排序
时间: 2023-09-11 16:05:16 浏览: 70
### 回答1:
Java代码实现快速排序的具体实现步骤如下: 1、选取数组的第一个元素作为基准,称为 “基准”。
2、将所有小于“基准”的元素移到“基准”的左边,所有大于“基准”的元素移到“基准”的右边。
3、对“基准”左边和右边的两个子数组分别重复第一、第二步,直到所有子数组只剩下一个元素为止。
### 回答2:
快速排序是一种常用的排序算法,它是基于分治法的思想。
具体实现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[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {9, 2, 5, 1, 4, 7, 6, 8, 3};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
在上述代码中,函数`quickSort()`用于排序整个数组,使用`partition()`函数确定一个基准元素,并将小于基准的元素放在它的左边,大于基准的元素放在它的右边。递归调用`quickSort()`函数对基准元素左右两边的子数组进行排序。最终得到排序后的数组。
在`main()`函数中,测试了一个包含9个元素的整型数组的快速排序的实现,并打印出排序后的数组。
快速排序的时间复杂度为O(nlogn),且是原地排序算法,不需要额外的空间。
### 回答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);
}
}
private 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 = {5, 2, 8, 3, 9, 1};
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
以上是一个简单的快速排序的实现。通过递归调用quickSort函数和partition函数,将数组不断拆分为子序列,并在每次选取基准时进行交换使得左边的元素都小于基准,右边的元素都大于基准。最后整个数组就有序了。
相关推荐
![](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)
![](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)
![](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)
![](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)