奇怪的排序问题题解

【前言】
无。
【暴力】
搜索
O(2^n)
【正解】
对于一个位置，如果这个位置后面有比它小的数，那这个位置肯定是要动的，这显然是答案的下限。
我们来证明一下这个下限是可以达到的。
有一种很显然的排序方法可以达到这个下限。
从后往前看每个位置，如果该位置的身高大于后面的位置，则进行一次选择，这样就达到了下限。
这种方法可以保证每次选择，被选择的位置到队尾(不包含被选位置)已经形成升序，排序后被选择的位置到队尾(包含被选位置)也变成了升序，这样每个必须要动的位置被动了一次，刚好达到下限。
复杂度O(n)
参考代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @return int整型
     */
    int wwork(int n, int* a, int aLen) {
        // write code here
    int mn=n+1,ans=0;
    for (int i=n-1;i>=0;i--)
    {
        if (a[i]>mn) ans++;
        mn=min(a[i],mn);
    }
    return ans;
    }
};