liyuxia713

蹣跚前行者

留言簿(3)

隨筆分類

收藏夾

隨筆檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

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

Algorithms

lzmagic (rss)
正在更新數據結構中的一些經典算法
第四維空間
數據結構算法
極限定律
算法

C++

鷹之夢園
C++ Primer 學習筆記

基本排序方法及分析（八）：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

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

//初始設為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

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

只有注冊用戶登錄后才能發表評論。


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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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