堆排序

package com.lianzhu.filemanage.utils;

import java.util.Stack;

/**
 * 栈排序
 * @description:栈的特性：先进后出  如空数组【】
 * @step1:有一串数字 4,8,7,9,2,6
 * 依次按照顺序 4 8 7  9  2  6放入【】然后就是这种【629784】
 * 然后取出来的时候就是6  2  9  7   8   4
 * 可以理解为一个桶，先进去的放在最里面，最后放进去的在最外边，这样取出来的时候就先取
 * 最外边的，最后取最先面的
 */
public class StackSort {



    private static void twoStackSort(int[] arr){
        //source原栈
        Stack<Integer> source = new Stack<Integer>();
        for(int i = 0; i < arr.length; i++){
            source.push(arr[i]);
        }
        //target目标栈
        Stack<Integer> target = twoStackSort(source);
        while(!target.isEmpty()){
            System.out.println(target.pop());
        }
    }

    /**
     * step1:原栈source不为空，目标栈source为空，把原栈target顶栈元素放入目标栈
     * step2:原栈source不为空，目标栈target不为空，把source顶栈元素与target进行比较
     *        1.0循环判断target不为空且顶栈元素大于source顶栈元素v，
     *        2.0把target大于source顶栈元素取出放入source
     *        3.0把v放入target
     * step3: 循环step1与step2
     * 特点：改变target v的判断逻辑可以把输出改为升序，目前输出是降序
     * @param source
     * @return
     */
    private static Stack<Integer> twoStackSort(Stack<Integer> source) {
        Stack<Integer> target = new Stack<Integer>();
        while(!source.isEmpty()){
            if(target.isEmpty()){
                target.push(source.pop());
            }else{
                int v = source.pop();
                if(target.peek() <= v){
                    target.push(v);
                }else{
                    while(!target.isEmpty() && target.peek() > v){
                        source.push(target.pop());
                    }
                    target.push(v);
                }
            }
        }
        return target;
    }

    public static void main(String[] args) {
        int arr[]=new  int []{98,5,4,61,3,2,57,4,65};
        twoStackSort(arr);
    }
}