快速排序java代码实现_数据结构中快速排序怎么排

激活谷笔记 • 2024-12-23 12:10 • 阅读 27

快速排序是一种高效的排序算法，其基本思想是选择一个基准值（pivot），将数组分为两部分，一部分包含所有小于基准值的素，另一部分包含所有大于基准值的素，然后对这两部分递归地应用快速排序算法。

下面是一个简单的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； // 如果low大于等于high，则没有素需要排序 // 找到分割点 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--； } } // 递归排序左右两部分 quickSort（arr, low, j）； quickSort（arr, i, high）； } public static void main（String[] args） { int[] arr = {5, 2, 7, 3, 6, 1, 4}； quickSort（arr, 0, arr.length - 1）； for （int num : arr） { System.out.print（num + " "）； } } }

这段代码定义了一个名为`QuickSort`的类，其中包含一个静态方法`quickSort`，用于对传入的整数数组进行快速排序。`main`方法中创建了一个数组，并调用`quickSort`方法对其进行排序，然后打印排序后的结果。

快速排序的平均时间复杂度为O（n log n），最坏情况下为O（n^2），但通过选择合适的基准值可以避免最坏情况的发生。

快速排序java代码实现_数据结构中快速排序怎么排

相关推荐