第三章续：O(n)复杂度算法

#include <iostream>
#include <algorithm>
#include <numeric>
#include <string>
#include <array>
#include <vector>
#include <functional>
#include <hash_set>
#include <ctime>
using namespace std;

inline int my_rand(int low, int high)    
{    
	srand((unsigned)time(NULL));
    int size = high - low + 1;    
    return  low + rand() % size;    
}    
    
int partition(int array[], int left, int right)    
{    
    int pivot = array[right];    
    int pos = left-1;    
    for(int index = left; index < right; index++)    
    {    
        if(array[index] <= pivot)    
            swap(array[++pos], array[index]);    
    }    
    swap(array[++pos], array[right]);    
    return pos;//返回pivot所在位置    
}    
    
//最坏情况下是线性时间O（N）
bool median_select(int array[], int left, int right, int k)    
{    
    //第k小元素，实际上应该在数组中下标为k-1    
    if (k-1 > right || k-1 < left)       
        return false;    
    
    //真正的三数中值作为枢纽元方法，关键代码就是下述六行    
    int midIndex=(left+right)/2;    
    if(array[left]<array[midIndex])    
        swap(array[left],array[midIndex]);    
    if(array[right]<array[midIndex])    
        swap(array[right],array[midIndex]);    
    if(array[right]<array[left])    
        swap(array[right],array[left]);    
    swap(array[left], array[right]);    
        
    int pos = partition(array, left, right);    
        
    if (pos == k-1)    
        return true;    
    else if (pos > k-1)    
        return median_select(array, left, pos-1, k);    
    else return median_select(array, pos+1, right, k);    
}    
    
//总的时间复杂度为线性期望时间：O（n+k）=O（n）（当k比较小时）
bool rand_select(int array[], int left, int right, int k)    
{    
    //第k小元素，实际上应该在数组中下标为k-1    
    if (k-1 > right || k-1 < left)       
        return false;    
    
    //随机从数组中选取枢纽元元素    
    int Index = my_rand(left, right);    
    swap(array[Index], array[right]);    
        
    int pos = partition(array, left, right);    
    
    if (pos == k-1)    
        return true;    
    else if (pos > k-1)    
        return rand_select(array, left, pos-1, k);    
    else return rand_select(array, pos+1, right, k);    
}    
    
//平均为O(N)
bool kth_select(int array[], int left, int right, int k)    
{    
    //直接取最原始的划分操作    
    if (k-1 > right || k-1 < left)       
        return false;    
    
    int pos = partition(array, left, right);    
    if(pos == k-1)    
        return true;    
    else if(pos > k-1)    
        return kth_select(array, left, pos-1, k);    
    else return kth_select(array, pos+1, right, k);    
}    
    
int main()    
{    
    int array1[] = {7, 8, 9, 54, 6, 4, 11, 1, 2, 33};     
    int array2[] = {7, 8, 9, 54, 6, 4, 11, 1, 2, 33};     
    int array3[] = {7, 8, 9, 54, 6, 4, 11, 1, 2, 33};     
        
    int numOfArray = sizeof(array1) / sizeof(int);    
    for(int i=0; i<numOfArray; i++)    
        printf("%d\t",array1[i]);    
        
    int K = 9,i;    
    bool flag1 = median_select(array1, 0, numOfArray-1, K);    
    bool flag2 = rand_select(array2, 0, numOfArray-1, K);    
    bool flag3 = kth_select(array3, 0, numOfArray-1, K);    
    
    for(i=0; i<K; i++)    
        printf("%d\t",array1[i]);   
    printf("\n");    
        
    for(i=0; i<K; i++)    
        printf("%d\t",array2[i]);    
    printf("\n");    

    for(i=0; i<K; i++)    
        printf("%d\t",array3[i]);    
    printf("\n");    
        
    return 0;    
}   

原文：http://blog.csdn.net/starcuan/article/details/19032981