vlambda博客
学习文章列表

public static void quickSort(int[] arr, int startIndex, int endIndex) {
    // 用一个集合栈来代替递归的函数栈
    Stack<Map<String, Integer>> quickSortStack = new Stack<Map<String, Integer>>();

    // 数组的下标通过哈希的形式入栈
    Map indexParam = new HashMap();
    indexParam.put("startIndex", startIndex);
    indexParam.put("endIndex", endIndex);
    quickSortStack.push(indexParam);

    // 循环结束条件:栈为空
    while (!quickSortStack.isEmpty()) {
        // 栈顶元素出栈,得到起止下标
        Map<String, Integer> param = quickSortStack.pop();
        // 得到基准元素位置
        int standardIndex = partition2(arr, param.get("startIndex"), param.get("endIndex"));
        // 根据基准元素分成两部分, 把每一部分的起止下标入栈
        if (param.get("startIndex") < standardIndex - 1) {
            Map<String, Integer> leftParam = new HashMap<>();
            leftParam.put("startIndex", param.get("startIndex"));
            leftParam.put("endIndex", param.get("endIndex"));
            quickSortStack.push(leftParam);
        }
        if (param.get("endIndex") > standardIndex + 1) {
            HashMap<String, Integer> rightParam = new HashMap<>();
            rightParam.put("startIndex", standardIndex + 1);
            rightParam.put("endIndex", param.get("endIndex"));
            quickSortStack.push(rightParam);
        }

    }

}

/**
 * @description: 非递归实现快速排序
 * @author: liangyadong
 * @date: 2021/7/12 0012 21:08
 **/
public class QuickSortNonRecur {

    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        // 用一个集合栈来代替递归的函数栈
        Stack<Map<String, Integer>> quickSortStack = new Stack<Map<String, Integer>>();

        // 数组的下标通过哈希的形式入栈
        Map indexParam = new HashMap();
        indexParam.put("startIndex", startIndex);
        indexParam.put("endIndex", endIndex);
        quickSortStack.push(indexParam);

        // 循环结束条件:栈为空
        while (!quickSortStack.isEmpty()) {
            // 栈顶元素出栈,得到起止下标
            Map<String, Integer> param = quickSortStack.pop();
            // 得到基准元素位置
            int standardIndex = partition(arr, param.get("startIndex"), param.get("endIndex"));
            // 根据基准元素分成两部分, 把每一部分的起止下标入栈
            if (param.get("startIndex") < standardIndex - 1) {
                Map<String, Integer> leftParam = new HashMap<>();
                leftParam.put("startIndex", param.get("startIndex"));
                leftParam.put("endIndex", param.get("endIndex"));
                quickSortStack.push(leftParam);
            }
            if (param.get("endIndex") > standardIndex + 1) {
                HashMap<String, Integer> rightParam = new HashMap<>();
                rightParam.put("startIndex", standardIndex + 1);
                rightParam.put("endIndex", param.get("endIndex"));
                quickSortStack.push(rightParam);
            }

        }

    }

    /**
     * 分治(单边循环法)
     *
     * @param arr        待交换的数组
     * @param startIndex 起始下标
     * @param endIndex   结束下标
     * @return 基准元素的位置
     */
    private static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一位元素作为基准元素
        int standardValue = arr[startIndex];
        // 指针指向数列的起始位置,mark代表小于基准元素的区域边界
        int mark = startIndex;

        // 遍历数组,如果遍历到的元素小于基准元素: 1. 2.
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < standardValue) {
                // 1.指针右移一位
                mark++;
                // 2.并将当前遍历到的元素和指针所指元素交换
                int temp = arr[i];
                arr[i] = arr[mark];
                arr[mark] = temp;
            }
        }

        // 遍历结束,将基准元素和指针指向的元素交换,这一轮宣告结束
        arr[startIndex] = arr[mark];
        arr[mark] = standardValue;
        return mark;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 6, 3, 7, 9, 8, 4, 1, 0};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
}