快排及找第K小元素

今天写了下看快排，以及快排的应用-找第K小的数字。

发现想法和实现真有距离。

写了好半天，才把快排和找第K小的程序写正确。

 

几个值得注意的问题：

1）一定要对输入参数进行合法性判断。

2）递推调用一定要有终止条件判断。

3）多动手写程序吧。

 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;
void swap( int *data, int first, int second );
void b_search( int *data, int low, int high );
int partition( int *data, int low, int high );
void print_( int *data, int low, int high );

#define LEN 100

int    main()
{
    int data[LEN];
    int n = 0;

    memset( data, 0x00, sizeof(data) );

    scanf( "%d", &n );
    if( n >= LEN )
    {
        printf( "input error\n" );
        return 1;
    }

    for( int i=0; i<n; i++ )
    {
        scanf( "%d", &data[i] );
    }

    b_search( data, 0, n-1 );

    print_( data, 0, n-1 );
}

//快排
void b_search( int *data, int low, int high )
{
    int cur = 0;
    //关键是这块要判断low和high
    if( low < high )
    {
        cur = partition( data, low, high );

///        print_( data, low, high );
        b_search( data, low, cur-1 );

        b_search( data, cur+1, high );
    }
}

int partition( int *data, int low, int high )
{
    int cur = low;
    int key = data[cur];

    if( data == NULL || low == high || low > high )
    {
        return 0;
    }

    while( low < high )
    {
        //一定要注意相等的情况
        while( low < high && data[high] >= key )
        {
            high--;
        }
        if( low < high )
        {
            //printf( "cur=[%d],high=[%d]\n", cur, high );
            swap( data, cur, high );
            cur = high;
        }

        while( low < high && data[low] <= key )
        {
            low++;
        }
        if( low < high )
        {
            //printf( "cur=[%d],high=[%d]\n", cur, high );
            swap( data, cur, low );
            cur = low;
        }
    }

//    data[low] = key;

    return low;
}

void swap( int *data, int first, int second )
{
    int tmp = 0;
    tmp = data[first];

    data[first] = data[second];
    data[second] = tmp;
}

void print_( int *data, int low, int high )
{
    int i = 0;
    for( int i=low; i<=high; i++ )
    {
        printf( "%d ", data[i] );
    }
    printf( "\n" );
}