70 数组的Kmin算法和二叉搜索树的Kmin算法对比

// 70_Kmin_of_Array_and_BST.cpp : Defines the entry point for the console application.
//
/*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/9/18
*/

#include “stdafx.h”
#include “iostream”
#include <ctime>
#include <algorithm>
using namespace std;

void print(int *a, int n)
{
    ; i < n; i++)
    {
        cout << a[i] << “ ”;
    }
    cout << endl;
}

int compare_less (const void *a, const void b)
{
    return ( (int *)a -  (int )b );
}

//========================================================
//   kmin of array
//========================================================
void myswap(int &a, int &b)
{
    int t = a;
    a = b;
    b = t;
}

int partition1(int *a, int left, int right)
{
    // a[left,…p-1]<=a[p]<a[p+1,…right]
    int i = left;
    int j = right;
    int key = a[left];
    while(i < j)
    {
        while(a[i] <= key) i++;
        while(a[j] > key) j–;
        if (i < j)
        {
            myswap(a[i], a[j]);
        }
    }
    // left—j—i—right
    myswap(a[left], a[j]);
    return j;
}

int kmin(int *a, int left, int right, int k)
{
    if(left < = right)
    {
        int p = partition1(a, left, right);
        ;
        if (k == pk)
        {
            return a[p];
        }
        else if (k < pk)
        {
            , k);
        }
        else // k >pk
        {
            , right, k - pk);
        }
    }
}

int Kmin_of_Array(int *a, int n, int k)
{
    )
        ;
     || k > n)
        ;
    , k);
}

void test_base(int *a, int n, int k)
{
    print(a, n);
    qsort(a, n, sizeof(int), compare_less);
    print(a, n);
    cout << k << “ min of array is: ” << Kmin_of_Array(a, n, k) << endl;
    cout << “==============================\n”;
}

void test_default()
{
    srand((unsigned int)time(NULL));
    ;
    int a[n];
    ; i < n; i++)
    {
        a[i] = rand() % ;
    }
    test_base(a, n, );
}

void test_main()
{
    test_default();
}

int _tmain(int argc, _TCHAR argv[])
{
    test_main();
    ;
}
/
37 30 22 10 22 63 6 44 36 41 43 75 54 77 9 99 3 13 28 27
3 6 9 10 13 22 22 27 28 30 36 37 41 43 44 54 63 75 77 99
3 min of array is: 9
==============================
*/