求n個數中第k大的數、前K大的數、快速排序

• 求n個數中第k大的數

#include <cstdlib>

#include <iostream>

/**

*求一個數組中的第k大數

*基本思想：

*以最後一個元素x為軸，把數組分為兩部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。這時有兩種情況：

*1.Sa中元素的個數小于k，則Sb中的第k-|Sa|個元素即為第k大數；

*2.Sa中元素的個數大于等于k，則傳回Sa中的第k大數。

*時間複雜度近似為O(n)

*/

using namespace std;

void exchange(int &a,int &b)

{

int temp;

temp=a;

a=b;

b=temp;

}

//快排的partition函數

int partition(int *a,int l,int r)

{

int i=l-1,j=l;

int x=a[r];

int temp;

for(j=l;j<r;j++)

{

if(a[j]>=x) //把比x大的數往前放

{

exchange(a[j],a[i+1]);

i++;

}

}

exchange(a[r],a[i+1]);

return i+1;

}

int k_element(int *a,int l,int r, int k)

{

if(l>=r)

return a[l];

int q=partition(a,l,r);

if(q==k-1)

return a[q];

else if(q>=k)

return k_element(a,l,q-1,k); //Sa中元素個數大于等于k

else

return k_element(a,q+1,r,k-(q+1)); //Sa中元素個數小于k

}

int main(int argc, char *argv[])

{

int a[100];

int length;

cin>>length;

for(int i=0;i<length;i++)

cin>>a[i];

cout<<k_element(a,0,length-1,4)<<endl;

system("PAUSE");

return EXIT_SUCCESS;

} 

•  求n個數中前K大的數

void exchange(int &a,int &b)
{
    int temp=a;
    a=b;
    b=temp;    
}
int partition(int *a,int l,int r)
{
    int i=l-1;
    int j=l;
    int x=a[r];
    for(j=l;j<r;j++)
    {
        if(a[j]>=x)
        {
            exchange(a[i+1],a[j]);
            i++;        
        }    
    }
    exchange(a[i+1],a[r]);
    return i+1;    
} 

void getKMax(int *a,int l,int r,int k)
{
    if(l>=r)
        return;
    int q=partition(a,l,r);
    if(q==k-1)
        return;
    else if(q>=k)
        return getKMax(a,l,q-1,k);
    else
        return getKMax(a,q+1,r,k-(q+1));    
}
int* findTopK(int *a,int n,int k)
{
    int *result = new int[k];
    getKMax(a,0,n-1,k);
    for(int i=0;i<k;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    for(int i=0;i<k;i++)
        result[i]=a[i];
    return result;        
}
           

• 快速排序

#include <cstdlib>

#include <iostream>

using namespace std;

int partition(int num[],int p,int r)

{

int i=p-1;

int j;

int x=num[r];

int temp;

for(j=p;j<r;j++)

{

if(num[j]<x)

{

temp=num[j];

num[j]=num[i+1];

num[i+1]=temp;

i++;

}

}

temp=num[r];

num[r]=num[i+1];

num[i+1]=temp;

return i+1;

}

void quick_sort(int num[],int p,int r)

{

if(p>=r)

return;

int q=partition(num,p,r);

quick_sort(num,p,q-1);

quick_sort(num,q+1,r);

}

int main(int argc, char *argv[])

{

int num[100];

int length;

int i;

cin>>length;

for(i=0;i<length;i++)

cin>>num[i];

quick_sort(num,0,length-1);

for(i=0;i<length;i++)

cout<<num[i]<<" ";

cout<<endl;

system("PAUSE");

return EXIT_SUCCESS;

}