#include <stdlib.h>

namespace dksl

{

    /*

    *交换

    */

    void Swap(int* numArray,int swapFrom,int swapTo)

    {

        int temp=numArray[swapFrom];

        numArray[swapFrom]=numArray[swapTo];

        numArray[swapTo]=temp;

    }

    /*

    *随机化快排

    */

    int RandomizedPartition(int* numArray,int head,int tail)

    {

        int r=rand()%(tail-head+)+head;

        Swap(numArray,r,tail);

        int pivot=numArray[tail];

        int i=head-;

        int j=tail;

        while(true)

        {

            do

            {

                i++;

            }while (i<=tail&&numArray[i]<pivot);

            do

            {

                j--;

            }while (j>=head&&numArray[j]>pivot);

            if(j<i)

                break;

            Swap(numArray,i,j);

        }

        Swap(numArray,j+,pivot);

        return j+;

    }

    /*

    *选择任意顺序统计量，numArray为待选择数组，head为数组开始位置索引，tail为数组结束位置索引，i为待选择的第i+1小的值

    */

    int RandomizedSelect(int* numArray,int head,int tail,int i)

    {

        if(head==tail)

            return numArray[head];

        int q=RandomizedPartition(numArray,head,tail);

        int k=q-head+;

        if(i==k)

            return numArray[q];

        else if(i<k)

            return RandomizedSelect(numArray,head,q-,i);

        else

            return RandomizedSelect(numArray,q+,tail,i-k);

    }

}

// RandomizedSelect.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include <iostream>

#include "RandomizedSelect.h"

using namespace std;

using namespace dksl;

int _tmain(int argc, _TCHAR* argv[])

{

    int a[] = {, , , , , , , , , };

    cout<<RandomizedSelect(a,,,)<<endl;

    system("PAUSE");

    return ;

}