Tanky Woo的程序人生
追逐C++的強大，追尋算法的內涵

隨筆 - 70 文章 - 160 trackbacks - 0

公告:

本博客采用知識共享署名 2.5 中國大陸許可協議進行許可。本博客版權歸作者所有，歡迎轉載，但未經作者同意不得隨機刪除文章任何內容，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。具體操作方式可參考此處。如您有任何疑問或者授權方面的協商，請給我留言。

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

搜索

積分與排名

積分 - 180077
排名 - 147

閱讀排行榜

建議先看看前言： http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

這一節講的是非線性排序。

一.計數排序(Counting Sort)

基本思想：對每一個輸入元素x，確定出小于x的元素個數。

適用范圍：適用于輸入是由小范圍的整數構成的序列。

穩定性：算法是穩定的。

具體實現：

1 /*
2 Author: Tanky Woo
3 Blog: www.WuTianQi.com
4 Description: 計數排序
5 */
6 #include <iostream>
7 using namespace std;
8
9 // arr--初始輸入數組， res--存放排序結果的數組，hash臨時存儲區[0

k]
10 int arr[100], res[100], hash[100];
11 int len, k = -1;
12
13 void PrintHash()
14 {
15     cout << "Hash數組: " << endl;
16     for(int i=0; i<=k; ++i)
17         cout << hash[i] << " ";
18     cout << endl;
19 }
20
21 void countingSort()
22 {
23     for(int i=0; i<=k; ++i)
24         hash[i] = 0;
25     // 此過程記錄每一個元素的個數
26     for(int i=1; i<=len; ++i)
27         ++hash[arr[i]];
28     PrintHash();
29     // 此過程確定小于x的元素的個數
30     for(int i=1; i<=k; ++i)
31         hash[i] += hash[i-1];
32     PrintHash();
33     // 思考這里為何從i=len開始？而不從i=1開始？
34     for(int i=len; i>0; --i)
35     {
36         res[hash[arr[i]]] = arr[i];
37         --hash[arr[i]];
38     }
39 }
40 /*
41 思考這里為何從i=len開始？而不從i=1開始？
42 保持排序后結果的穩定性！
43 因為同一個元素，靠后的元素在排序后相對也是從后開始存入結果數組的。
44 */
45
46 int main()
47 {
48     cout << "輸入元素個數: ";
49     cin >> len;
50     cout << "輸入" << len << "個元素: " << endl;
51     for(int i=1; i<=len; ++i)
52     {
53         cin >> arr[i];
54         if(k < arr[i])
55             k = arr[i];
56     }
57     countingSort();
58     cout << "排序后結果為: " << endl;
59     for(int i=1; i<=len; ++i)
60         cout << res[i] << " ";
61     cout << endl;
62 }

輸出結果：

二.基數排序(Radix Sort)

基本思想：按組成關鍵字的各個位的值來實現排序的。

排序方式：

排序方式：LSD 由右向左排; MSD 由左向右排

穩定性：算法是穩定的。

推薦：嚴蔚敏《數據結構》上的基數排序。

先說下什么是基數：計算的基數就是基本的單元數。比如10進制的基數就是10，二進制的基數就2，八進制的基數是8等等。

基數排序說通俗點，就是把帶排序的N個數字右對齊排成一列。然后把相同的位數互相比較，來排序。

例圖：

以下是具體實現和分析：

1

/*
2

Author: Tanky Woo
3

Blog: www.WuTianQi.com
4

Description: 基數排序
5

*/
6

#include <iostream>
7

#include <cstring>
8

using namespace std;
9

10

int arr[100], res[100], hash[10];
11

int n;
12

13

int maxbit()
14

{
15

int _max = 0;
16

int temp[100];
17

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

temp[i] = arr[i];
19

20

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

{
22

int tt = 1;
23

while(temp[i]/10 > 0)
24

{
25

tt++;
26

temp[i] /= 10;
27

}
28

if(_max < tt)
29

_max = tt;
30

}
31

cout << "_max : " << _max << endl;
32

return _max;
33

}
34

35

void radixSort()
36

{
37

memset(res, 0, sizeof(res));
38

int nbit = maxbit();
39

int tmp;
40

int radix = 1;
41

// 以下和計數排序一樣
42

for(int i=1; i<=nbit; ++i)
43

{
44

for(int j=0; j<10; ++j)
45

hash[j] = 0;
46

for(int j=0; j<n; ++j)
47

{
48

tmp = (arr[j]/radix)%10;
49

++hash[tmp];
50

}
51

for(int j=1; j<10; ++j)
52

hash[j] += hash[j-1];
53

for(int j=n-1; j>=0; --j)
54

{
55

tmp = (arr[j]/radix)%10;
56

--hash[tmp];
57

res[hash[tmp]] = arr[j];
58

}
59

for(int j=0; j<n; ++j)
60

arr[j] = res[j];
61

radix *= 10;
62

}
63

}
64

65

int main()
66

{
67

freopen("input.txt", "r", stdin);
68

cout << "輸入元素個數: ";
69

cin >> n;
70

cout << "輸入" << n << "個元素: " << endl;
71

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

cin >> arr[i];
73

radixSort();
74

cout << "排序后結果為: " << endl;
75

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

cout << res[i] << " ";
77

cout << endl;
78

}

推薦一個基數排序的動畫演示：http://blogimg.chinaunix.net/blog/upfile/070912120349.swf

桶排序就不寫了，本質就是計數排序和基數排序的結合。
不過我有點不明白，我們一般說的桶排序貌似就是基數排序？

在我獨立博客上的原文：http://www.wutianqi.com/?p=2378

歡迎大家互相學習，互相探討。

posted on 2011-04-24 09:28 Tanky Woo 閱讀(1529) 評論(4) 編輯收藏引用

FeedBack:

# re: 《算法導論》學習總結 — 8.第八章(2) 計數排序 && 基數排序 && 桶排序 2011-04-29 21:43 KingJ

今天剛看了這一章，感覺書上對基數排序的內容寫的有點朦朧，來看lz寫的感覺比較直觀，桶排序看著一堆公式感覺好亂回復更多評論

# re: 《算法導論》學習總結 — 8.第八章(2) 計數排序 && 基數排序 && 桶排序 2011-04-29 21:48 Tanky Woo

@KingJ
呵呵，怎么說呢，書上的分析還是很給力的，我能做的也就是補充一些，然后實現，大家共勉吧。至于那個堆排序，我也不太明白，他的給力之處到底在哪。。。而且在我印象中基數排序又稱堆排序的。回復更多評論

# re: 《算法導論》學習總結 — 8.第八章(2) 計數排序 && 基數排序 && 桶排序 2011-04-29 22:06 KingJ

@Tanky Woo
我感覺書上的分析理解了以后能有種豁然開朗的感覺，呵呵，方便留個qq嗎
？交流交流，呵呵回復更多評論

# re: 《算法導論》學習總結 — 8.第八章(2) 計數排序 && 基數排序 && 桶排序 2011-04-30 11:59 Tanky Woo

@KingJ
給你發私信了~~~ 回復更多評論

刷新評論列表

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



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

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