算法3.1--简单的选择算法(QSelect)

问题名称：Selection

问题描述：求Ｎ个元素中的第k元，不关心其他元素的有序问题．

比如求k=[N/2]，中值问题．

 

最简单的想法是将整个list排序，然后给出第k个，但是最好的排序也是O(N*lgN)的，而这个问题，有Ｏ(N)阶的解．

实际上，Selection是求快排中划分元位于k的划分．比之于QuickSort,　QSelect只需要对一侧进行递归．当然，最坏的情况下还是O(N^2)，与快排相同．

 

#include
#include
#include
#include

#define MAX_LENGTH 100
#define STACK_INCREASE 20

/*Show usage*/
void usage(char * prog)
{
        printf("%s Usage:\n", prog);
        printf("%s \n", prog);
}

/*Generate and initialize the list*/
int * generate_list(int count)
{
        int i;
        int * list;
        list = (int *)malloc(count*sizeof(int));
        if(list == NULL)
        {
                perror("malloc");
                return NULL;
        }

        /*Initialize the list with integers less than 100*/
        srandom((unsigned int)time(NULL));
        for (i  = 0; i < count ; i ++)
                list[i] = random()%100;

        return list;
}

/*Show the list*/
void show_list(int * list, int length)
{
        int i;
        for(i = 0; i < length; i ++)
                printf("%d      ", list[i]);

        printf("\n");
}

/*partition algorithm in quick sort*/
int partition(int * list, int first, int last)
{
        int left = first;
        int right = last;
        int pivot = list[left];
        while(left < right)
        {
                while((right > left) && (list[right] >= pivot))
                        right --;
                if(left < right)
                {
                        list[left] = list[right];
                        left ++;
                }
                while((left < right) && (list[left] < pivot))
                        left ++;
                if(left < right)
                {
                        list[right] = list[left];
                        right --;
                }
        }
        list[left] = pivot;
        return left;
}

/*Algorithm*/
int qselect(int * list, int first, int last, int k)
{
        int i, temp;
        if(last == first)
        {
                return list[first];
        }
        i = partition(list, first, last);
        if(k == i)
        {
                return list[i];
        }
        if(k < i)
        {
                temp = qselect(list, first, i - 1, k);
        }
        else
        {
                temp = qselect(list, i + 1, last, k);
        }
        return temp;
}

int main(int argc, char * argv[])
{
        int length, k;
        int * list = NULL;

        /*Deal with the arguments*/
        if(argc != 2)
        {
                usage(argv[0]);
                exit(127);
        }

        length = atoi(argv[1]);
        if(!length || length > MAX_LENGTH)
        {
                usage(argv[0]);
                exit(129);
        }

        list = generate_list(length);
        if(list == NULL)
                exit(128);
        else
        {
                int list_k;
                k = random()%(length -1);
                printf("Try to find element %d from the list: (list[0]...list[%d])\n", k, length -1);
                show_list(list, length);
                list_k = qselect(list, 0, length-1, k);
                printf("list[%d] = %d\n", k, list_k);
        }

        free(list);
        return 1;
}