2020-06-07 数列排序

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int arr[205];
int n;

int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (c<'0'||c>'9') {//符号位
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {//符号位
        x = x * 10 + c-'0';
        c = getchar();
    }
    return x*f;
}

void swap(int &x, int &y){
    int t = x;
    x = y;
    y = t;
}

void quickSort(int start,int end){
    
    int temp;
    int left, right;
    
    left = start;
    right = end;
    
    temp = arr[start];
    
    //printf("start:%d,end:%d,temp:%d\n",start,end,temp);
    
    while (left<right) {
        
        while (right>left && arr[right] >= temp) {
            right--;
        }
        
        //printf("right:%d ",right);
        
        while (right>left && arr[left]<=temp) {
            left++;
        }
        
        //printf("left:%d\n",left);
        
        swap(arr[left],arr[right]);
    }
    
//    for (int i = 1; i<=n; i++) {
//        printf("%d",arr[i]);
//    }
    
    //printf("\n");
    
    swap(arr[start],arr[left]);
    
    if(start < left)quickSort(start, left);
    if(right < end)quickSort(left+1, end);
}

int main() {
    n = read();
    
    for (int i = 1; i<=n; i++) {
        arr[i] = read();
    }
    
    quickSort(1,n);
    for (int i = 1; i<=n; i++) {
        if (i==1) {
            printf("%d",arr[i]);
        }else{
            printf(" %d",arr[i]);
        }
    }
    return 0;
}