快速排序（Java栈实现）

引入一个存储Map类型的元素的栈，用于存储每一次交换时的起止下标。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author lizz
 * @ClassName QuickSortStack.java
 * @Description 用栈（stack）实现快速排序
 * @createTime 2022年04月22日 11:10:00
 */
public class QuickSortStack {


    /**
     * 基于递归实现快速排序
     * @param array  要排序的数组
     * @param startIndex 开始下标
     * @param endIndex 结束下标
     */
    public void sort(int[] array,int startIndex,int endIndex){
        // 用一个集合栈代替递归的函数栈
        Stack<Map<String, Integer>> maps = new Stack<Map<String, Integer>>();
        // 整个数列的起止下标，以哈希的形式入列
        Map rootMap = new HashMap();
        rootMap.put("startIndex",startIndex);
        rootMap.put("endIndex", endIndex);
        maps.push(rootMap);

        //循环结束条件：栈为空时
        while( !maps.isEmpty()){
            //栈顶元素出栈，得到起止下标
            Map<String, Integer> pop = maps.pop();

            //得到基准元素位置
            Integer start = pop.get("startIndex");
            Integer end = pop.get("endIndex");
            int partition = partition(array, start, end);

            //根据基准元素分成两部分，把每一部分的起止下标入栈
            if(start < partition -1){
                Map<String ,Integer> leftParam = new HashMap<String,Integer>();
                leftParam.put("startIndex",start);
                leftParam.put("endIndex",partition-1);
                maps.push(leftParam);
            }
            if(end > partition+1){
                Map<String ,Integer> rightParam = new HashMap<String,Integer>();
                rightParam.put("startIndex",partition+1);
                rightParam.put("endIndex",end);
                maps.push(rightParam);
            }
        }
    }

    /**
     * 分治（单边循环法）
     * @param array  待交换的数组
     * @param startIndex 开始下标
     * @param endIndex 结束下标
     * @return
     */
    public int partition(int[] array,int startIndex,int endIndex){
        // 取第一个元素作为基准元素（可以随机选择）
        int pivot = array[startIndex];
        //mark 标识小于基准元素的区域边界
        int mark = startIndex;
        /*
            如果元素大于基准元素，就继续遍历
            如果元素小于基准元素：
                1：mark指针右移一位，因为小于pivot的区域增大了一个。
                2：最新遍历到的元素和mark指针所指在的元素交换位置，因为最新遍历的元素归属于小于pivot的区域。
         */
        for (int i = startIndex+1; i<= endIndex ; i++) {
            //此时遍历到的元素小于基准元素
            if(array[i] < pivot){
                mark++;
                int temp = array[mark];
                array[mark] = array[i];
                array[i] = temp;
            }
        }

        //将pivot元素交换到mark指针所在的位置，这一轮交换结束
        array[startIndex] = array[mark];
        array[mark] = pivot;

        return mark;
    }

    public static void main(String[] args) {
        QuickSortStack quickSort = new QuickSortStack();
        int[] array = new int[]{2,4,6,1,5,83,2,9};
        quickSort.sort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
}