有趣的排序

	importjava.util.Scanner;



	publicclassMain {



	//  思路是这样的，这串数字可以分为两类：一类是不动数另一类是动数。动数的个数就是算法要移动的次数。



	//  不动数满足两个条件：1.后面的数都大于该数。并且,2.前面最小动数大于该数。



	//  动数和不动数刚好相反：1.后面的数至少有一个数大于该数。或者2.前面最小动数小于该数。



	//  不是不动数的数就是动数。只需要找到所有动数个数，就能得到算法移动次数。



	    publicstaticvoidmain(String args[]){



	        Scanner sc = newScanner(System.in);



	        intpoint_num = sc.nextInt();



	        int[] list = newint[point_num];



	        for(inti = 0; i < list.length; i++){



	            list[i] = sc.nextInt();



	        }



	 



	        intmove_count = 0;  // 记录动数的个数。



	        intmin_move_value = 1001;  // 初始化最小动数的值。



	        for(inti = 0; i < list.length; i++){



	             



	            if(min_move_value < list[i]){



	                move_count++;  // 满足动数条件2



	                continue;



	            }



	 



	            for(intj = i+1; j < list.length; j++){



	                if(list[i]>list[j]){



	                    move_count++;  // 满足动数条件1



	                    min_move_value = list[i];  // 该动数与最小动数值比较



	                    break;



	                }



	            }



	        }



	 



	        System.out.println(move_count);



	    }



	}

//大概的想法就是，首先怎样移操作最少：首先找到数组里面最小的一个，显然这个数是不需要移动的。
// 同时第二小，并且在第一小后面也不需要移动，以此类推，直到出现了一个第k小并且它在第k-1小前面
// 显然这个时候需要移动了，一旦这个数移动了，后面所有的第k+1到n小的数都需要移动，因此总的移动次数为n-k。
import java.util.Scanner;
import java.util.Arrays;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[] num = new int[n];
            int[] sorted = new int[n];
            int min_op = 0;
            for(int i=0;i<n;i++){
                num[i] = sc.nextInt();
                sorted[i] = num[i];
            }
            Arrays.sort(sorted);
            for(int i=1;i<n;i++){
                int forward = 0;
                int backward = 0;
                for(int j=0;j<n;j++){
                    if(num[j]==sorted[i-1])forward=j;
                    if(num[j]==sorted[i])backward=j;
                }
                if(backward<forward){
                    min_op = n-i;
                    break;
                }
            }
            System.out.println(min_op);
        }
    }
}

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[55],b[55],n,i,res,j;
int main(){
    for(scanf("%d",&n),i=0;i<n;i++)
        scanf("%d",a+i),b[i]=a[i];
    for(sort(b,b+n),i=0;i<n;i++)
        if(a[i]==b[j]) res++,j++;
    printf("%d\n",n-res);
}

#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin>>n;
	vector<int> vec(n);
	for(int i=0;i<n;i++)
	{
		cin>>vec[i];
	}
	vector<int> vec2(vec.begin(),vec.end());
	sort(vec2.begin(),vec2.end());//排序
	for(int i=0;i<n-1;i++)
	{
   //从最小的数开始找，在排序好的序列中，找相邻的两个数m,n,其中m<n;
   //如果在原始序列中m的位置大于n,就需要把n移到后面，然后所有大于n的数就都需要移到后面。
		if((find(vec.begin(),vec.end(),vec2[i])-find(vec.begin(),vec.end(),vec2[i+1]))>0)
		{
			cout<<n-i-1<<endl;
			return 0;
		}
	}
	cout<<0<<endl;
	return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String[] s = sc.nextLine().split(" ");
        int[] arr = new int[n];
        int[] brr = new int[n];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(s[i]);
            brr[i] = Integer.parseInt(s[i]);
            min = Math.min(arr[i], min);
        }
        int p = 0;
        Arrays.sort(brr);               // 升序
        for (int i = 0; i < n; i++) {
            if(arr[i] == brr[p])    p++;
        }
        System.out.println(n - p);
    }
}

先把数组从小到大排列，然后逐次比较sorted[i]和sorted[i+1]在array中的下标,如果i下标大于i+1下标count加1同时对array进行操作

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            int num=scan.nextInt();
            int[] array=new int[num];
            int[] sorted=new int[num];
            for(int i=0;i<num;i++){
                array[i]=scan.nextInt();
                sorted[i]=array[i];
            }
            int count=0;
            Arrays.sort(sorted);
            for(int j=0;j<num-1;j++){
                if(index(sorted[j],array)>index(sorted[j+1],array)){
                    count++;
                    int temp=sorted[j+1];
                    for (int k=index(sorted[j+1],array);k<array.length-1;k++){
                        array[k]=array[k+1];
                    }
                    array[array.length-1]=temp;
                }
            }
            System.out.println(count);
        }
    }
    public static int index(int param,int[] array){
        for(int i=0;i<array.length;i++){
            if(array[i]==param){
                return i;
            }
        }
        return -1;
    }
}

//现在我们的思路是找出有序的最小的一组元素，先找出v1的最小元素，记住值imin和位置back，和前一位置相比
//若该位置在前一位置front之后，令front=back，删除该位置元素，此处必须为“<=”,因为删除元素之后，之后back是可以和front相等的
//若存在back>front,则直接结束
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n,m;
	int cnt = 0;
	vector<int> v,v2;
	cin>>n;
	for(int i = 0;i != n;i++){
		cin>>m;
		v.push_back(m);
		v2.push_back(m);
	}
	sort(v2.begin(),v2.end());//将v2排序
	int front = -1;
	int back;
         for(int i = 0;i != n;i++){
		int imin = 1001;
		for(int j = 0;j != v.size();j++){
			if(v[j] < imin){
				imin = v[j];
				back = j;
			}
		}
		if(v2[i] == imin){
	    	if(front <= back){
		    	cnt++;
		    	front = back;
		    	v.erase(v.begin()+back);
	    	}
    		else
	    	    break;
    	}
    }
	cout<<n-cnt<<endl;
} 

//借鉴各位大神的思路  把不需要移动的数字个数记录下来
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n,a[50];
    int i =0;
    int count = 0;
    cin >> n;
    vector<int> arr;
    while(n--)
    {
        int temp ;
        cin >> temp;
        a[i++] = temp;
        arr.push_back(temp);
    }
    sort(arr.begin(),arr.end());
    int m = 0;
    for(int j = 0;j<i;j++)
    {
        if(a[j]==arr[m])
        {
            count++;
            m++;
        }
    }
    cout << i-count << endl;
}

if __name__ == '__main__':
    #解法1，易理解
    n = int(sys.stdin.readline().strip())
    alist = map(int,sys.stdin.readline().strip().split(" "))
    newlist = sorted(alist)
    mdict = {}
    org = len(alist)
    nmax = org
    for i,data in enumerate(alist):
        mdict[data] = i
    for i in range(org-1):
        # 以已排序数组中元素为参照，依次在待排数组中查看相邻元素的小标是否满足“左小右大”原则，不满足的，将大值插入到数组末尾。
        if mdict[newlist[i]]>mdict[newlist[i+1]]:
            mdict[newlist[i+1]]=nmax
            nmax+=1
    print nmax-org

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;
int main()
{
    int N, temp;
    cin>>N;
    vector<int> v;
    map<int, int> m;
    for(int i=0; i<N; ++i)
    {
        cin>>temp;
        v.push_back(temp);
        m[temp]=i;
    }
    sort(v.begin(), v.end());
    int t=N, count=0;
    for(int i=0; i<N-1; ++i)
    {
        if(m[v[i]]>m[v[i+1]])
        {
            m[v[i+1]]=t++;
            ++count;
        }
    }
    cout<<count<<endl;
}

/*另类解法：*/
#include<iostream>
#include<list>
intmain()
{
    int N;
    std::cin >> N;
    std::list<int>numlist;//创建链表
    int answer=0, power = 0, swich;//初始化
    for(int i = 0; i != N; ++i)
    {
        int number;
        std::cin >> number;
        numlist.push_back(number);
    }//把数存入链表
    numlist.reverse();//反转链表
    while(numlist.size()>1)
    {
        swich = 0;
        intfirstnum = numlist.front();//获取第一个元素
        numlist.pop_front();//删掉第一个元素
        for(auto p=numlist.begin();p!=numlist.end();)//遍历链表
        {
            if(*p > firstnum)//比第一个数大？
            {
                ++answer;//答案加一
                swich = 1;//开关触发
                p=numlist.erase(p);//删掉满足条件的点；
            }
            else ++p;
        }
        if(swich)//如果开关触发
        {
            answer += power;//释放能量
            power = 1;//重置能量
        }
        else
            ++power;//积蓄能量
    }
    std::cout << answer;
    return 0;
}

#include<iostream>
#include<string>
using namespace std;
  
int main(){
    int N, a[50];
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> a[i];
    }
    // find longest sorted subarray embedded in the array that starts from the min,
    // then the min steps is N-N_sorted_subarray
    //
    // go through every element, store the first element in the subarray, if the next element
    // is larger than the first one, then include it in the subarray, if not, reduce the subarray
    // until it can include this one. Also record the smallest element so far that is not in the subarray,
    // if coming element is larger than that, then ignore.
    // Finally, output the length of subarray
    int asub[50]={-1000};
    int j=0;
    int min_out=1000;
    asub[0]=a[0];
    for(int i=1;i<N;i++){
        if(a[i]<=min_out){
            while(j>=0 && asub[j]>=a[i]){
                min_out=asub[j];
                j--;
            }
            j++;
            asub[j]=a[i];
        }
    }
    cout << N-j-1;
      
    return 0;
}

	//思路是这样的，从最小的值开始找，找到最长的按数组中的值的大小严格出现的最长序列，然后答案就是数组长度-最长序列的长度



	



	importjava.util.*;



	publicclassMain {



	    staticclassp{



	        intval;



	        intindex;



	        publicp(intv,inti){



	            val=v;



	            index=i;



	        }



	    }



	    publicstaticvoidmain(String[] args){



	        Scanner in=newScanner(System.in);



	        intn=in.nextInt();



	        p[] data=newp[n];



	        for(inti=0;i<n;++i){



	            intv=in.nextInt();



	             



	            data[i]=newp(v, i);



	        }



	        Arrays.sort(data,newComparator<p>() {



	 



	            @Override



	            publicintcompare(p o1, p o2) {



	                // TODO Auto-generated method stub



	                returno1.val-o2.val;



	            }



	        });



	        intlen=1;



	        ints=data[0].index;



	        for(inti=1;i<n;++i){



	            if(data[i].index>s){



	                len++;



	                s=data[i].index;



	            }else{



	                break;



	            }



	        }



	        System.out.println(n-len);



	         



	        in.close();



	    }



	}

递归，先找到最小数的数组下标，以该元素分为两部分，前一部分是要移动的，并且要找到前一部分中最小的元素min。
然后，从后一部分找比min要大的元素个数，这些也是需要移动的，然后找比min要小的元素，这些元素是待定的，把他们存入另一个数组中，然后以这个数组为递归的新参数，递归调用，直到不需要移动。

#include<iostream>
using namespace std;

int min(int *a, int n)
{
    int mi = 0;
    for(int i = 1; i<n; i++) {
        if( a[mi] >a[i])
            mi = i;
    }
    return mi;
}

int dp(int *a, int n) {
    if(n == 0)
        return 0;
    int pos = min(a,n);
    int y1 = pos;
    if(pos == 0 )
        y1 = dp(a+1, n-1);
    else {
        int mi = min(a,pos);
        int b[n];
        int t = 0;
        for(int i = pos +1; i< n; i++) {
            if(a[mi] < a[i] ) {
                y1++;
            } else {
                b[t] = a[i];
                t++;
            }
        }
        y1 = y1 + dp(b,t);
    }

    return y1;
}

int main()
{
    int n;
    while(cin>>n) {
        int a[n];
        for(int i = 0; i<n; i++) {
            cin>>a[i];
        }
        int t = dp(a,n);
        printf("%d\n", t);
    }

}

//假设数组A=[1,3,2,5,4],先进行排序，变成数组B=[1,2,3,4,5]，然后开始顺序检索B数组
//中的数字，会发现2在1后面，3在2前面，所以我们要从3开始重排，因为只能把3移到无序
//数组末端，所以所有数组B在3之后的元素都要进行重排，所以重排次数就是数组大小减去
//第一个重排数在数组B中的序数。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int size;
    vector <int> arr,arr2;
    cin>>size;
    
    int temp=0;
    for(int i=0;i<size;i++)
        {
        cin>>temp;
        arr.push_back(temp);
        arr2.push_back(temp);
    }
    
    sort(arr.begin(),arr.end());

    int g=0;
    
    for(int h;h<size;h++)
        if(arr2[h]==arr[g])
        {
            g++;
            continue;
        }

    	cout<<size-g;
             
    return 0;
}