生成一个快速排序代码用java语言
时间: 2023-08-31 13:20:50 浏览: 65
### 回答1:
public class QuickSort {
public static void sort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length == 0)
return;
if (low >= high)
return;
int middle = low + (high - low) / 2;
int pivot = arr[middle];
int i = low, j = high;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (low < j)
quickSort(arr, low, j);
if (high > i)
quickSort(arr, i, high);
}
}
### 回答2:
快速排序(Quick Sort)是一种常用的排序算法。
下面是一个用Java语言实现快速排序的代码:
```java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length == 0) {
return;
}
if (low >= high) {
return;
}
int middle = low + (high - low) / 2;
int pivot = arr[middle];
int i = low, j = high;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (low < j) {
quickSort(arr, low, j);
}
if (high > i) {
quickSort(arr, i, high);
}
}
public static void main(String[] args) {
int[] arr = {7, 2, 9, 3, 6, 1, 8, 5, 4};
int length = arr.length;
quickSort(arr, 0, length - 1);
System.out.println("排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
通过调用`quickSort`方法对输入的数组进行快速排序。在每次排序中,我们选择一个基准元素(pivot),将小于基准元素的数放在基准元素的左边,将大于基准元素的数放在基准元素的右边。然后对左右两个子数组分别进行快速排序。最后,整个数组就被排序好了。
以上代码的输出结果为:
```
排序后的数组:
1 2 3 4 5 6 7 8 9
```
快速排序的时间复杂度为O(nlogn),是一种高效的排序算法。
### 回答3:
快速排序(Quick Sort)是一种高效的排序算法,它利用分治法来实现排序。以下是用Java语言实现的快速排序代码:
```java
public class QuickSort {
public void quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
}
private 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 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, 5, 1, 3, 8, 4, 7, 2, 6};
QuickSort quickSort = new QuickSort();
quickSort.quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组:");
for (int element : arr) {
System.out.print(element + " ");
}
}
}
```
这段代码中,QuickSort类包含三个方法:quickSort、partition和swap。
- quickSort方法是快速排序的入口,它通过递归调用自身来实现排序。首先判断左下标是否小于右下标,如果满足条件,选取数组最右边的元素作为基准值(pivot),并通过调用partition方法将数组分为两部分。然后再对左右两部分分别进行快速排序,直到排序完成。
- partition方法是用于划分数组的核心算法。它使用两个指针,i和j,分别从数组的左边和右边向中间移动。如果发现arr[j]小于基准值,则将i和j的元素互换位置,然后i自增1。当遍历完数组后,将基准值放入最终的位置,返回该位置的下标。
- swap方法是用于交换数组中两个元素的位置。
在主函数main中,我们可以看到如何使用这个快速排序算法来对一个整数数组进行排序。首先声明一个数组,并调用quickSort方法对该数组进行排序。最后,打印排序后的数组。
该代码使用了传统的快速排序算法,并且在每一步都选择数组最右边的元素作为基准值。但是快速排序也有其他的优化方式,如随机选择基准值和三数取中法,以提高算法的效率和稳定性。