用Java实现快速排序算法,并分析算法的时间复杂度,写出完整的代码,包括类名
时间: 2024-03-24 18:41:33 浏览: 23
好的,下面是Java实现快速排序算法的代码,类名为QuickSort:
```java
public class QuickSort {
public static void main(String[] args) {
int[] arr = { 10, 7, 8, 9, 1, 5 };
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println("Sorted array: ");
printArray(arr);
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 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 - 1; 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 printArray(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
}
```
这段代码中,我们定义了一个QuickSort类,其中包含了三个方法:quickSort、partition和printArray。
quickSort方法是快速排序算法的主要部分,它通过递归的方式将数组划分为两个部分,并对每个部分进行排序。在每次递归时,我们选择数组中的一个元素作为基准元素,并将数组中小于该元素的元素放在基准元素的左侧,大于该元素的元素放在基准元素的右侧。
partition方法用于划分数组,它选择数组的最后一个元素作为基准元素,然后将数组中小于该元素的元素放在基准元素的左侧,大于该元素的元素放在基准元素的右侧。
printArray方法用于输出排序后的数组。
快速排序算法的时间复杂度为O(nlogn)。