java - 如何找到对数组进行排序所需的最大组数？

Question

假设我有一个数组:

[1, 8, 5, 6, 10, 9, 11, 12];

我想按升序对其进行排序，但找出我需要排序的最大组数。在这个例子中，答案是:

[1], [8,5,6], [10,9], [11], [12]: so 5

[3, 2, 1] 结果会是 1，因为整个数组都需要排序。

我完全不知道如何做到这一点，将不胜感激向正确的方向轻推。

Answer 1

我的解决方案使用插入排序算法，该算法将已排序的元素保留在它们的位置，并将未排序的元素移向数组的开头，直到它们到达它们的位置。我们可以使用此行为来检测需要排序的组。

在每次迭代中，我们检查当前元素是否大于或等于前一个元素。如果是这样，我们可能遇到了一个新的群体。我们将当前索引插入堆栈。

如果当前元素小于上一个元素，那么我们仍然在同一个组中。我们开始将这个元素与之前的元素交换，直到它就位。在每一步中，我们都会检查我们是否越过了前一组的边界。如果边界被越过，则意味着这两组实际上是一组，所以我们从堆栈中弹出最后一个值。

最后，组数等于堆栈大小。

实现如下:

public static int countGroups(int[] a) {
    if (a.length < 2) return a.length;
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    for (int i = 1; i < a.length; i++) {
        if (a[i] >= a[i - 1]) stack.push(i);
        for (int j = i; j > 0 && a[j] < a[j - 1]; j--) {
            swap(a, j, j - 1);
            if (j <= stack.peek()) stack.pop();
        }
    }
    return stack.size();
}

private static void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

下面是一段带有一些示例的 JavaScript 片段:

console.log(countGroups([1, 8, 5, 6, 10, 9, 11, 12]));    //5 - [1], [8, 5, 6], [10, 9], [11], [12]
console.log(countGroups([1, 8, 5, 6, 10, 9, 2, 11, 12])); //4 - [1], [8, 5, 6, 10, 9, 2], [11], [12]
console.log(countGroups([3, 8, 5, 6, 10, 9, 2, 11, 1]));  //1 - [3, 8, 5, 6, 10, 9, 2, 11, 1]
console.log(countGroups([1, 2, 8, 6, 10, 9, 11]));        //5 - [1], [2], [8, 6], [10, 9], [11]
console.log(countGroups([1, 2, 1, 1, 10, 9, 10]));        //4 - [1], [2, 1, 1], [10, 9], [10]

function countGroups(a) {
    if (a.length < 2) return a.length;
    let stack = [0];
    for (let i = 1; i < a.length; i++) {
        if (a[i] >= a[i - 1]) stack.push(i);
        for (let j = i; j > 0 && a[j] < a[j - 1]; j--) {
            swap(a, j, j - 1);
            if (j <= stack[stack.length - 1]) stack.pop();
        }
    }
    return stack.length;
}

function swap(a, i, j) {
   let t = a[i];
   a[i] = a[j];
   a[j] = t;
}

UPDATE:如果不需要真正对数组进行排序，似乎可以在线性时间内解决问题:

public static int countGroupsLinear(int[] a) {
    Stack<Integer> stack = new Stack<>();
    stack.push(a[0]);
    for (int i = 1; i < a.length; i++) {
        if (a[i] >= stack.peek()) stack.push(a[i]);
        else {
            int last = stack.pop();
            while (stack.size() > 0 && a[i] < stack.peek()) stack.pop();
            stack.push(last);
        }
    }
    return stack.size();
}