快速排序非递归实现

Q:为什么快速排序要非递归实现：
A:虽然递归是实现快速排序的一种常见方式，但选择非递归实现（迭代实现）通常是出于以下一些原因：

1. 避免递归调用带来的额外开销： 递归调用在一些编程语言中可能引入额外的开销，包括函数调用栈的使用和维护。非递归实现可以通过显式地使用栈来避免这些开销。

2. 避免栈溢出： 在极端情况下，递归实现可能导致栈溢出，尤其是在处理大规模数据时。非递归实现使用显式的数据结构（如栈）来管理状态，不依赖于系统的调用栈。

3. 降低空间复杂度： 递归实现可能需要更多的内存空间，因为每个递归调用都需要在内存中保留一些信息。非递归实现通常使用更少的内存，只需维护一些必要的状态信息。

4. 提高性能： 一些编程语言和环境中，递归调用的性能可能不如循环，因为每个递归调用都需要函数调用的开销。非递归实现可以更好地与一些编译器和优化器协同工作，从而提高性能。

5. 方便迭代的优化： 非递归实现更容易进行一些优化，例如通过使用迭代而不是递归的方式来访问数组，以更好地利用 CPU 缓存。

总体而言，非递归实现提供了一种更直接、更灵活地控制算法流程和资源使用的方式，尤其在对性能和内存使用有严格要求的情况下，非递归实现可能更受青睐。然而，递归实现通常更易理解和实现，具有更直观的表达方式。选择使用递归还是非递归实现取决于具体的应用场景和性能需求。

这里使用栈和迭代的方式进行非递归实现快排

package day11;

import java.util.Stack;

//快速排序的非递归实现

public class QuickSort {
    public static void quickSort(int[] array){
        if(array==null||array.length == 0){
            return;
        }
        Stack<Integer> stack = new Stack<>(); //存储排序过程中待处理子数组的起始和结束索引
        stack.push(0);
        stack.push(array.length-1);
        while (!stack.isEmpty()){
            int end = stack.pop();
            int start = stack.pop();
            int partitionIndex = partition(array,start,end); //基准元素的索引
            //第一个条件判断检查基准元素左侧是否还有元素，即检查分区后左侧子数组是否有两个及以上的元素。
            //如果有，将左侧子数组的起始索引 start 和结束索引 partitionIndex-1 推入栈中，以便后续对这个左侧子数组的排序。
            if(partitionIndex-1>start){
                stack.push(start);
                stack.push(partitionIndex-1);
            }
            //条件判断检查基准元素右侧是否还有元素，即检查分区后右侧子数组是否有两个及以上的元素。
            // 如果有，将右侧子数组的起始索引 partitionIndex+1 和结束索引 end 推入栈中，以便后续对这个右侧子数组的排序。
            if(partitionIndex+1<end){
                stack.push(partitionIndex+1);
                stack.push(end);
            }
        }
    }
    //这段代码实现了快速排序算法中的分区（Partition）步骤。
    public static int partition(int[] array,int start,int end){
        int pivot = array[end]; //基准元素选最后一个
        int i = start-1; //始终指向小于等于基准元素的元素应该放置的位置。
        for(int j = start;j<end;j++){
            if(array[j]<=pivot){
                i++;
                swap(array,i,j);
            }
        }
        //pivot 放置到最终的位置，确保左侧的元素都小于等于基准元素，右侧的元素都大于基准元素。
        swap(array, i+1, end);
        return i+1;
    }
    private static void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static void main(String[] args){
        int[] array = {3,1,4,1,5,9,2,6,5,3,5};
        quickSort(array);
        System.out.println("Sorted Array");
        for(int num:array){
            System.out.println(num+" ");
        }
    }
}