`
shappy1978
  • 浏览: 700117 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

三種線性排序算法 計數排序、桶排序與基數排序

 
阅读更多

 

https://www.byvoid.com/zht/blog/sort-radix

[非基於比較的排序]

在計算機科學中,排序是一門基礎的算法技術,許多算法都要以此作爲基礎,不同的排序算法有着不同的時間開銷和空間開銷。排序算法有非常多種,如我們最常用的快速排序和堆排序等算法,這些算法需要對序列中的數據進行比較,因爲被稱爲基於比較的排序

基於比較的排序算法是不能突破O(NlogN)的。簡單證明如下:

N個數有N!個可能的排列情況,也就是說基於比較的排序算法的判定樹有N!個葉子結點,比較次數至少爲log(N!)=O(NlogN)(斯特林公式)。

非基於比較的排序,如計數排序,桶排序,和在此基礎上的基數排序,則可以突破O(NlogN)時間下限。但要注意的是,非基於比較的排序算法的使用都是有條件限制的,例如元素的大小限制,相反,基於比較的排序則沒有這種限制(在一定範圍內)。但並非因爲有條件限制就會使非基於比較的排序算法變得無用,對於特定場合有着特殊的性質數據,非基於比較的排序算法則能夠非常巧妙地解決。

本文着重介紹三種線性的非基於比較的排序算法:計數排序、桶排序與基數排序。

[計數排序]

首先從計數排序(Counting Sort)開始介紹起,假設我們有一個待排序的整數序列A,其中元素的最小值不小於0,最大值不超過K。建立一個長度爲K的線性表C,用來記錄不大於每個值的元素的個數。

算法思路如下:

  1. 掃描序列A,以A中的每個元素的值爲索引,把出現的個數填入C中。此時C[i]可以表示A中值爲i的元素的個數。
  2. 對於C從頭開始累加,使C[i]<-C[i]+C[i-1]。這樣,C[i]就表示A中值不大於i的元素的個數
  3. 按照統計出的值,輸出結果。

由線性表C我們可以很方便地求出排序後的數據,定義B爲目標的序列,Order[i]爲排名第i的元素在A中的位置,則可以用以下方法統計。

/*
 * Problem: Counting Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:27
 * State: Solved
 * Memo: 計數排序
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
void CountingSort(int *A,int *B,int *Order,int N,int K)
{
    int *C=new int[K+1];
    int i;
    memset(C,0,sizeof(int)*(K+1));
    for (i=1;i<=N;i++) //把A中的每個元素分配
        C[A[i]]++;
    for (i=2;i<=K;i++) //統計不大於i的元素的個數
        C[i]+=C[i-1];
    for (i=N;i>=1;i--)
    {
        B[C[A[i]]]=A[i]; //按照統計的位置,將值輸出到B中,將順序輸出到Order中
        Order[C[A[i]]]=i;
        C[A[i]]--;
    }
}
int main()
{
    int *A,*B,*Order,N=15,K=10,i;
    A=new int[N+1];
    B=new int[N+1];
    Order=new int[N+1];
    for (i=1;i<=N;i++)
        A[i]=rand()%K+1; //生成1..K的隨機數
    printf("Before CS:\n");
    for (i=1;i<=N;i++)
        printf("%d ",A[i]);
    CountingSort(A,B,Order,N,K);
    printf("\nAfter CS:\n");
    for (i=1;i<=N;i++)
        printf("%d ",B[i]);
    printf("\nOrder:\n");
    for (i=1;i<=N;i++)
        printf("%d ",Order[i]);
    return 0;
}

程序運行效果如下:

Before CS:
2 8 5 1 10 5 9 9 3 5 6 6 2 8 2
After CS:
1 2 2 2 3 5 5 5 6 6 8 8 9 9 10
Order:
4 1 13 15 9 3 6 10 11 12 2 14 7 8 5

顯然地,計數排序的時間複雜度爲O(N+K),空間複雜度爲O(N+K)。當K不是很大時,這是一個很有效的線性排序算法。更重要的是,它是一種穩定排序算法,即排序後的相同值的元素原有的相對位置不會發生改變(表現在Order上),這是計數排序很重要的一個性質,就是根據這個性質,我們才能把它應用到基數排序。

[桶排序]

可能你會發現,計數排序似乎饒了點彎子,比如當我們剛剛統計出C,C[i]可以表示A中值爲i的元素的個數,此時我們直接順序地掃描C,就可以求出排序後的結果。的確是這樣,不過這種方法不再是計數排序,而是桶排序(Bucket Sort),確切地說,是桶排序的一種特殊情況。

用這種方法,可以很容易寫出程序,比計數排序還簡單,只是不能求出穩定的Order。

/*
 * Problem: Bucket Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:32
 * State: Solved
 * Memo: 桶排序特殊實現
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
void BucketSort(int *A,int *B,int N,int K)
{
    int *C=new int[K+1];
    int i,j,k;
    memset(C,0,sizeof(int)*(K+1));
    for (i=1;i<=N;i++) //把A中的每個元素按照值放入桶中
        C[A[i]]++;
    for (i=j=1;i<=K;i++,j=k) //統計每個桶元素的個數,並輸出到B
        for (k=j;k<j+C[i];k++)
            B[k]=i;
}
int main()
{
    int *A,*B,N=1000,K=1000,i;
    A=new int[N+1];
    B=new int[N+1];
    for (i=1;i<=N;i++)
        A[i]=rand()%K+1; //生成1..K的隨機數
    BucketSort(A,B,N,K);
    for (i=1;i<=N;i++)
        printf("%d ",B[i]);
    return 0;
}

這種特殊實現的方式時間複雜度爲O(N+K),空間複雜度也爲O(N+K),同樣要求每個元素都要在K的範圍內。更一般的,如果我們的K很大,無法直接開出O(K)的空間該如何呢?

首先定義桶,桶爲一個數據容器,每個桶存儲一個區間內的數。依然有一個待排序的整數序列A,元素的最小值不小於0,最大值不超過K。假設我們有M個桶,第i個桶Bucket[i]存儲iK/M至(i+1)K/M之間的數,有如下桶排序的一般方法:

  1. 掃描序列A,根據每個元素的值所屬的區間,放入指定的桶中(順序放置)。
  2. 對每個桶中的元素進行排序,什麼排序算法都可以,例如快速排序。
  3. 依次收集每個桶中的元素,順序放置到輸出序列中。

對該算法簡單分析,如果數據是期望平均分佈的,則每個桶中的元素平均個數爲N/M。如果對每個桶中的元素排序使用的算法是快速排序,每次排序的時間複雜度爲O(N/Mlog(N/M))。則總的時間複雜度爲O(N)+O(M)O(N/Mlog(N/M)) = O(N+ Nlog(N/M)) =O(N + NlogN - NlogM)當M接近於N是,桶排序的時間複雜度就可以近似認爲是O(N)的。就是桶越多,時間效率就越高,而桶越多,空間卻就越大,由此可見時間和空間是一個矛盾的兩個方面。

桶中元素的順序放入和順序取出是有必要的,因爲這樣可以確定桶排序是一種穩定排序算法,配合基數排序是很好用的。

/*
 * Problem: Bucket Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:50
 * State: Solved
 * Memo: 桶排序一般實現
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
struct linklist
{
    linklist *next;
    int value;
    linklist(int v,linklist *n):value(v),next(n){}
    ~linklist() {if (next) delete next;}
};
inline int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
/*
爲了方便,我把A中元素加入桶中時是倒序放入的,而收集取出時也是倒序放入序列的,所以不違背穩定排序。
*/
void BucketSort(int *A,int *B,int N,int K)
{
    linklist *Bucket[101],*p;//建立桶
    int i,j,k,M;
    M=K/100;
    memset(Bucket,0,sizeof(Bucket));
    for (i=1;i<=N;i++)
    {
        k=A[i]/M; //把A中的每個元素按照的範圍值放入對應桶中
        Bucket[k]=new linklist(A[i],Bucket[k]);
    }
    for (k=j=0;k<=100;k++)
    {
        i=j;
        for (p=Bucket[k];p;p=p->next)
            B[++j]=p->value; //把桶中每個元素取出,排序並加入B
        delete Bucket[k];
        qsort(B+i+1,j-i,sizeof(B[0]),cmp);
    }
}
int main()
{
    int *A,*B,N=100,K=10000,i;
    A=new int[N+1];
    B=new int[N+1];
    for (i=1;i<=N;i++)
        A[i]=rand()%K+1; //生成1..K的隨機數
    BucketSort(A,B,N,K);
    for (i=1;i<=N;i++)
        printf("%d ",B[i]);
    return 0;
}

[基數排序]

下面說到我們的重頭戲,基數排序(Radix Sort)。上述的基數排序和桶排序都只是在研究一個關鍵字的排序,現在我們來討論有多個關鍵字的排序問題。

假設我們有一些二元組(a,b),要對它們進行以a爲首要關鍵字,b的次要關鍵字的排序。我們可以先把它們先按照首要關鍵字排序,分成首要關鍵字相同的若干堆。然後,在按照次要關鍵值分別對每一堆進行單獨排序。最後再把這些堆串連到一起,使首要關鍵字較小的一堆排在上面。按這種方式的基數排序稱爲MSD(Most Significant Dight)排序。

第二種方式是從最低有效關鍵字開始排序,稱爲LSD(Least Significant Dight)排序。首先對所有的數據按照次要關鍵字排序,然後對所有的數據按照首要關鍵字排序。要注意的是,使用的排序算法必須是穩定的,否則就會取消前一次排序的結果。由於不需要分堆對每堆單獨排序,LSD方法往往比MSD簡單而開銷小。下文介紹的方法全部是基於LSD的。

通常,基數排序要用到計數排序或者桶排序。使用計數排序時,需要的是Order數組。使用桶排序時,可以用鏈表的方法直接求出排序後的順序。下面是一段用桶排序對二元組基數排序的程序:

/*
 * Problem: Radix Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:50
 * State: Solved
 * Memo: 基數排序 結構數組
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
struct data
{
    int key[2];
};
struct linklist
{
    linklist *next;
    data value;
    linklist(data v,linklist *n):value(v),next(n){}
    ~linklist() {if (next) delete next;}
};
void BucketSort(data *A,int N,int K,int y)
{
    linklist *Bucket[101],*p;//建立桶
    int i,j,k,M;
    M=K/100+1;
    memset(Bucket,0,sizeof(Bucket));
    for (i=1;i<=N;i++)
    {
        k=A[i].key[y]/M; //把A中的每個元素按照的範圍值放入對應桶中
        Bucket[k]=new linklist(A[i],Bucket[k]);
    }
    for (k=j=0;k<=100;k++)
    {
        for (p=Bucket[k];p;p=p->next) j++;
        for (p=Bucket[k],i=1;p;p=p->next,i++)
            A[j-i+1]=p->value; //把桶中每個元素取出
        delete Bucket[k];
    }
}
void RadixSort(data *A,int N,int K)
{
    for (int j=1;j>=0;j--) //從低優先到高優先 LSD
        BucketSort(A,N,K,j);
}
int main()
{
    int N=100,K=1000,i;
    data *A=new data[N+1];
    for (i=1;i<=N;i++)
    {
        A[i].key[0]=rand()%K+1;
        A[i].key[1]=rand()%K+1;
    }
    RadixSort(A,N,K);
    for (i=1;i<=N;i++)
        printf("(%d,%d) ",A[i].key[0],A[i].key[1]);
    printf("\n");
    return 0;
}

基數排序是一種用在老式穿卡機上的算法。一張卡片有80列,每列可在12個位置中的任一處穿孔。排序器可被機械地"程序化"以檢查每一迭卡片中的某一列,再根據穿孔的位置將它們分放12個盒子裏。這樣,操作員就可逐個地把它們收集起來。其中第一個位置穿孔的放在最上面,第二個位置穿孔的其次,等等。

對於一個位數有限的十進制數,我們可以把它看作一個多元組,從高位到低位關鍵字重要程度依次遞減。可以使用基數排序對一些位數有限的十進制數排序

[三種線性排序算法的比較]

從整體上來說,計數排序,桶排序都是非基於比較的排序算法,而其時間複雜度依賴於數據的範圍,桶排序還依賴於空間的開銷和數據的分佈。而基數排序是一種對多元組排序的有效方法,具體實現要用到計數排序或桶排序。

相對於快速排序、堆排序等基於比較的排序算法,計數排序、桶排序和基數排序限制較多,不如快速排序、堆排序等算法靈活性好。但反過來講,這三種線性排序算法之所以能夠達到線性時間,是因爲充分利用了待排序數據的特性,如果生硬得使用快速排序、堆排序等算法,就相當於浪費了這些特性,因而達不到更高的效率。

在實際應用中,基數排序可以用於後綴數組的倍增算法,使時間複雜度從O(NlogNlogN)降到O(N*logN)。線性排序算法使用最重要的是,充分利用數據特殊的性質,以達到最佳效果

分享到:
评论

相关推荐

    三种线性排序算法Java实现

    本资源提供的Java实现包括了三种线性排序算法:桶排序(Bucket Sort)、基数排序(Radix Sort)和计数排序(Counting Sort)。这三种算法在特定条件下可以达到线性的平均或最好时间复杂度,效率相对较高。 1. **桶...

    排序算法: 冒泡排序,桶排序,计数排序,堆排序,插入排序,合并排序,快速排序,基数排序,选择排序,希尔排序 Python实现

    本文将详细介绍九种常见的排序算法,包括冒泡排序、桶排序、计数排序、堆排序、插入排序、合并排序、快速排序、基数排序和选择排序,并特别关注Python语言的实现。 1. **冒泡排序**:这是一种简单的排序算法,通过...

    线性时间排序算法

    **基数排序**是一种非比较型整数排序算法,其原理是通过按低位到高位的顺序依次进行计数排序来实现。该算法特别适合于处理大范围的整数,尤其是当整数的位数固定时效果更佳。 1. **位数处理**:基数排序将整数视为...

    基数排序算法 java实现

    基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法对于大数据量的排序尤其有效,因为其时间复杂度为线性,即O(n*k),其中n是待排序的元素数量,k是每...

    基数排序算法.zip

    基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法是通过分配、收集和再分配的步骤来实现的,它不依赖于元素之间的比较,而是依赖于数字的位数。这种...

    桶排序,基数排序

    算法导论之基数排序,桶排序。基数排序是利用在各个位上进行计数排序,是一种线性排序

    归并排序,基数排序算法比较

    归并排序和基数排序是两种不同的排序算法,它们在实现方式和效率特点上存在显著差异。 **归并排序**是一种基于分治策略的排序算法。它的基本思想是将待排序的序列分成两个长度相等(或近似相等)的部分,分别对这两...

    十种排序算法介绍十种排序算法介绍

    - **原理**: 桶排序是排序算法中的一种,其基本思想是将数组分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序),然后再把桶里的数据汇集起来组成排序后的...

    算法与数据结构的排序算法

    7. 计数排序、桶排序和基数排序:这些是线性时间复杂度的非比较排序算法,适用于特定类型的数据,如整数排序。 三、排序算法的时间复杂度 时间复杂度是衡量排序算法效率的重要指标,常见排序算法的时间复杂度如下:...

    C经典算法之基数排序法

    - **非比较性排序**:这一类排序算法不需要通过元素之间的比较来决定它们的顺序,而是利用数据本身的特性进行排序,例如计数排序、桶排序等。 此外,根据排序后相同元素的相对位置是否保持不变,还可以将排序算法...

    十大排序算法.pdf

    桶排序不是基于比较的排序算法,其时间复杂度为O(n+k),k是桶的数量,可以认为是线性的,但不是稳定排序算法。 9. 基数排序 基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每...

    各种常用排序算法的C语言实现

    当输入数据均匀分布时,桶排序可以达到线性时间复杂度O(n + k)。 10. 基数排序(Radix Sort) 基数排序根据数字的每一位进行排序,从低位到高位逐次处理。C语言实现中,需要处理每一位的排序,例如使用计数排序或桶...

    线性排序:如何根据年龄给100万用户数据排序?.pdf

    本文将探讨线性排序算法,包括桶排序、计数排序和基数排序,并通过一个具体的案例——根据年龄对100万用户数据进行排序,来深入理解这些算法的工作原理及其适用场景。 #### 二、线性排序算法介绍 线性排序算法是一...

    12种排序算法详解(寒小阳博客转出PDF版)

    插入排序(Insertion Sort)是最基础和简单的排序算法之一,它基于一种简单直观的排序思路:将数组分为已排序和未排序两个部分,每次从未排序部分取出一个元素,与已排序部分的元素逐一比较,找到合适的位置进行插入...

    各种排序算法大全

    基数排序是一种非比较型整数排序算法,根据数字位数从低位到高位依次进行排序。它适用于大量整数的排序,尤其在位数相同的场景下表现出色。 以上就是压缩包中包含的各种排序算法,它们各有优缺点,适用于不同的场景...

    内部排序算法的性能分析

    8. **计数排序**、**桶排序**和**基数排序**:这些属于非比较型排序,不依赖于关键字的比较,而是基于特定的属性(如数值范围或位数)。它们在某些特定情况下可以实现线性时间复杂度O(n)。 通过对这些算法进行实际...

    排序算法总结.doc

    8. 计数排序、基数排序和桶排序: 这些是线性时间复杂度的排序算法,适用于特定类型的数据。计数排序适用于非负整数,基数排序用于数字的每一位进行排序,桶排序则将数据分配到多个桶中分别排序,然后再合并。它们...

    多种排序算法的比较

    7. **计数排序、桶排序和基数排序**:这些是线性时间复杂度的非比较型排序算法,适用于特定类型的数据。例如,计数排序适用于非负整数,桶排序则适用于分布均匀的数据,基数排序适用于可以按位表示的数字。 在实际...

Global site tag (gtag.js) - Google Analytics