liyuxia713

蹒跚前行者

常用链接

统计

Algorithms

C++

最新评论

Order Statistics 顺序统计(找出第i小元素)

/*
 * Order Statistics 顺序统计
 * Select(int* a, int n, int ith): 从给定的n个元素中找出第i个小的元素
 * 思想:QuickSort的Partition方法进行分割
 * 如果 i = rank(pivot), 则返回a[k]
 * 如果 i < rank(pivot), 则从前半部分中找第i个小的元素
 * 如果 i > rank(pivot), 则从后半部分中找第i-rank(pivot)个小的元素 
 * 最坏运行时间O(n^2)
 * 平均运行时间O(nlgn)
 */
 1#include <iostream> 
 2#include <cstdlib>
 3
 4using namespace std; 
 5
 6//交换两个元素值 
 7void swap(int& a , int& b)
 8{
 9     int temp = a;
10     a = b;
11     b = temp;
12}

13
14//输出数组 
15void print(int* a , int n)
16{
17     for(int i = 0; i < n ; i++)
18             cout << a[i] << ",";
19     cout << endl;
20}

21
22//分割 
23int Partition(int* a, int p, int q)
24{
25    int pivot = a[p];
26    int i = p;
27    
28    for(int j = p+1; j <= q; j++)
29    {
30            if(a[j] <= pivot)
31            {
32                    i = i + 1;
33                    swap(a[i],a[j]);
34            }

35    }

36    swap(a[i],a[p]);
37    return i;
38}

39
40//重复迭代函数 
41int SelectStep(int *a, int p, int q, int i) 
42{
43    if( p==q ) return a[p];
44    
45    else
46    {
47        int k = Partition(a,p,q);           
48     
49        //i-1而不是i是因为下标是从0开始  
50        //k-p而不是k,这点要特别注意!! 
51        if( i-1 == k-p)
52              return a[i-1];
53        else if( i-1 < k-p)
54              return SelectStep(a,p,k-1,i);
55        else 
56              return SelectStep(a,k+1,q,i-k-1);
57     }

58}

59
60//最终调用函数 
61int Select(int* a, int size, int ith)
62{
63    return SelectStep(a,0,size-1,ith);
64}

65         
66int main()
67{
68    const int N = 8;
69    
70    int a[N] = {6,10,13,5,8,3,2,11};
71    
72    print(a,N);
73   
74    cout << Select(a,N,7<< endl;
75   
76    system("pause");
77    return 0;
78}
 

posted on 2010-01-21 16:29 幸运草 阅读(656) 评论(0)  编辑 收藏 引用 所属分类: Algorithms


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理