java实现快速排序
时间: 2023-09-17 18:05:45 浏览: 83
### 回答1:
Java实现快速排序的方法如下:
```java
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;
}
```
首先通过递归调用快速排序算法对整个数组进行排序,其中partition()函数用来确定基准元素的位置。在partition()函数中通过遍历整个数组,将小于等于基准元素的数都放在基准元素的左边,大于基准元素的数都放在基准元素的右边。最后通过递归调用快速排序算法对基准元素左边和右边的两个子序列分别进行排序,直到整个序列有序。
### 回答2:
快速排序是一种高效的排序算法,其思想是通过选择一个基准元素,将待排序序列分成两部分,左边的元素小于基准元素,右边的元素大于基准元素。然后对左、右两部分分别进行递归快速排序,直到排序完成。以下是Java实现快速排序的代码:
```java
public class QuickSort {
public 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 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 = {8, 4, 2, 5, 1, 9, 3};
QuickSort quickSort = new QuickSort();
quickSort.quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
以上代码通过递归调用实现了快速排序。首先选择数组的第一个元素作为基准元素,然后使用双指针的方式,将小于基准元素的元素移到基准元素的左边,将大于基准元素的元素移到基准元素的右边。然后对左右两个子数组分别进行递归排序,直到排序完成。最后输出排序后的数组。
### 回答3:
快速排序是一种常见的排序算法,也是Java中常用的排序算法之一。下面是一个用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 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;
left++;
right--;
}
}
// 将基准元素放到正确的位置上
int temp = arr[low];
arr[low] = arr[right];
arr[right] = temp;
return right; // 返回基准元素的位置
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 7, 6, 3};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
上述代码中,`quickSort`方法是快速排序的入口方法,它接受一个待排序数组、低位索引和高位索引作为参数。在`quickSort`方法中,首先判断低位索引是否小于高位索引,如果是则找到基准元素的位置并对其左右两边的子数组进行递归排序。`partition`方法用来找到基准元素的位置,通过左右指针从数组两端开始寻找符合条件的元素,并交换它们的位置,最后将基准元素放到正确的位置上。最后,在`main`方法中初始化一个数组并调用`quickSort`方法对其进行排序,然后输出排序后的结果。
快速排序的平均时间复杂度为O(nlogn),是一种高效的排序算法。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)