JAVA快速排序：递归与非递归堆栈实现解析

"本文介绍了两种在Java中实现快速排序的方法：传统递归实现和非递归堆栈模拟实现。提供了详细的代码示例，包括主函数测试部分。" 快速排序是一种高效的排序算法，由C.A.R. Hoare在1960年提出。它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。 ### 1. 递归实现快速排序 在传统的递归实现中，快速排序的核心是选择一个“基准”元素，然后将数组分为两部分：一部分的所有元素都小于基准，另一部分的所有元素都大于或等于基准。这个过程称为分区操作。然后，对这两部分再分别进行快速排序。 ```java public static void quicksort(int array[], int low, int high) { // ... int i = low; int j = high; int key = array[(low + high) / 2]; // 获取中间值作为基准 swap(array, low, (low + high) / 2); // 将基准放到数组的起始位置 // ... } ``` 在这个例子中，`quicksort()`函数接收一个数组、起始索引和结束索引作为参数。基准的选择是取区间的中间元素，然后通过两个指针`i`和`j`分别从两端向中间扫描，找到第一个大于基准的元素和第一个小于基准的元素，交换它们。当`i`和`j`相遇时，分区完成。接着，对`i`左侧和`j`右侧的子区间进行递归调用`quicksort()`。 ### 2. 非递归堆栈模拟实现快速排序 递归实现虽然简洁，但在处理大量数据时可能会导致递归深度过大，影响性能。非递归实现通过使用堆栈来模拟递归过程，避免了系统调用开销。 ```java class Stack { private LinkedList linkedlist = new LinkedList<>(); // ... } ``` 在非递归实现中，我们可以使用一个自定义的`Stack`类来存储待处理的子区间。每次从堆栈中取出一个子区间，执行分区操作，并将新产生的子区间压入堆栈。当堆栈为空时，排序完成。 ### 分区操作 ```java while (low < high && array[high] >= key) { // 从右向左找到第一个小于基准的元素 high--; } while (low < high && array[low] <= key) { // 从左向右找到第一个大于基准的元素 low++; } swap(array, low, high); // 交换找到的元素，将基准放到正确的位置 ``` 这部分代码实现了分区操作，通过两个循环找到合适的位置，然后交换元素使得所有小于基准的元素都在其左侧，大于基准的元素在其右侧。 ### 主函数测试 ```java public static void main(String[] args) { int test[] = new int[]{23, 11, 5, 14, 12, 67, 89, 31, 52, 113, 56}; // 打印原始数组 // 对数组进行快速排序 // 打印排序后的数组 } ``` 主函数用于测试快速排序的效果，创建一个无序数组，先打印原始数组，然后调用`quicksort()`函数进行排序，最后再次打印排序后的数组。 通过这两种方式，我们可以看到快速排序的两种实现思路，递归和非递归。递归实现简洁但可能导致深度过大的问题，非递归实现则可以解决这个问题，但代码相对复杂。在实际应用中，可以根据具体场景选择适合的实现方式。