久久综合精品一区,国产一区在线播放,国产亚洲视频在线观看

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

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

/**
2

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

* 對a[0],

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

*/
5

#include <iostream>
7

#include <cstdlib>
8

using namespace std;
10

void print(int* a , int n)
12

{
13

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

cout << a[i];
15

cout << endl;
16

}
17

//對a[0],

,a[n-1]進(jìn)行排序，其中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

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

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

{
27

c[i] = 0;
28

}
29

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

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

{
33

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

}
35

//c[i-1]中存儲值小于等于i的個數(shù)
37

for(int i = 1; i < m; i++)
38

{
39

c[i] = c[i] + c[i-1];
40

}
41

//排序
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

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

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

{
52

a[i] = temp[i];
53

}
54

}
55

int main()
57

{
58

int a[5] = {4,1,3,4,3};
59

print(a,5);
61

Counting_Sort(a,5,4);
63

print(a,5);
65

system("pause");
67

return 0;
68

}
69

posted on 2010-01-18 15:50 幸運(yùn)草閱讀(458) 評論(0) 編輯收藏引用所屬分類: Algorithms

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

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

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

liyuxia713

導(dǎo)航

留言簿(3)

隨筆分類

收藏夾

隨筆檔案

閱讀排行榜

評論排行榜

常用鏈接

統(tǒng)計

Algorithms

C++

最新評論

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