问题名称:Selection
问题描述:求Ｎ个元素中
第k元
不关心其他元素有序问题．比如求k=[N/2]
中值问题．最简单
想法是将整个list排序然后给出第k个但是最好排序也是O(N*lgN)而这个问题有Ｏ(N)阶解．实际上
Selection是求快排中划分元位于k划分．比的于QuickSort, QSelect只需要对
侧进行递归．当然最坏情况下还是O(N^2)和快排相同．#
<stdlib.h>#
<stdio.h>#
<sys/time.h>#
<time.h>#
MAX_LENGTH 100#
STACK_INCREASE 20/*Show usage*/
void usage(char * prog)
{
pr
f(\"%s Usage:\\n\", prog);pr
f(\"%s <the count of numbers to sort (should be less than 100)>\\n\", prog);}
/*Generate and initialize the list*/
* generate_list( count){
i; * list;list = (
*)malloc(count*
());
(list 
NULL){
perror(\"malloc\");
NULL;}
/*Initialize the list with
egers less than 100*/srandom((unsigned
)time(NULL));for (i = 0; i < count ; i
)list[i] = random
%100; list;}
/*Show the list*/
void show_list(
* list, length){
i;for(i = 0; i < length; i
)pr
f(\"%d \", list[i]);pr
f(\"\\n\");}
/*partition algorithm in quick sort*/
partition( * list, first, last){
left = first; right = last; pivot = list[left];while(left < right)
{
while((right > left) && (list[right] >= pivot))
right --;
(left < right){
list[left] = list[right];
left
;}
while((left < right) && (list[left] < pivot))
left
;(left < right){
list[right] = list[left];
right --;
}
}
list[left] = pivot;
left;}
/*Algorithm*/
qselect( * list, first, last, k){
i, temp;
(last first){
list[first];}
i = partition(list, first, last);
(k i){
list[i];}
(k < i){
temp = qselect(list, first, i - 1, k);
}
{
temp = qselect(list, i + 1, last, k);
}
temp;}
( argc, char * argv
){
length, k; * list = NULL;/*Deal with the arguments*/
(argc != 2){
usage(argv[0]);
exit(127);
}
length = atoi(argv[1]);
(!length || length > MAX_LENGTH){
usage(argv[0]);
exit(129);
}
list = generate_list(length);
(list NULL)exit(128);
{
list_k;k = random
%(length -1);pr
f(\"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);
pr
f(\"list[%d] = %d\\n\", k, list_k);}
free(list);
1;}
最新评论