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

這一節(jié)講的是非線性排序。

一.計(jì)數(shù)排序(Counting Sort)

基本思想：對(duì)每一個(gè)輸入元素x，確定出小于x的元素個(gè)數(shù)。

適用范圍：適用于輸入是由小范圍的整數(shù)構(gòu)成的序列。

穩(wěn)定性：算法是穩(wěn)定的。

具體實(shí)現(xiàn)：

 1 /*
 2 Author: Tanky Woo
 3 Blog:   www.WuTianQi.com
 4 Description: 計(jì)數(shù)排序
 5 */
 6 #include <iostream>
 7 using namespace std;
 8  
 9 // arr--初始輸入數(shù)組， res--存放排序結(jié)果的數(shù)組，hash臨時(shí)存儲(chǔ)區(qū)[0k]
10 int arr[100], res[100], hash[100];
11 int len, k = -1;
12  
13 void PrintHash()
14 {
15     cout << "Hash數(shù)組: " << 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     // 此過程記錄每一個(gè)元素的個(gè)數(shù)
26     for(int i=1; i<=len; ++i)
27         ++hash[arr[i]];
28     PrintHash();
29     // 此過程確定小于x的元素的個(gè)數(shù)
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 保持排序后結(jié)果的穩(wěn)定性！
43 因?yàn)橥粋€(gè)元素，靠后的元素在排序后相對(duì)也是從后開始存入結(jié)果數(shù)組的。
44 */
45  
46 int main()
47 {
48     cout << "輸入元素個(gè)數(shù): ";
49     cin >> len;
50     cout << "輸入" << len << "個(gè)元素: " << 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 << "排序后結(jié)果為: " << endl;
59     for(int i=1; i<=len; ++i)
60         cout << res[i] << " ";
61     cout << endl;
62 }

輸出結(jié)果：

二.基數(shù)排序(Radix Sort)

基本思想：按組成關(guān)鍵字的各個(gè)位的值來實(shí)現(xiàn)排序的。

排序方式：

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

穩(wěn)定性：算法是穩(wěn)定的。

推薦：嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)》上的基數(shù)排序。

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

基數(shù)排序說通俗點(diǎn)，就是把帶排序的N個(gè)數(shù)字右對(duì)齊排成一列。然后把相同的位數(shù)互相比較，來排序。

例圖：

以下是具體實(shí)現(xiàn)和分析：

 1/**//*
 2Author: Tanky Woo
 3Blog:   www.WuTianQi.com
 4Description: 基數(shù)排序
 5*/
 6#include <iostream>
 7#include <cstring>
 8using namespace std;
 9 
10int arr[100], res[100], hash[10];
11int n;
12 
13int 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 
35void radixSort()
36{
37    memset(res, 0, sizeof(res));
38    int nbit = maxbit();
39    int tmp;
40    int radix = 1;
41    // 以下和計(jì)數(shù)排序一樣
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 
65int main()
66{
67    freopen("input.txt", "r", stdin);
68    cout << "輸入元素個(gè)數(shù): ";
69    cin >> n;
70    cout << "輸入" << n << "個(gè)元素: " << endl;
71    for(int i=0; i<n; ++i)
72        cin >> arr[i];
73    radixSort();
74    cout << "排序后結(jié)果為: " << endl;
75    for(int i=0; i<n; ++i)
76        cout << res[i] << " ";
77    cout << endl;
78}

推薦一個(gè)基數(shù)排序的動(dòng)畫演示：http://blogimg.chinaunix.net/blog/upfile/070912120349.swf

桶排序就不寫了，本質(zhì)就是計(jì)數(shù)排序和基數(shù)排序的結(jié)合。
不過我有點(diǎn)不明白，我們一般說的桶排序貌似就是基數(shù)排序？

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

歡迎大家互相學(xué)習(xí)，互相探討。