排序次数

[编程题]排序次数

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

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

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

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

输入描述:

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

输出描述:

输出一行操作数

示例1

输入

4
19 7 8 25

输出

说明

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

算法知识视频讲解

C/C++

Kaitle

//1.输入一个整数和一串数组
//2.遍历比较相邻的两个数，若大于，则利用push_back()将元素放入数组的末尾
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,s=0;
    vector<int> a;
    cin>>n;
    int x;
    for(int i=0;i<n;i++){
        cin>>x;
        a.push_back(x);
    }
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(a[i]>a[j])
            {
                a.push_back(a[i]);
                s++;
                break;
            }
        }
    }
    cout<<s;
}

发表于 2020-04-25 00:26:37 回复(0)

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)

sunshuai

n = int(input())
l = list(map(int, input().split()))

flag = [False] * len(l)

for i in range(len(l) - 1):
    for j in range(i + 1, len(l)):
        if l[j] < l[i]:
            flag[i] = True
            break

for i in range(0, len(l) - 1):
    if l[i] < l[-1] and flag[i] == True:
        flag[-1] = True

print(flag.count(True))

发表于 2020-05-15 13:11:23 回复(0)

C/C++

jiajun107

按照GHYYYS1314同学的思路提供的一种C++写法

#include <iostream>
#include <vector>
using namespace std;
int  main(){
    int n;
    cin>>n;
    vector<int> vi;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        vi.push_back(x);
    }
    int count=0;
    vector<int> v;
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(vi[j]<vi[i]){
                count++;
                v.push_back(vi[i]);
                break;
            }
        }
    }
    for(int i=0;i<v.size();i++){
        if(vi[n-1]>v[i]){
            count++;
            break;
        }
    }
    cout<<count<<endl;
    return 0;
}

发表于 2020-02-10 13:56:52 回复(1)

我讨厌递归算法

1：解题思路：每次移动最小的到最后即可完成任务。

2：有序的部分不要移动 19 7 8 25 中 7 不需要移动，8不需要移动， 19 需要移动，25 需要移动

某个位置的数字是否需要移动取决于后面有没有比他小的数字，有就需要移动，没有就不需要移动

3：最后一位是否需要移动需要单独处理

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        int[] arr = new int[N];
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt();
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        int count = 0 ;

        boolean flag = false ;  // 有没有数学移动到最后

        for (int i = 0; i < arr.length - 1; i++) {
            boolean tmp = needMove(arr, i);
            if (tmp) {
                flag = true;
                count++;
            }
        }

        // 判断最后一位需不需要移动

        if(flag){
            // 不是最大的不需要移动

            boolean flag1 = true ;
            if (arr[arr.length - 1] == max) {

                // 如果是最大的，还取决于前面有没有最大值  3 2 3 ; 移动一次即可
                for (int i = 0; i < arr.length - 1; i++) {
                    if (arr[i] == max) {
                        flag1 = false;
                        break;
                    }
                }

                if (flag1) {
                    count++;
                }
            }

        }


        System.out.println(count);

    }


    private static boolean needMove(int[] arr, int i) {

        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[i]) {
                return true;
            }
        }

        return false;
    }

}

发表于 2019-08-26 10:51:40 回复(0)

正在卷的三文鱼很讨厌吃香菜

这道题的数据不好，没有考虑到2 1 2这种情况，开始我也想错了，后面想到了一个简单的方法，每次从上次查找到的下标的后一位开始查找，这样就可以解决2 1 2这种情况，具体代码如下：

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[] a=new int[n];
        int[] b=new int[n];
        String[] line=br.readLine().split(" ");
        for(int i=0;i<n;i++){
            a[i]=Integer.parseInt(line[i]);
            b[i]=a[i];
        }
        Arrays.sort(b);
        int start=0;
        for(int i=0;i<n;i++){
            int next=search(a,b[i],start);
            if(next==n){
                System.out.println(n-i);
                return;
            }
            start=next+1;
        }
        System.out.println(0);
    }
    private static int search(int[] a,int target,int start){
        for(int i=start;i<a.length;i++){
            if(a[i]==target){
                return i;
            }
        }
        return a.length;
    }
}

编辑于 2019-08-23 20:04:26 回复(0)