移动网站设计教程,郑州网站建设技术支持,福建省城乡和住房建设厅网站,网站建设图片qq群快速排序#xff08;Quicksort#xff09;是一种高效的排序算法#xff0c;采用分治法#xff08;Divide and Conquer#xff09;的策略来把一个序列分为较小和较大的两个子序列#xff0c;然后递归地排序两个子序列。以下是用Java实现的快速排序算法#xff1a;
publi…快速排序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)。
