liyuxia713

蹣跚前行者

導(dǎo)航

<

2010年1月

>

日

一

二

三

四

五

六

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

6

留言簿(3)

隨筆分類

收藏夾

隨筆檔案

閱讀排行榜

評論排行榜

常用鏈接

統(tǒng)計

隨筆 - 50
文章 - 0
評論 - 32
引用 - 0

Algorithms

lzmagic (rss)
正在更新數(shù)據(jù)結(jié)構(gòu)中的一些經(jīng)典算法
第四維空間
數(shù)據(jù)結(jié)構(gòu) 算法
極限定律
算法

C++

鷹之夢園
C++ Primer 學(xué)習(xí)筆記

基本排序方法及分析（八）：CoungtingSort 計數(shù)排序

計數(shù)排序?qū)[0],...,a[n-1]進行排序，其中1 <= a[i] <= m
計數(shù)排序不是基于比較的排序方法，從而最壞情形下的運行時間也不受比較的排序方法最快O(nlgn)的限制。
計數(shù)排序的運行時間是O(n+m)

1

/**
2

* Countying sort計數(shù)排序
3

* 對a[0],

,a[n-1]進行排序，其中1 <= a[i] <= m
4

*/
5

6

#include <iostream>
7

#include <cstdlib>
8

9

using namespace std;
10

11

void 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
19

void Counting_Sort(int *a, int n , int m)
20

{
21

int *c = new int[m];
22

int *temp = new int[n];
23

24

//初始設(shè)為0
25

for(int i = 0; i < m ; i++)
26

{
27

c[i] = 0;
28

}
29

30

//c[i-1]中存儲值為i的個數(shù)
31

for(int i = 0; i < n; i++)
32

{
33

c[a[i]-1] += 1;
34

}
35

36

//c[i-1]中存儲值小于等于i的個數(shù)
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

//從臨時數(shù)組轉(zhuǎn)到a
50

for(int i = 0; i < n; i++)
51

{
52

a[i] = temp[i];
53

}
54

}
55

56

int 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 幸運草閱讀(462) 評論(0) 編輯收藏引用所屬分類: Algorithms

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 基本排序方法及分析（九）：Randomized-Quicksort快速排序的隨機化版本 Order Statistics 順序統(tǒng)計（找出第i小元素）基本排序方法及分析（八）：CoungtingSort 計數(shù)排序基本排序方法及分析（七）：HeapSort 堆排序同時求最大最小值基本排序算法及分析（六）：桶式排序基本排序算法及分析（五）：歸并排序基本排序算法及分析（四）：快速排序基本排序算法及分析（三）：shell排序基本排序算法及分析（二）：冒泡排序

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品