随机选择算法

对于一个无序的数列，如何以线性时间选择其中位数？快速排序可以，但时间复杂度为O(nlogn)，我们并不想得到整个数列的顺序，只需要其中位数，即第n/2个数。因此，我们从快速排序算法的思路得到随机选择算法，时间复杂度为o(n)

#include <iostream>

using namespace std;

#include <stdlib.h>
#include <conio.h>
#include <time.h>

int Partition(int L[],int first,int last)
{
    int left = first;
    int right = last;
    int pivot = L[first];

    while (left < right)
    {
        while (left < right && L[right] >= pivot)right--;
        L[left] = L[right];
        while (left < right && L[left] < pivot) left++;
        L[right] = L[left];
    }
    L[left] = pivot;
    return left;
}
int Random_Partition(int L[],int first,int last)
{
    int i;
    int temp;

    srand((unsigned)time(NULL));
    i = rand() % (last - first + 1)+first;

    temp = L[i];
    L[i] = L[last];
    L[last] = temp;
    return Partition(L,first,last);
}
int RandomizeSelect(int L[],int first,int last,int mid_num)
{
    int q,k;

    if(first == last)return L[first];

    q = Random_Partition(L,first,last);
    k = q - first + 1;

    if (mid_num == k)return L[q];
    else if (mid_num < k)return RandomizeSelect(L,first,q - 1,mid_num);
    else return RandomizeSelect(L,q + 1,last,mid_num - k);
}


void main()
{
    int L[8] = {3,45,13,27,34,23,56,8};
    int select;

    select = RandomizeSelect(L,0,7,1);
    cout<<select<<endl;
    select = RandomizeSelect(L,0,7,2);
    cout<<select<<endl;
    select = RandomizeSelect(L,0,7,3);
    cout<<select<<endl;
    select = RandomizeSelect(L,0,7,4);
    cout<<select<<endl;

    select = RandomizeSelect(L,0,7,5);
    cout<<select<<endl;
    select = RandomizeSelect(L,0,7,6);
    cout<<select<<endl;
    select = RandomizeSelect(L,0,7,7);
    cout<<select<<endl;
    select = RandomizeSelect(L,0,7,8);
    cout<<select<<endl;
}