21xrx.com
2025-03-17 14:58:49 Monday
文章检索 我的文章 写文章
Java快速排序的两种方法
2023-11-04 07:52:18 深夜i     14     0
Java 快速排序 方法 排序算法

Java快速排序是一种高效的排序算法，常用于对大量数据进行排序。它的核心思想是通过将一个数组分割成较小的子数组，并对每个子数组进行排序，最终将这些子数组合并成一个有序的数组。快速排序有两种常用的实现方法：递归实现和非递归实现。

递归实现是最常见的实现方法之一。它的实现思路是选择数组中的一个元素作为基准元素，将比基准元素小的所有元素放在基准元素的左边，将比基准元素大的所有元素放在基准元素的右边，然后对左右两个子数组分别进行递归排序，最后将左右子数组和基准元素按顺序合并起来。递归实现的代码如下：

public static void quickSort(int[] arr, int low, int high){
  if(low < high){
   int pivot = partition(arr, low, high);
   quickSort(arr, low, pivot - 1);
   quickSort(arr, pivot + 1, high);
  }
}
public static int partition(int[] arr, int low, int high){
  int pivot = arr[low];
  while(low < high){
   while(low < high && arr[high] >= pivot)
     high--;
   
   arr[low] = arr[high];
   while(low < high && arr[low] <= pivot){
     low++;
   }
   arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

非递归实现是将递归实现转化为循环实现的一种方法。它使用一个栈来存储待排序子数组的起始和结束位置，实现起来比递归实现更加复杂。其思路是将整个数组分割成多个较小的子数组，然后依次对每个子数组进行排序，最后将所有子数组按顺序合并起来。非递归实现的代码如下：

public static void quickSort(int[] arr){
  Stack<Integer> stack = new Stack<>();
  stack.push(0);
  stack.push(arr.length - 1);
  while (!stack.isEmpty()){
   int high = stack.pop();
   int low = stack.pop();
   int pivot = partition(arr, low, high);
   if(pivot - 1 > low){
     stack.push(low);
     stack.push(pivot - 1);
   }
   if(pivot + 1 < high){
     stack.push(pivot + 1);
     stack.push(high);
   }
  }
}
public static int partition(int[] arr, int low, int high){
  int pivot = arr[low];
  while(low < high){
   while(low < high && arr[high] >= pivot)
     high--;
   
   arr[low] = arr[high];
   while(low < high && arr[low] <= pivot){
     low++;
   }
   arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

无论是递归实现还是非递归实现，Java快速排序都是一种快速高效的排序算法。它的时间复杂度为O(nlogn)，并且在平均情况下具有较好的性能。因此，使用Java快速排序可以提高程序的执行效率，适用于对大量数据进行排序的场景。

  
  

评论区