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

Question

我在HackerRank上练习了更多问题，然后遇到了一个叫做“新年混乱”的问题。基本上，前提是对阵列进行排序并计算所进行的开关。渔获是没有数字的，允许进行超过2个开关。 BubbleSort通过了前几个测试，但在其余测试上超时。是否有一个更有效的数组排序算法仍考虑到交换机的数量？我尝试过mergeSort和quickSort，但是在像这样分割数组时很难跟踪开关。

问题提示：今天是元旦，每个人都在排队玩仙境过山车！有很多人在排队，每个人都戴着一个贴纸，指示他们在队列中的初始位置。初始位置从行的开头到行的后面递增。

队列中的任何人都可以贿赂在他们前面的人以换位。如果两个人调换职位，他们仍然会贴上相同的标签，以表示他们原先的位置。一个人最多可以贿赂另外两个人。例如，如果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);

    }
}

给出主方法中的输入，测试1的输出应为4（开关：索引处= 3的5、3 = 5，索引处的4 = 8、8，索引处的4 = 8，8，索引处= q.length-1 | 7 ，在索引= q.length-2处的6）和测试2的“太混乱”（因为5离其初始位置> 2个开关）

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);