数组的partition调整补充问题

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>num(n);
    for(int i=0;i<n;i++)
        cin>>num[i];
    int left=-1,right=n,i=0;
    while(i<right)
    {
        if(num[i]==0)
            swap(num[i++],num[++left]);
        else if(num[i]==2)
            swap(num[i],num[--right]);
        else
            i++;
    }
    for(int i=0;i<n;i++)
        cout<<num[i]<<" ";
    return 0;
}

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
        
        int p0=0;
        int p2 = n-1;
        for(int i=0;i<=p2;i++){
            while(p0 < n && arr[p0]==0) p0++;
            while(p2>=0 && arr[p2]==2) p2--;
            if(arr[i]==0 && i>=p0){
                swap(arr,i,p0);
                i--;
            }else if(arr[i]==2 &&i<=p2){
                swap(arr,i,p2);
                i--;
            }
        }
        
        for(int i=0;i<n;i++){
            System.out.print(arr[i] +" ");
        }
	}
    
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, x, b[3];
    memset(b, 0, sizeof(b));
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        b[x]++;
    }
    for(int i=0;i<=2;i++)
        for(int j=1;j<=b[i];j++)
            cout<<i<<" ";
    return 0;
}

//荷兰国旗问题
/*
1）若遍历到的位置为0，则说明它一定位于A的左侧。于是就和A处的元素交换，同时向右移动A和C。
2）若遍历到的位置为1，则说明它一定位于AB之间，满足规则，不需要动弹。只需向右移动C。
3）若遍历到的位置为2，则说明它一定位于B的右侧。于是就和B处的元素交换，交换后只把B向左移动，C仍然指向原位置。（因为交换后的C可能是属于A之前的，所以C仍然指向原位置


*/
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> vec;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        vec.push_back(tmp);
    }
    //开始荷兰国旗
    int left_index = -1;
    int right_index = vec.size();
    int index = 0;
    while (index < right_index) { // 000 0 110 1 ==> 0000 0 011 1
        if (vec[index] == 0 ) {
            left_index ++;//先扩张一下右边界， 新扩张的边界 步满足 边界内部条件
            swap(vec[left_index],vec[index]);// 把满足边界条件的值进行交换
            index ++; // index 左边一定 不是 0 就是 1，所以 index ++ 即可
        } else if (vec[index] == 2) {
            right_index --;
            swap(vec[index],vec[right_index]);
            // 但是从右边换过来的 可能是 0 1 2 ，所以需要再次验证
        } else {
            index ++;
        }
    }
    for (auto x : vec) 
        cout << x <<  " ";
    return 0;
}

n = input()
#对输入的列表排序
ls = sorted(list(input().split()))
print(' '.join(ls))

def main():
    n=int(input())
    l=list(map(int,input().split()))
    
    n0,n1,n2=0,0,0
    for i in range(n):
        if l[i]==0:
            n0+=1
        elif l[i]==1:
            n1+=1
        else:
            n2+=1
    for i in range(n0):
        print(0,end=" ")
    for i in range(n1):
        print(1,end=" ")
    for i in range(n2):
        print(2,end=" ")
        
if __name__=="__main__":
    main()

#include <bits/stdc++.h>
using namespace std;

void SortPartially(vector<int>& arr) {
    for (int i = 0, left = 0; i < arr.size(); ++i) {
        if (arr[i] == 0)
            swap(arr[left++], arr[i]);
    }

    for(int i = arr.size()-1, right = arr.size()-1; i >= 0; --i) {
        if (arr[i] == 2)
            swap(arr[right--], arr[i]);
    }
}

int main()
{
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    SortPartially(arr);
    for (auto c : arr) {
        cout << c << " ";
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n; scanf("%d", &n);
    int num;
    int a=0, b=0, c=0;
    for(int i=0; i<n; i++){
        scanf("%d", &num);
        if(num == 0) a++;
        else if(num == 1) b++;
        else c++;
    }
    for(int i=0; i<(a+b+c); i++){
        if(i<a) printf("%d ", 0);
        else if(i>=a && i<a+b) printf("%d ", 1);
        else printf("%d ", 2);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;++i) cin>>v[i];
    // 三指针
    // i左侧为已排序好的0
    // k右侧为已排好序的2
    // j为工作指针
    int i = 0;
    int k = n-1;
    int j = 0;
    while(j<=k) 
    {
        if(v[j]==1)
            ++j;
        else if(v[j]==0)
            swap(v[i++],v[j++]);
        else swap(v[k--],v[j]);
    }
    for(auto item : v)
        cout<<item<<" ";
    return 0;
}