学步园

建议先看看前言 ： http://www.cnblogs.com/tanky_woo/archive/2011/04/09/2010263.html

这一节讲的是非线性排序。

一.计数排序(Counting Sort)

基本思想：对每一个输入元素x，确定出小于x的元素个数。

适用范围：适用于输入是由小范围的整数构成的序列。

稳定性：算法是稳定的。

具体实现：

 /*

Author: Tanky Woo

Blog:   www.WuTianQi.com

Description: 计数排序
*/

#include <iostream>
using namespace std;

 
// arr--初始输入数组， res--存放排序结果的数组，hash临时存储区[0...k]
int arr[100], res[100], hash[100];
int len, k = -1;

 
void PrintHash()

{

    cout << "Hash数组: " << endl;

    for(int i=0; i<=k; ++i)

        cout << hash[i] << " ";

    cout << endl;

}

 
void countingSort()

{

    for(int i=0; i<=k; ++i)

        hash[i] = 0;

    // 此过程记录每一个元素的个数
    for(int i=1; i<=len; ++i)

        ++hash[arr[i]];

    PrintHash();

    // 此过程确定小于x的元素的个数
    for(int i=1; i<=k; ++i)

        hash[i] += hash[i-1];

    PrintHash();

    // 思考这里为何从i=len开始？而不从i=1开始？
    for(int i=len; i>0; --i)

    {

        res[hash[arr[i]]] = arr[i];

        --hash[arr[i]];

    }

}
/*

思考这里为何从i=len开始？而不从i=1开始？

保持排序后结果的稳定性！

因为同一个元素，靠后的元素在排序后相对也是从后开始存入结果数组的。
*/

 
int main()

{

    cout << "输入元素个数: ";

    cin >> len;

    cout << "输入" << len << "个元素: " << endl;

    for(int i=1; i<=len; ++i)

    {

        cin >> arr[i];

        if(k < arr[i])

            k = arr[i];

    }

    countingSort();

    cout << "排序后结果为: " << endl;

    for(int i=1; i<=len; ++i)

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

    cout << endl;

}  

输出结果：

 

 二.基数排序(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

欢迎大家互相学习，互相探讨。