IceSandwich

线性时间排序

常见的线性排序算法

算法
字数统计: 1.4k阅读时长: 6 min
2020/07/14 Share

前言

快速排序的时间复杂度为$O(n*log(n))$ ，但是对于一些简单的排序来说，这个代价未免有点高。过去我们在算法：排序（一）和算法：排序（二）讨论了几个排序算法，都是基于比较的排序。其实还有一些不是基于比较的排序，能够实现复杂度为$O(n)$的排序。

计数排序

既然不是基于比较的排序，那是基于什么呢？答案是：频数表。

举个栗子，我们有数组 2,5,3,0,2,3,0,3 ，对它作频数表，然后对频数表作积分表，称之为分布表(关于积分表，详看 积分表和差分表的使用)

频数表如何得到？横坐标为数组中所有出现过不重复的数字，对每个x值，纵坐标就是x在数组中出现的次数。比如，当x=2时，2在数组中出现了2次，因此纵坐标为2，又如，当x=1时，1在数组中没有出现过，因此纵坐标为0，依此类推。

分布表呢？就是将左边的都加起来。设定频数表为P，则分布表D[n] = D[n-1] + P[n]

分布表表示什么呢？D[3] = 6，表示输出的数组Res中，有Res[6] = 3。也就是说D[n]的值就是表示n放在输出数组中哪个位置。再如，D[4]=7,有Res[7]=4，合并起来就是Res[D[n]]=n，对应下面代码的第54和第56行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <memory.h>
using namespace std;

/*const int n = 8;
int A[n] = {2,5,3,0,2,3,0,3};*/
const int n = 10;
int A[n] = {95, 94, 91, 98, 99, 90, 99, 93, 91, 92};

void findMaxMinIdx(int &min, int &max) {
    min = max = 0;
    for (int i = 1; i < n; ++i) {
        if (A[min] > A[i]) {
            min = i;
        }
        if (A[max] < A[i]) {
            max = i;
        }
    }
}

int *countingDistribution(int &startRange, int &len) {
    //Step 1. 计算分布表横坐标范围[minIdx, maxIdx]
    int minIdx, maxIdx;
    findMaxMinIdx(minIdx, maxIdx);
    len = A[maxIdx] - A[minIdx] + 1;
    startRange = A[minIdx];

    //Step 2. 新建频数表，并初始化为0
    int *distribution = new int[len];
    memset(distribution, 0, len * sizeof(int));

    //Step 3. 进行统计，注意x进行了平移，从startRange开始
    for (int i = 0; i < n; ++i) {
        ++distribution[A[i]-startRange];
    }

    //Step 4. 统计求和，得到分布表
    for (int i = 1; i < len; ++i) {
        distribution[i] += distribution[i-1];
    }
    return distribution;
}

int main() {
    //Step 1. 计算分布表
    int srange, lenx;
    int *distrib = countingDistribution(srange, lenx);

    //Step 2. 从分布表得到排序结果
    int *result = new int[n];
    for (int i = 0; i < n; ++i) {
        //根据分布表得到A[i]应该放在哪个地方
        int &lastPosition = distrib[A[i]-srange]; 
        //注意lastPosition是从1开始（逻辑序列），转成物理序列要减1
        result[lastPosition-1] = A[i]; //放置
        --lastPosition; //放置后地方-1，因为我们是从右边往左放置元素
    }

    //Step 3. 输出结果
    for (int i = 0; i < n; ++i) {
        printf("%d ", result[i]);
    }
    delete[] distrib;
    delete[] result;
    return 0;
}

这个的代码加了一点修改，因为上面描述的方法中，出现一个问题，如果我们要排序的数字范围为[90, 99]，这样我们需要开辟长度为99的数组，但只用了其中的10个元素，非常浪费，因此需要将横坐标向左平移即可。

横坐标都减掉数组中最小的元素，得到的频数表就是从0开始的了。

对计数排序的思考

网上有不少计数排序的算法实现，理解起来挺容易的，但是似乎他们都没有分布表这一个步骤。其实没有分布表，也是可以的。想一想，为什么有分布表也可以？

基数排序

基数排序顾名思义，按照位数排序。通常我们认为，如果对3位数的数组排序，应当先排序百位，再排序十位，之后再排序个位。但是，基数排序恰好反过来，它需要先对个位排序，然后对十位排序，最后对百位排序。排序的时候所用的排序算法可以随便选，只要排序的算法是稳定的就可以了，特别灵活。

下面的代码中，第9行到21行是从算法：排序（一）的插入排序复制过来的，修改了一下比较函数CompareTo，因为我们不是基于数值的比较，而是基于十进制位的比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;

const int n = 7;
int A[n] = {329,457,657,839,436,720,355};
int digit = 1;

//CompareTo、Swap、InsertSort都是插入排序的函数
int CompareTo(int index1, int index2) {
    return (A[index1]%digit/(digit/10))-(A[index2]%digit/(digit/10));
}
void Swap(int index1, int index2) {
    int t = A[index1];
    A[index1] = A[index2];
    A[index2] = t;
}
void InsertSort() {
    for (int i = n-1; i >= 0; --i)
        for (int j = i-1; j < n-1 && CompareTo(j, j+1)>0; ++j)
            Swap(j, j+1);
}

int main() {
    for (int i = 1; i <= 3; ++i) {
        //对每一位进行插入排序
        digit = digit * 10;
        InsertSort();
    }
    for (int k = 0; k < n; ++k) {
        printf("%d ", A[k]);
    }
    return 0;
}

桶排序

没什么特别的，可以设定桶的序号为十进制的第二位（十位）的数字，桶里面放链表，对链表进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int n = 10;
int A[n] = {78,17,39,26,72,94,21,12,23,68};
vector<int> Bucket[10];

int main() {
    for (int i = 0; i < n; ++i) {
        //以第二位为主键放桶
        Bucket[A[i]/10].push_back(A[i]);
    }
    for (int i = 0; i < n; ++i) {
        sort(Bucket[i].begin(), Bucket[i].end()); //对链表排序，任何一种排序方式都可以
        //遍历输出
        for (vector<int>::iterator iter = Bucket[i].begin(); iter != Bucket[i].end(); ++iter) {
            printf("%d ", *iter);
        }
    }
    return 0;
}

原文作者：IceSandwich

原文链接：https://icesandwich.github.io/2020/07/14/%E7%BA%BF%E6%80%A7%E6%97%B6%E9%97%B4%E6%8E%92%E5%BA%8F/

发表日期：July 14th 2020, 12:00:00 am

更新日期：January 12th 2021, 3:40:51 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 前言
  2. 2. 计数排序
    1. 2.1. 对计数排序的思考
  3. 3. 基数排序
  4. 4. 桶排序
Total : 21
2021
2020
2019
c docker 算法 GTK 三维重建 KinectFusion 稠密重建 MSSQL html gtk opencv cuda BundleFusion 油猴脚本 js esp8266 arduino python torch Premiere FFmpeg 渗透
算法原理 docker GTK 三维重建 gtk BundleFusion 算法 脚本 硬件 研究 FFMPEG 渗透