Quick sort, query the k-largest number of the sequence

  Principal component ： The element on the left of the primary element is no larger than it , The elements on the right are larger than it

int randPartition(int *a,int l,int r) // Select the principal component randomly , Avoid a quick sort that degenerates into O(n^2)
{
    srand((unsigned int) time(NULL));   // Initialize random sequence , Prevent every rand() Return the same value
    int pos=rand()/(RAND_MAX*1.0)*(r-l)+l;  // pos=[l,r);
    swap(a[l],a[pos]);
    int temp=a[l];
    while(l<r)        // be based on two point Thought
    {
        while(l<r&&a[r]>temp)
            --r;
        a[l]=a[r];
        while(l<r&&a[l]<=temp)
            ++l;
        a[r]=a[l];
    }
    a[l]=temp;
    return l;

}

int rand(void):stdlib.h Next function , return

Go back to one 0 To rand_max Between pseudorandom numbers ;
To avoid getting the same sequence of random numbers every time the program runs , You can call srand function , With his parameters
The random number generator is initialized , It's usually srand((unsigned int) time(NULL));
time function ：
        time_t time(time_t timer):
        When timer yes NULL when , Get the current time （ from 1970-01-01 00:00:00 The number of seconds to now ）;

 void quicksort(int *a,int l,int r)  // Call the randomly selected primary function for quick sorting
{
    if(l<r)        // The length of the current interval is two minutes
    {
        int pos=randPartition(a,l,r);
        quicksort(a,l,pos-1);       //pos The sequence on the left is sorted
        quicksort(a,pos+1,r);        //pos The elements on the right are sorted
    }
}

 int randselect(int *a,int l, int r,int k)  // Select the... From the sequence k Large number , Time complexity O(n), Is a very good algorithm
{
    if(l==r)
        return a[l];    // Recursive boundary , This step is necessary , Otherwise, it will be queried k Larger than the sequence length , Can cause errors
    int pos=randPartition(a,l,r);
    int th=pos-l+1;        // At this time, No pos The sign is the... Of the sequence th Big
    if(th==k)
        return a[pos];
    else if(th<k)        
        randselect(a,pos+1,r,k-th);
    else
        randselect(a,l,pos-1,k);
}

 

/**
    3) Quick sort 
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;

/**
int my_partition(int *a,int l,int r) // Select the first element as the primary element to sort , The element on the left of the primary element is no larger than it , The elements on the right are larger than it 
{
    int temp=a[l];
    while(l<r)
    {
        while(l<r&&a[r]>temp)
            --r;
        a[l]=a[r];
        while(l<r&&a[l]<=temp)
            ++l;
        a[r]=a[l];
    }
    a[l]=temp;
    return l;
}
*/

//void quicksort(int *a,int l,int r)  // Call the main meta function for quick sorting 
//{
//    if(l<r)
//    {
//        int pos=my_partition(a,l,r);
//        quicksort(a,l,pos-1);
//        quicksort(a,pos+1,r);
//    }
//}

/**
int rand(void):stdlib.h Next function , Return to one 0 To rand_max Between pseudorandom numbers ;
 To avoid getting the same sequence of random numbers every time the program runs , You can call srand function , With his parameters 
 The random number generator is initialized , It's usually srand((unsigned int) time(NULL));
time  function ：
        time_t time(time_t timer):
         When timer yes NULL when , Get the current time （ from 1970-01-01 00:00:00  The number of seconds to now ）;
*/

int randPartition(int *a,int l,int r) // Select the principal component randomly , Avoid a quick sort that degenerates into O(n^2)
{
    srand((unsigned int) time(NULL));   // Initialize random sequence , Prevent every rand() Return the same value 
    int pos=rand()/(RAND_MAX*1.0)*(r-l)+l;  // pos=[l,r);
    swap(a[l],a[pos]);
    int temp=a[l];
    while(l<r)
    {
        while(l<r&&a[r]>temp)
            --r;
        a[l]=a[r];
        while(l<r&&a[l]<=temp)
            ++l;
        a[r]=a[l];
    }
    a[l]=temp;
    return l;

}

void quicksort(int *a,int l,int r)  // Call the random selection phase principal component function for quick sorting 
{
    if(l<r)
    {
        int pos=randPartition(a,l,r);
        quicksort(a,l,pos-1);
        quicksort(a,pos+1,r);
    }
}


int randselect(int *a,int l, int r,int k)  // Select the... From the sequence k Large number , Time complexity O(n), Is a very good algorithm 
{
    if(l==r)
        return a[l];    // Recursive boundary , This step is necessary , Otherwise, it will be queried k Larger than the sequence length , Can cause errors 
    int pos=randPartition(a,l,r);
    int th=pos-l+1;
    if(th==k)
        return a[pos];
    else if(th<k)
        randselect(a,pos+1,r,k-th);
    else
        randselect(a,l,pos-1,k);
}


int main()
{
    int n;
    cin >> n;
    int a[n];
    for(int i=0;i<n;++i)
        cin >> a[i];
    cout << randselect(a,0,n-1,11) << endl;
    quicksort(a,0,n-1);
    for(auto b: a)
        cout << b<< endl;

    cout << "Hello world!" << endl;
    return 0;
}

Here is an example ：

subject ： Given a set of integers , The integers in the set are different , Now let's divide it into two sets ,
    Make the union of these two sets the original set , Turn into an empty set , At the same time, the number of elements in the two subsets should be n1 and n2 The absolute value of
    As small as possible , The sum of the respective elements should be as large as possible . Output the absolute value of the difference between the sum of the elements of two sets .
    data:
            13
            1 6 33 18 4 0 10 5 12 7 2 9 3

analysis ： When N When it's even , The set selects the first half and the second half of the sequence as its own elements ; When it's odd , Interpretation No. (N+1)/2 Is it a positive number or a negative number , If it's a positive number , In the next set , If it's negative , Put it in
  In the previous set .

/**
     subject ： Given a set of integers , The integers in the set are different , Now let's divide it into two sets ,
     Make the union of these two sets the original set , Turn into an empty set , At the same time, the number of elements in the two subsets should be n1 and n2 The absolute value of 
     As small as possible , The sum of the respective elements should be as large as possible . Output the absolute value of the difference between the sum of the elements of two sets .

     analysis ： When N When it's even , The set selects the first half and the second half of the sequence as its own elements ; When it's odd ,
         Interpretation No.  (N+1)/2  Is it a positive number or a negative number , If it's a positive number , In the next set , If it's negative , Put it in 
         In the previous set 
    data:
            13
            1 6 33 18 4 0 10 5 12 7 2 9 3
*/

/**

    3) Quick sort 
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;


/**
int rand(void):stdlib.h Next function , Return to one 0 To rand_max Between pseudorandom numbers ;
 To avoid getting the same sequence of random numbers every time the program runs , You can call srand function , With his parameters 
 The random number generator is initialized , It's usually srand((unsigned int) time(NULL));
time  function ：
        time_t time(time_t timer):
         When timer yes NULL when , Get the current time （ from 1970-01-01 00:00:00  The number of seconds to now ）;
*/

int randPartition(int *a,int l,int r) // Select the principal component randomly , Avoid a quick sort that degenerates into O(n^2)
{
    srand((unsigned int) time(NULL));   // Initialize random sequence , Prevent every rand() Return the same value 
    int pos=rand()/(RAND_MAX*1.0)*(r-l)+l;  // pos=[l,r);
    swap(a[l],a[pos]);
    int temp=a[l];
    while(l<r)
    {
        while(l<r&&a[r]>temp)
            --r;
        a[l]=a[r];
        while(l<r&&a[l]<=temp)
            ++l;
        a[r]=a[l];
    }
    a[l]=temp;
    return l;

}

/** This function is not required 
void quicksort(int *a,int l,int r)  // Call the random selection phase principal component function for quick sorting 
{
    if(l<r)
    {
        int pos=randPartition(a,l,r);
        quicksort(a,l,pos-1);
        quicksort(a,pos+1,r);
    }
}
*/

int randselect(int *a,int l, int r,int k)  // Select the... From the sequence k Large number , Time complexity O(n), Is a very good algorithm 
{
    if(l==r)
        return a[l];    // Recursive boundary , This step is necessary , Otherwise, it will be queried k Larger than the sequence length , Can cause errors 
    int pos=randPartition(a,l,r);
    int th=pos-l+1;
    if(th==k)
        return a[pos];
    else if(th<k)
        return randselect(a,pos+1,r,k-th);
    else
        return randselect(a,l,pos-1,k);
}

int main()
{
    int n,sum=0;
    cin >> n;
    int a[n];
    for(int i=0;i<n;++i)
        cin >> a[i];
        
    if(n&1)
    {
        int k=(n+1)/2;
        int val=randselect(a,0,n-1,k);
        if(val>0)
        {
            for(int i=k-1;i<n;++i)  // Special attention needs to be paid here , The subscript is from 0 At the beginning 
                sum+=a[i];
            for(int i=0;i<k-1;++i)
                sum-=a[i];
        }
        
        else
        {
            for(int i=k;i<n;++i)
                sum+=a[i];
            for(int i=0;i<k;++i)
                sum-=a[i];
        }
    }

    else
    {
        int k=n/2;
        randselect(a,0,n-1,k);
        for(int i=k;i<n;++i)
            sum+=a[i];
        for(int i=0;i<k;++i)
            sum-=a[i];
    }
    cout << sum << endl;
    
    for(auto b: a)
        cout << b<< endl;
    return 0;
}