快速排序（Java栈实现）

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

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


public class QuickSortStack {


    
    public void sort(int[] array,int startIndex,int endIndex){
        // 用一个集合栈代替递归的函数栈
        Stack> maps = new Stack>();
        // 整个数列的起止下标，以哈希的形式入列
        Map rootMap = new HashMap();
        rootMap.put("startIndex",startIndex);
        rootMap.put("endIndex", endIndex);
        maps.push(rootMap);

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

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

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

    
    public int partition(int[] array,int startIndex,int endIndex){
        // 取第一个元素作为基准元素（可以随机选择）
        int pivot = array[startIndex];
        //mark 标识小于基准元素的区域边界
        int mark = startIndex;
        
        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));
    }
}