基数排序与桶排序,计数排序【详解】-阿里云开发者社区

开发者社区> 人工智能> 正文

基数排序与桶排序,计数排序【详解】

简介: 桶排序简单入门篇^-^ 在我们生活的这个世界中到处都是被排序过的东东。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序……总之很多东东都需要排序,可以说排序是无处不在。

桶排序简单入门篇^-^

在我们生活的这个世界中到处都是被排序过的东东。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序……总之很多东东都需要排序,可以说排序是无处不在。现在我们举个具体的例子来介绍一下排序算法。

首先出场的是我们的主人公小哼,上面这个可爱的娃就是啦。期末考试完了老师要将同学们的分数按照从高到低排序。小哼的班上只有5个同学,这5个同学分别考了5分、3分、5分、2分和8分,哎,考得真是惨不忍睹(满分是10分)。接下来将分数进行从大到小排序,排序后是8 5 5 3 2。你有没有什么好方法编写一段程序,让计算机随机读入5个数然后将这5个数从大到小输出?请先想一想,至少想15分钟再往下看吧(*^__^*)。

我们这里只需借助一个一维数组就可以解决这个问题。请确定你真的仔细想过再往下看哦。

首先我们需要申请一个大小为11的数组int a[11]。OK,现在你已经有了11个变量,编号从a[0]~a[10]。刚开始的时候,我们将a[0]~a[10]都初始化为0,表示这些分数还都没有人得过。例如a[0]等于0就表示目前还没有人得过0分,同理a[1]等于0就表示目前还没有人得过1分……a[10]等于0就表示目前还没有人得过10分。

下面开始处理每一个人的分数,第一个人的分数是5分,我们就将相对应的a[5]的值在原来的基础增加1,即将a[5]的值从0改为1,表示5分出现过了一次。

第二个人的分数是3分,我们就把相对应的a[3]的值在原来的基础上增加1,即将a[3]的值从0改为1,表示3分出现过了一次。

注意啦!第三个人的分数也是5分,所以a[5]的值需要在此基础上再增加1,即将a[5]的值从1改为2,表示5分出现过了两次。

按照刚才的方法处理第四个和第五个人的分数。最终结果就是下面这个图啦。
 

你发现没有,a[0]~a[10]中的数值其实就是0分到10分每个分数出现的次数。接下来,我们只需要将出现过的分数打印出来就可以了,出现几次就打印几次,具体如下。

a[0]为0,表示“0”没有出现过,不打印。

a[1]为0,表示“1”没有出现过,不打印。

a[2]为1,表示“2”出现过1次,打印2。

a[3]为1,表示“3”出现过1次,打印3。

a[4]为0,表示“4”没有出现过,不打印。

a[5]为2,表示“5”出现过2次,打印5 5。

a[6]为0,表示“6”没有出现过,不打印。

a[7]为0,表示“7”没有出现过,不打印。

a[8]为1,表示“8”出现过1次,打印8。

a[9]为0,表示“9”没有出现过,不打印。

a[10]为0,表示“10”没有出现过,不打印。

最终屏幕输出“2 3 5 5 8”,完整的代码如下。

 1     #include <stdio.h> 
 2     int main()  
 3     {  
 4         int a[11],i,j,t;  
 5         for(i=0;i<=10;i++)  
 6             a[i]=0;  //初始化为0  
 7           
 8         for(i=1;i<=5;i++)  //循环读入5个数  
 9         {  
10             scanf("%d",&t);  //把每一个数读到变量t中  
11             a[t]++;  //进行计数  
12         }  
13      
14         for(i=0;i<=10;i++)  //依次判断a[0]~a[10]  
15             for(j=1;j<=a[i];j++)  //出现了几次就打印几次  
16                 printf("%d ",i);  
17      
18         getchar();getchar();   
19         //这里的getchar();用来暂停程序,以便查看程序输出的内容  
20         //也可以用system("pause");等来代替  
21         return 0;  
22     } 

输入数据为:

5 3 5 2 8 

仔细观察的同学会发现,刚才实现的是从小到大排序。但是我们要求是从大到小排序,这该怎么办呢?还是先自己想一想再往下看哦。

其实很简单。只需要将for(i=0;i<=10;i++)改为for(i=10;i>=0;i--)就OK啦,快去试一试吧。

这种排序方法我们暂且叫它“桶排序”。因为其实真正的桶排序要比这个复杂一些,以后再详细讨论,目前此算法已经能够满足我们的需求了。

这个算法就好比有11个桶,编号从0~10。每出现一个数,就在对应编号的桶中放一个小旗子,最后只要数数每个桶中有几个小旗子就OK了。例如2号桶中有1个小旗子,表示2出现了一次;3号桶中有1个小旗子,表示3出现了一次;5号桶中有2个小旗子,表示5出现了两次;8号桶中有1个小旗子,表示8出现了一次。

现在你可以尝试一下输入n个0~1000之间的整数,将它们从大到小排序。提醒一下,如果需要对数据范围在0~1000的整数进行排序,我们需要1001个桶,来表示0~1000之间每一个数出现的次数,这一点一定要注意。另外,此处的每一个桶的作用其实就是“标记”每个数出现的次数,因此我喜欢将之前的数组a换个更贴切的名字book(book这个单词有记录、标记的意思),代码实现如下。

 1     #include <stdio.h> 
 2      
 3     int main()  
 4     {  
 5         int book[1001],i,j,t,n;  
 6         for(i=0;i<=1000;i++)  
 7             book[i]=0;   
 8         scanf("%d",&n);//输入一个数n,表示接下来有n个数  
 9         for(i=1;i<=n;i++)//循环读入n个数,并进行桶排序  
10         {  
11             scanf("%d",&t);  //把每一个数读到变量t中  
12             book[t]++;  //进行计数,对编号为t的桶放一个小旗子  
13         }  
14         for(i=1000;i>=0;i--)  //依次判断编号1000~0的桶  
15             for(j=1;j<=book[i];j++)  //出现了几次就将桶的编号打印几次  
16                  printf("%d ",i);  
17      
18         getchar();getchar();  
19         return 0;  
20     } 

可以输入以下数据进行验证。

10  

8 100 50 22 15 6 1 1000 999 0 

运行结果是:

1000 999 100 50 22 15 8 6 1 0 

最后来说下时间复杂度的问题。代码中第6行的循环一共循环了m次(m为桶的个数),第9行的代码循环了n次(n为待排序数的个数),第14行和第15行一共循环了m+n次。所以整个排序算法一共执行了m+n+m+n次。我们用大写字母O来表示时间复杂度,因此该算法的时间复杂度是O(m+n+m+n)即O(2*(m+n))。我们在说时间复杂度的时候可以忽略较小的常数,最终桶排序的时间复杂度为O(m+n)。还有一点,在表示时间复杂度的时候,n和m通常用大写字母即O(M+N)。

这是一个非常快的排序算法。桶排序从1956年就开始被使用,该算法的基本思想是由E.J. Issac和R.C. Singleton提出来的。之前我说过,其实这并不是真正的桶排序算法,真正的桶排序算法要比这个更加复杂!

下面具体来说说基数排序和桶排序吧!

基数排序

基本思想

不进行关键字的比较,而是利用”分配”和”收集”。

PS:以十进制为例,基数指的是数的位,如个位,十位百位等。而以十六进制为例,0xB2,就有两个radices(radix的复数)。

Least significant digit(LSD)

短的关键字被认为是小的,排在前面,然后相同长度的关键字再按照词典顺序或者数字大小等进行排序。比如1,2,3,4,5,6,7,8,9,10,11或者”b, c, d, e, f, g, h, i, j, ba” 。

Most significance digit(MSD)

直接按照字典的顺序进行排序,对于字符串、单词或者是长度固定的整数排序比较合适。比如:1, 10, 2, 3, 4, 5, 6, 7, 8, 9和 “b, ba, c, d, e, f, g, h, i, j”。

基数排序图示

这里写图片描述
这里写图片描述

从图示中可以看出基数排序(LSD)的基本流程为如下节。

基数排序流程

将根据整数的最右边数字将其扔进相应的0~9号的篮子里,对于相同的数字要保持其原来的相对顺序(确保排序算法的稳定性),然后将篮子里的数如图所示的串起来,然后再进行第二趟的收集(按照第二位的数字进行收集),就这样不断的反复,当没有更多的位时,串起来的数字就是排好序的数字。

算法分析

空间

采用顺序分配,显然不合适。由于每个口袋都有可能存放所有的待排序的整数。所以,额外空间的需求为10n,太大了。采用链接分配是合理的。额外空间的需求为n,通常再增加指向每个口袋的首尾指针就可以了。在一般情况下,设每个键字的取值范围为d, 首尾指针共计2×radix个,总的空间为O(n+2×radix)

时间

上图示中每个数计有2 位,因此执行2 次分配和收集就可以了。在一般情况下,每个结点有d 位关键字,必须执行d 次分配和收集操作。

  • 每次分配的代价:O(n)
  • 每次收集的代价:O(radix)
  • 总的代价为:O(d×(n+radix))

算法的c++ plus plus实现

基于LSD的基数排序算法:

 1 #include <iostream>
 2 
 3 using namespace std;
 4 const int MAX = 10;
 5 
 6 void print(int *a,int sz) {               
 7     for(int i = 0; i < sz; i++)
 8         cout << a[i] << " ";
 9     cout << endl;
10 }
11 
12 void RadixSortLSD(int *a, int arraySize)
13 {
14     int i, bucket[MAX], maxVal = 0, digitPosition =1 ;
15     for(i = 0; i < arraySize; i++) {
16         if(a[i] > maxVal) maxVal = a[i];
17     }
18 
19     int pass = 1;  // used to show the progress
20     /* maxVal: this variable decide the while-loop count 
21                if maxVal is 3 digits, then we loop through 3 times */
22     while(maxVal/digitPosition > 0) {
23         /* reset counter */
24         int digitCount[10] = {0};
25 
26         /* count pos-th digits (keys) */
27         for(i = 0; i < arraySize; i++)
28             digitCount[a[i]/digitPosition%10]++;
29 
30         /* accumulated count */
31         for(i = 1; i < 10; i++)
32             digitCount[i] += digitCount[i-1];
33 
34         /* To keep the order, start from back side */
35         for(i = arraySize - 1; i >= 0; i--)
36             bucket[--digitCount[a[i]/digitPosition%10]] = a[i];
37 
38         /* rearrange the original array using elements in the bucket */
39         for(i = 0; i < arraySize; i++)
40             a[i] = bucket[i];
41 
42         /* at this point, a array is sorted by digitPosition-th digit */
43         cout << "pass #" << pass++ << ": ";
44         print(a,arraySize);
45 
46         /* move up the digit position */
47         digitPosition *= 10;
48     }   
49  }
50 
51 int main()
52 {
53     int a[] = {170, 45, 75, 90, 2, 24, 802, 66};
54     const size_t sz = sizeof(a)/sizeof(a[0]);
55 
56     cout << "pass #0: ";
57     print(a,sz);
58     RadixSortLSD(&a[0],sz);
59     return 0;
60 }

输出为:

1 pass #0: 170 45 75 90 2 24 802 66 
2 pass #1: 170 90 2 802 24 45 75 66 
3 pass #2: 2 802 24 45 66 170 75 90 
4 pass #3: 2 24 45 66 75 90 170 802 

这里写图片描述

首先统计10个篮子(或口袋)中各有多少个数字,然后从0~9数字的频次分布(而不是频次密度,有一个累加的过程),以确定“收集”整数时的位置下标所在。同时为了保证排序算法稳定,相同的数字保持原来相对位置不变,对原始数据表倒序遍历,逐个构成收集后的数据表。例如,上图所示,对于数字66,其所对应的频次分布为8,也就是应当排在第8位,在数组中下标应该为7。而如果对于数字2和802,对应的频次分布为4,那么对于数据表从后往前遍历的话,对应802的下标为3,而2的下标2,这样实际上就保证了排序算法的稳定性。

桶排序(bucket sort)

基本思想

桶排序的基本思想是将一个数据表分割成许多buckets,然后每个bucket各自排序,或用不同的排序算法,或者递归的使用bucket sort算法。也是典型的divide-and-conquer分而治之的策略。它是一个分布式的排序,介于MSD基数排序和LSD基数排序之间。

基本流程

建立一堆buckets;
遍历原始数组,并将数据放入到各自的buckets当中;
对非空的buckets进行排序;
按照顺序遍历这些buckets并放回到原始数组中即可构成排序后的数组。

图示

这里写图片描述

算法的c++ plus plus描述

  1 #include <iostream>
  2 #include <iomanip>
  3 using namespace std;
  4 
  5 #define NARRAY 8  /* array size */
  6 #define NBUCKET 5 /* bucket size */
  7 #define INTERVAL 10 /* bucket range */
  8 
  9 struct Node 
 10 { 
 11     int data;  
 12     struct Node *next; 
 13 };
 14 
 15 void BucketSort(int arr[]);
 16 struct Node *InsertionSort(struct Node *list);
 17 void print(int arr[]);
 18 void printBuckets(struct Node *list);
 19 int getBucketIndex(int value);
 20 
 21 void BucketSort(int arr[])
 22 {   
 23     int i,j;
 24     struct Node **buckets;  
 25 
 26     /* allocate memory for array of pointers to the buckets */
 27     buckets = (struct Node **)malloc(sizeof(struct Node*) * NBUCKET); 
 28 
 29     /* initialize pointers to the buckets */
 30     for(i = 0; i < NBUCKET;++i) {  
 31         buckets[i] = NULL;
 32     }
 33 
 34     /* put items into the buckets */
 35     for(i = 0; i < NARRAY; ++i) {   
 36         struct Node *current;
 37         int pos = getBucketIndex(arr[i]);
 38         current = (struct Node *) malloc(sizeof(struct Node));
 39         current->data = arr[i]; 
 40         current->next = buckets[pos];  
 41         buckets[pos] = current;
 42     }
 43 
 44     /* check what's in each bucket */
 45     for(i = 0; i < NBUCKET; i++) {
 46         cout << "Bucket[" << i << "] : ";
 47             printBuckets(buckets[i]);
 48         cout << endl;
 49     }
 50 
 51     /* sorting bucket using Insertion Sort */
 52     for(i = 0; i < NBUCKET; ++i) {  
 53         buckets[i] = InsertionSort(buckets[i]); 
 54     }
 55 
 56     /* check what's in each bucket */
 57     cout << "-------------" << endl;
 58     cout << "Bucktets after sorted" << endl;
 59     for(i = 0; i < NBUCKET; i++) {
 60         cout << "Bucket[" << i << "] : ";
 61             printBuckets(buckets[i]);
 62         cout << endl;
 63     }
 64 
 65     /* put items back to original array */
 66     for(j =0, i = 0; i < NBUCKET; ++i) {    
 67         struct Node *node;
 68         node = buckets[i];
 69         while(node) {
 70             arr[j++] = node->data;
 71             node = node->next;
 72         }
 73     }
 74 
 75     /* free memory */
 76     for(i = 0; i < NBUCKET;++i) {   
 77         struct Node *node;
 78         node = buckets[i];
 79         while(node) {
 80             struct Node *tmp;
 81             tmp = node; 
 82             node = node->next; 
 83             free(tmp);
 84         }
 85     }
 86     free(buckets); 
 87     return;
 88 }
 89 
 90 /* Insertion Sort */
 91 struct Node *InsertionSort(struct Node *list)
 92 {   
 93     struct Node *k,*nodeList;
 94     /* need at least two items to sort */
 95     if(list == 0 || list->next == 0) { 
 96         return list; 
 97     }
 98 
 99     nodeList = list; 
100     k = list->next; 
101     nodeList->next = 0; /* 1st node is new list */
102     while(k != 0) { 
103         struct Node *ptr;
104         /* check if insert before first */
105         if(nodeList->data > k->data)  { 
106             struct Node *tmp;
107             tmp = k;  
108             k = k->next; 
109             tmp->next = nodeList;
110             nodeList = tmp; 
111             continue;
112         }
113 
114         for(ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
115             if(ptr->next->data > k->data) break;
116         }
117 
118         if(ptr->next!=0){  
119             struct Node *tmp;
120             tmp = k;  
121             k = k->next; 
122             tmp->next = ptr->next;
123             ptr->next = tmp; 
124             continue;
125         }
126         else{
127             ptr->next = k;  
128             k = k->next;  
129             ptr->next->next = 0; 
130             continue;
131         }
132     }
133     return nodeList;
134 }
135 
136 int getBucketIndex(int value)
137 {
138     return value/INTERVAL;
139 }
140 
141 void print(int ar[])
142 {   
143     int i;
144     for(i = 0; i < NARRAY; ++i) { 
145         cout << setw(3) << ar[i]; 
146     }
147     cout << endl;
148 }
149 
150 void printBuckets(struct Node *list)
151 {
152     struct Node *cur = list;
153     while(cur) {
154         cout << setw(3) << cur->data;
155         cur = cur->next;
156     }
157 }
158 
159 int main(void)
160 {   
161     int array[NARRAY] = {29,25,3,49,9,37,21,43};
162 
163     cout << "Initial array" << endl;
164     print(array);
165     cout << "-------------" << endl;
166 
167     BucketSort(array); 
168     cout << "-------------" << endl;
169     cout << "Sorted array"  << endl;
170     print(array); 
171     return 0;
172 }

输出为:

 1 Initial array
 2  29 25  3 49  9 37 21 43
 3 -------------
 4 Bucket[0] :   9  3
 5 Bucket[1] :
 6 Bucket[2] :  21 25 29
 7 Bucket[3] :  37
 8 Bucket[4] :  43 49
 9 -------------
10 Bucktets after sorted
11 Bucket[0] :   3  9
12 Bucket[1] :
13 Bucket[2] :  21 25 29
14 Bucket[3] :  37
15 Bucket[4] :  43 49
16 -------------
17 Sorted array
18   3  9 21 25 29 37 43 49

虽然程序中的bucket采用链表结构以充分利用空间资源,而且bucket的构造也很巧妙,做的数据结构类似于栈链表的形式,插入都是插到顶部,所以后遍历的数据总是会在上面,因此从放入bucket之后的输出可以看出,跟图示进行对比,发现确实跟原来的原始相对顺序相反。

计数排序(counting sort)

目前介绍的利用比较元素进行排序的方法对数据表长度为n的数据表进行排序时间复杂度不可能低于O(nlogn)。但是如果知道了一些数据表的信息,那么就可以实现更为独特的排序方式,甚至是可以达到线性时间的排序。

基本思想

当数据表长度为n,已知数据表中数据的范围有限,比如在范围0k之间,而k又比n小许多,这样可以通过统计每一个范围点上的数据频次来实现计数排序。

基本操作

根据获得的数据表的范围,分割成不同的buckets,然后直接统计数据在buckets上的频次,然后顺序遍历buckets就可以得到已经排好序的数据表。

算法的c++ plus plus实现

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 void print(int a[], int sz) {
 6     for (int i = 0; i < sz;  i++ ) cout << a[i] << " ";
 7     cout << endl;
 8 }
 9 
10 void CountingSort(int arr[], int sz) {
11     int i, j, k;
12     int idx = 0;
13     int min, max;
14 
15     min = max = arr[0];
16     for(i = 1; i < sz; i++) {
17         min = (arr[i] < min) ? arr[i] : min;
18         max = (arr[i] > max) ? arr[i] : max;
19     }
20 
21     k = max - min + 1;
22     /* creates k buckets */
23     int *B = new int [k]; 
24     for(i = 0; i < k; i++) B[i] = 0;
25 
26     for(i = 0; i < sz; i++) B[arr[i] - min]++;
27     for(i = min; i <= max; i++) 
28         for(j = 0; j < B[i - min]; j++) arr[idx++] = i;
29 
30     print(arr,sz);
31 
32     delete [] B;
33 }
34 
35 int main()
36 {
37     int a[] = {5,9,3,9,10,9,2,4,13,10};
38     const size_t sz = sizeof(a)/sizeof(a[0]);
39     print(a,sz);
40     cout << "----------------------\n" ;
41     CountingSort(a, sz);
42 }

输出为:

1 5 9 3 9 10 9 2 4 13 10
2 ----------------------
3 2 3 4 5 9 9 9 10 10 13

计算排序构造了k个buckets来统计数据频次,共需要两趟来实现排序,第一趟增量计数进行统计,第二趟将计数统计的对应的数重写入原始数据表中。

因为这种排序没有采用比较,所以突破了时间复杂度O(nlogn)的上限,但是counting sort又不像是一种排序,因为在复杂数据结构中,它不能实现同结构体中排序码的排序来对结构体进行排序。也就不要提稳定与否了。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章