网站后台地址忘记了衙门口网站建设
快速排序（Quicksort）是一种高效的排序算法，采用分治法（Divide and Conquer）的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。以下是用Java实现的快速排序算法：
public class QuickSort { // 主方法，用于测试快速排序 public static void main(String[] args) { int[] array = {10, 7, 8, 9, 1, 5}; int n = array.length; System.out.println("排序前的数组:"); printArray(array); quickSort(array, 0, n-1); System.out.println("排序后的数组:"); printArray(array); } // 快速排序方法 public static void quickSort(int[] array, int low, int high) { if (low < high) { // 找到分区点 int pi = partition(array, low, high); // 递归地对左右子数组排序 quickSort(array, low, pi - 1); quickSort(array, pi + 1, high); } } // 分区方法 public static int partition(int[] array, int low, int high) { int pivot = array[high]; // 选择最右边的元素作为枢轴 int i = (low - 1); // i是较小元素的索引 for (int j = low; j < high; j++) { // 如果当前元素小于或等于枢轴 if (array[j] <= pivot) { i++; // 交换array[i]和array[j] int temp = array[i]; array[i] = array[j]; array[j] = temp; } } // 交换array[i + 1]和array[high] (或枢轴) int temp = array[i + 1]; array[i + 1] = array[high]; array[high] = temp; return i + 1; } // 打印数组方法 public static void printArray(int[] array) { int n = array.length; for (int i = 0; i < n; ++i) { System.out.print(array[i] + " "); } System.out.println(); }
}代码解释
- 主方法 (
main):- 创建一个数组并输出排序前的数组。
- 调用
quickSort方法对数组进行排序。 - 输出排序后的数组。
- 快速排序方法 (
quickSort):- 如果
low小于high，则进行排序。 - 调用
partition方法获取分区点pi。 - 递归地对分区点前后的子数组进行排序。
- 如果
- 分区方法 (
partition):- 选择数组的最后一个元素作为枢轴。
- 初始化较小元素的索引
i。 - 遍历数组，如果当前元素小于或等于枢轴，则交换
array[i]和array[j]。 - 遍历完成后，将枢轴放到正确的位置（即
i + 1），并返回该位置。
- 打印数组方法 (
printArray):- 遍历数组并打印每个元素。
注意事项
- 枢轴的选择可以优化，例如随机选择枢轴或选择数组的中间元素作为枢轴，以减少最坏情况（例如已经有序的数组）下的性能下降。
- 快速排序的空间复杂度主要是递归调用栈，最坏情况下为 O(n)，但平均情况下较好。
- 快速排序的时间复杂度平均情况下为 O(n log n)，最坏情况下为 O(n^2)。