当前位置:编程学习 > 网站相关 >>

《算法导论》学习总结 — 8.第八章(2) 计数排序 && 基数排序 && 桶排序

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

一.计数排序(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;

输出结果:

 

 jishupaixu

 二.基数排序(Radix Sort)

基本思想:按组成关键字的各个位的值来实现排序的。

排序方式:

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

稳定性:算法是稳定的。

推荐:严蔚敏《数据结构》上的基数排序。

先说下什么是基数:计算的基数就是基本的单元数。比如10进制的基数就是10,二进制的基数就2,八进制的基数是8等等。

基数排序说通俗点,就是把带排序的N个数字右对齐排成一列。然后把相同的位数互相比较,来排序。

例图:

jishu

以下是具体实现和分析:

  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  &nb

补充:综合编程 , 其他综合 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,