排序次数

[编程题]排序次数

热度指数：516 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小摩有一个N个数的数组，他想将数组从小到大排好序，但是萌萌的小摩只会下面这个操作：

任取数组中的一个数然后将它放置在数组的最后一个位置。

问最少操作多少次可以使得数组从小到大有序？

输入描述:

首先输入一个正整数N，接下来的一行输入N个整数。(N <= 50, 每个数的绝对值小于等于1000)

输出描述:

输出一行操作数

示例1

输入

4
19 7 8 25

输出

说明

19放到最后，25放到最后，两步完成从小到大排序

算法知识视频讲解

Java

GHYYYS1314

这个只需要记录一下逆序元素的个数，然后思想上把逆序的元素从小到大移动到末尾就行（不用真的移动）

//遍历数组，判断一个数如果是逆序元素（后面有比他小的数），计数加一就可，算法统计出所有逆序元素个数，别忘了判断数组中最后一个数是不是逆序元素，只需要在最后面判断数组中最后一个数和已知最小的逆序元素的大小。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr =new int[n];
        for(int i = 0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int min = Integer.MAX_VALUE;
        int count = 0;
        for(int i = 0;i<n;i++){
            for(int j = i+1;j<n;j++){
                if(arr[j] < arr[i]){
                    count++;
                    min = arr[i] < min?arr[i]:min;
                    break;
                }
            }
        }
        if(count == 0){
            System.out.println(count);
        }
        else{
            int k = n-1;
            while(k>0){
                if(arr[k] > min && arr[k] > arr[k-1]){
                    count++;
                    k--;
                }
               else
                    break;
            }
            System.out.println(count);
        }
    }
}

编辑于 2019-09-27 16:52:41 回复(2)