给定问题标准，是否有比冒泡排序更有效的排序此数组的形式？

Question

我在 HackerRank 上练习了一些更多的问题，我运行进入了这个叫做 "New Year Chaos" 的问题。基本上前提是对数组进行排序并计算所做的切换。要注意的是，不允许进行 2 次以上的切换。 BubbleSort 通过了前几个测试，但在其余测试中超时。是否有更有效的数组排序算法仍然考虑到开关的数量？我尝试了 mergeSort 和 quickSort，但是像这样划分数组时很难跟踪开关。

问题提示：今天是元旦，每个人都在排队乘坐 Wonderland 过山车！有很多人在排队，每个人都贴着一张标明他们在队列中的初始位置的贴纸。初始位置从行的前面到后面递增。

队列中的任何人都可以贿赂直接在他们前面的人交换位置。如果两个人交换位置，他们仍然会佩戴相同的贴纸，表示他们原来排队的位置。一个人最多可以贿赂另外两个人。例如，如果 n = 8 并且第 5 个人贿赂第 4 个人，则队列将如下所示：{1, 2, 3, 5, 4, 6, 7, 8}。

被这个混乱的队列迷住了，您决定必须知道要使队列进入当前状态所发生的最少贿赂次数！

public class LineBribing {

    static int[] replace(int[] q, int i, int n) {
        int temp = q[i];
        q[i] = q[n];
        q[n] = temp;
        return q;
    }

    static void minimumBribes(int[] q) {
        int count = 0;
        for (int i = 0; i < q.length - 1; i++) {
            if (q[i] > i + 3 || q[i] < i - 1) {
                System.out.println("Too chaotic");
                return;
            }
            if (q[i] > q[i + 1]) {
                count++;
                replace(q, i, i + 1);
                i = 0;
            }
        }
        System.out.println(count);
    }

    public static void main(String[] args) {
        int[] test = {1, 2, 5, 3, 4, 7, 8, 6};
        int[] test2 = {1, 2, 5, 3, 7, 8, 6, 4};
        minimumBribes(test);
        minimumBribes(test2);

    }
}

给定 main 方法中的输入，测试 1 的输出应为 4（开关：5、3 at index = 3 | 5、4 at index = 4 | 8、6 at index = q.length - 1 | 7, 6 at index = q.length - 2) and "Too Chaotic" for test 2 (因为 5 is > 2 switches away from its initial position)

Answer 1

我觉得这道题不需要对数组进行排序。你只需要计算超过一个人的人数。注意：

一个人最多可以贿赂2个不同的人
一个人可以贿赂在他面前的人所以，你应该先判断谁行贿超过2人。然后统计超车人数

我的 Java 代码是这样的：

        int ans = 0;
        for (int i = q.length - 1; i >= 0; i--) {
            if (q[i] - (i + 1) > 2) {
                System.out.println("Too chaotic");
                return;
            }
            for (int j = Math.max(0, q[i] - 2); j < i; j++) {
                if (q[j] > q[i]) {
                    ans++;
                }
            }
        }
        System.out.println(ans);

给定问题标准，是否有比冒泡排序更有效的排序此数组的形式？

Is there a more efficient form of sorting this array than bubblesort given the problem criteria?

java

arrays

bubble-sort