liyuxia713

蹒跚前行者

常用链接

统计

Algorithms

C++

最新评论

基本排序方法及分析（八）：CoungtingSort 计数排序

计数排序对a[0],...,a[n-1]进行排序，其中1 <= a[i] <= m
计数排序不是基于比较的排序方法，从而最坏情形下的运行时间也不受比较的排序方法最快O(nlgn)的限制。
计数排序的运行时间是O(n+m)
 1/**
 2 * Countying sort计数排序
 3 * 对a[0],,a[n-1]进行排序，其中1 <= a[i] <= m 
 4 */ 
 5
 6#include <iostream> 
 7#include <cstdlib>
 8
 9using namespace std; 
10
11void print(int* a , int n)
12{
13     for(int i = 0; i < n ; i++)
14             cout << a[i];
15     cout << endl;
16}
17
18//对a[0],,a[n-1]进行排序，其中1 <= a[i] <= m 
19void Counting_Sort(int *a, int n , int m)
20{
21     int *c = new int[m];
22     int *temp = new int[n];
23     
24     //初始设为0 
25     for(int i = 0; i < m ; i++)
26     {
27             c[i] = 0;
28     }  
29     
30     //c[i-1]中存储值为i的个数 
31     for(int i = 0; i < n; i++)
32     {
33             c[a[i]-1] += 1;             
34     }
35        
36     //c[i-1]中存储值小于等于i的个数 
37     for(int i = 1; i < m; i++) 
38     {
39             c[i] = c[i] + c[i-1];
40     }   
41     
42     //排序 
43     for(int i = n-1; i >= 0; i--)
44     { 
45             temp[c[a[i]-1]-1] = a[i];
46             c[a[i]-1]--;
47     }    
48      
49     //从临时数组转到a 
50     for(int i = 0; i < n; i++)
51     {
52             a[i] = temp[i];
53     }
54}
55
56int main()
57{
58    int a[5] = {4,1,3,4,3};
59   
60    print(a,5);
61   
62    Counting_Sort(a,5,4);
63   
64    print(a,5); 
65   
66    system("pause");
67    return 0;
68} 
69
70

posted on 2010-01-18 15:50 幸运草 阅读(420) 评论(0)  编辑 收藏 引用 所属分类: Algorithms


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理