耐心排序

十大经典排序算法

大家应该玩过纸牌游戏，耐心排序（Patience Sort）就是一种基于纸牌游戏的算法。他的实现原理就是首先使用数组中的第一个数字创建一个纸牌堆，然后逐个读取数组中的剩余数字，如果当前数字比所有纸牌堆中最上面的数字都大，就新建一个纸牌堆，把当前数字放到该堆中。否则找到一个最上面数字不小于当前数字的纸牌堆，把当前数字放到该纸牌堆中。

我们看到这里的纸牌堆实际上就是一个单调集合，我们可以使用一个栈来记录，从栈顶到栈底是单调递增的，来看下代码。

private void patienceSort(int[] nums) {
    // 创建堆，这里使用优先队列。
    PriorityQueue<Stack<Integer>> queue = new PriorityQueue<>(
            Comparator.comparingInt(Stack::peek));
    // 为第一个元素创建一个单独的集合。
    Stack<Integer> firstStack = new Stack<>();
    firstStack.push(nums[0]);
    queue.offer(firstStack);

    int length = nums.length;
    for (int i = 1; i < length; i++) {
        int num = nums[i];
        Stack<Integer> stack = null;
        // 遍历堆中的所有集合，查找集合中第一个元素大于等于当前元素的集合。
        for (Stack<Integer> queueStack : queue) {
            if (queueStack.peek() >= num) {
                stack = queueStack;
                stack.push(num);
                break;
            }
        }
        // 如果没找到，创建一个新的集合，最后再把它放到堆中。
        if (stack == null) {
            stack = new Stack<>();
            stack.push(num);
            queue.offer(stack);
        }
    }

    // 每个集合都是有序的，合并所有集合。
    int index = 0;
    while (index < length) {
        Stack<Integer> pollStack = queue.poll();// 出队
        nums[index++] = pollStack.pop();// 取出集合中的第一个元素，也是集合中最小的
        if (!pollStack.isEmpty())// 如果该集合不为空，还需要在把它加入到堆中。
            queue.add(pollStack);
    }
}

相关链接