随笔 - 312, 文章 - 14, 评论 - 1393, 引用 - 0
数据加载中……

得到第K个大的数算法研究

本文为原创,如需转载,请注明作者和出处,谢谢!

    第一种算法是最容易想到的,就是利用快速排序的思想,将一个数组分成以某一个数X为轴,左边的所有的数都比X小,而右边的数都比X大。但我快速排序不同的是,在这个算法中只考虑X的一边,而不是两边都考虑。

   如果X的位置是i,那么要得到第k个数,如果k<=i, 那么这个数一定在i的左边,否则在i的右边。

源码如下:

#include <stdio.h>
#include 
<stdlib.h>
int new_random(int min, int max)
{
    
return (min + (int)(((float)rand()/RAND_MAX)*(max - min)));
}
void swap(int *a, int *b)
{
    
int c = *a;
    
*= *b;
    
*= c;
}

int partition(int A[], int p, int r)
{
    
int i = p - 1, j;
    
for(j = p; j < r; j++)
    {
        
if(A[j] <= A[r])
        {
            i
++;
            swap(
&A[i], &A[j]);
        }
    }
    swap(
&A[i + 1], &A[r]);
    
return i + 1;
}

int randomize_partition(int A[], int p, int r)
{
    
int i = new_random(p, r);
    swap(
&A[i], &A[r]);
    
return partition(A, p, r);
}

//第一种算法
int randomized_select(int data[], int p, int r, int k)
{
    
if(k > (r - p + 1)) return 0;
    
if(p == r) return data[p];
    
int i = randomize_partition(data, p, r);
    
//int i = partition(data, p, r); //不好使,死循环, 必须用随机数,在第二步时总是在最大数处划分

    
int count = i - p + 1;
    
if(k <= count)
        
return randomized_select(data, p, i, k);
    
else
        
return randomized_select(data, i + 1, r, k - count);
}


    另外一种对这种算法做了一下改进,即将数组每5个数一组进行排序,然后取得它的中位数,再对这些中位数进行排序。然后先出的轴X最比较好的,因此X的左边和右边的数总是很平均,所以平均查找速度更快。算法如下:

void quicksort(int data[], int b, int e)
{
    
if(b < e)
    {
        
int k = partition(data, b, e);
        quicksort(data, b, k 
- 1);
        quicksort(data, k 
+ 1, e);
    }
}

int partition1(int A[], int p, int r, int x)
{
    
int i = p - 1, j;
    
for(j = p; j <= r; j++)
    {
        
if(A[j] <= x)
        {
            i
++;
            swap(
&A[i], &A[j]);
        }
    }
    A[i 
+ 1= x;
    
return i + 1;
}
//第二种算法
int select_new(int data[], int p, int r, int k)
{
    
if(r - p < 75)
    {
        quicksort(data, p, r);
        
return data[p + k - 1];
    }   
    
int i;
    
for(i = 0; i <= (r - p - 4/ 5; i++)
    {
        quicksort(data, p 
+ 5 * i, p + 5 * i + 4);
        swap(
&data[p + 5 * i + 2], &data[p + i]);
    }
    
int x = select_new(data, p, p + (r - p - 4/ 5, (r - p - 4)/10); // 得到更好的轴X
    i = partition1(data, p, r, x);
    
int count = i - p + 1
    
if(k <= count)
        
return select_new(data, p, i, k);
    
else
        
return select_new(data, i + 1, r, k - count);
}

int main()
{
    
int data[] = {3173481167812-1100};
    printf(
"%d\n", randomized_select(data, 092));
    
int data1[] = {3173481167812-1100};
    printf(
"%d\n", select_new(data1, 092));
   
     
return 0;
}





Android开发完全讲义(第2版)(本书版权已输出到台湾)

http://product.dangdang.com/product.aspx?product_id=22741502



Android高薪之路:Android程序员面试宝典 http://book.360buy.com/10970314.html


新浪微博:http://t.sina.com.cn/androidguy   昵称:李宁_Lining

posted on 2008-05-12 20:55 银河使者 阅读(1910) 评论(0)  编辑  收藏 所属分类: algorithmC/C++ 原创


只有注册用户登录后才能发表评论。


网站导航: