2017级算法第二次上机-A.ModricWang's Real QuickSort Query

其实这道题更多的是模拟题的感觉。按照题目给定的思路写即可。C++ 可以直接使用STL里面的sort。

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

const int maxlen=1e6 + 10;
int ar[maxlen];
void swap(int *p,int *q){
    int temp;
    temp=*p;
    *p=*q;
    *q=temp;
}
int main(){
    
    int n,i,j,k,mid,p,q;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&ar[i]);
    i=0;
    j=n-1;
    mid=ar[n/2];
    while(i <= j){
        while(ar[i] < mid)
            i++;
        while(ar[j] > mid)
            j--;
        if(i<=j){
            swap(ar[i],ar[j]);
            i++;
            j--;
        }
    }
    n=i;
    i=0;
    j=n-1;
    mid=ar[n/2];
    while(i <= j){
        while(ar[i] < mid)
            i++;
        while(ar[j] > mid)
            j--;
        if(i<=j){
            swap(ar[i],ar[j]);
            i++;
            j--;
        }
    }

    for(k=i;k<n;k++)
        printf("%d ",ar[k]);
    printf("
");
    return 0;
}