链接：https://ac.nowcoder.com/acm/problem/21803
来源：牛客网

牛牛刚学完排序，他准备拿n个数一展身手，但是他发现现实中的排序与课堂里的排序不一样

每次他只能对连续的n-1个数进行从小到大的排序

请问牛牛最少需要几次排序能将所有的数排成有序的

这道题目其实是一道简单的入门题,不需要多复杂的计算和思考.但是刷题比较少的小萌新可能第一时间看见这题目会有点懵,因此我们首先来分析一下题目.

首先这题题目虽然是"牛牛的排序",但是不需要我们写排序算法,只是判断根据他提供的方式将数据排序成已排序数列需要多少步.就是判断需要执行多少次题目给的排序方法才能将数据排序完成.

"每次他只能对连续的n-1个数进行从小到大的排序"就表示只有两种排序方法:1.将第一个数到倒数第二个数排序完成.2.将第二个数到最后一个数排序完成.

因此,就可以将数据分为三部分:
第一部分:第一个数
第二部分:中间的所有数
第三部分:最后一个数

而排序后序列就是要保证第一位数为最小值,最后一位为最大值.所以我们可以根据最大值和最小值所在的位置判断需要执行几步方法才能完成数组排序.可以得下图

最大值的次数如下:

因此可得下图

其中当一开始第一位就为最小值,最后一位为最大值时.由于第二部分可能为乱序,因此我们需要在代码中特殊判断一下.
而表格中某些行出现减一的情况是因为本题只有两种排序方法,所以当第一部分通过一次操作做完完整的两种排序方法移至第三部分时第三部分必定会移动至中间部分.因此就需要在加上第三部分移动次数的时候执行减一操作.

通过表3再加上前文所言的特殊情况就可以得到这道题的所有解了.以下附出java代码.

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
   public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int array[] = new int [n];
        int min = 9999999;
        int max = -1;
        int flag = 1;//flag=1表示数组中前一位都比后一位小
        for(int i = 0; i < n; i++) {

            array[i] = in.nextInt();//将数据存入数组
            if(min > array[i]) min = array[i];
            if(max < array[i]) max = array[i];//获取最大最小值
            if(flag == 1 && i>0 && i<n-1 &&array[i]<array[i-1]) {
                flag = 0;//如果数组非已排序数列,则将flag置0;
//                System.out.println(i+"--flag:"+flag);
            }
        }
        int a = array[0];//将首位数字存入a变量中
        int b = array[n-1];//将首位数字存入b变量中
//        if(a==min && b==max && flag==1) System.out.println("0");//已排序数列,直接输出0
        if(a==min) {//首位为最小值
            if(flag==1&&b==max) {
                System.out.println("0");//已排序数列,直接输出0
                return;
            }
            else {
                System.out.println("1");//首位为最小值,后面n-1位未排序,直接一次排序即可完成排序
                return;
            }
        }
        if(b==max) {//尾位不为最大值
            if(flag==1&&a==min) {
                System.out.println("0");//已排序数列,直接输出0
                return;
            }
            else {
                System.out.println("1");//首位为最小值,后面n-1位未排序,直接一次排序即可完成排序
                return;
            }
        }
        if(a==max&&b==min) {
            System.out.println("3");//如果首位为最大值,尾位为最小值,则需要3此
            return;
        }
        else System.out.println("2");
    }
}

ps:代码写的有点不够简洁,但我实在太懒了,不愿意修改.QAQ!!!!!