简介
counting sort和radix sort和原来的那些通过比较交换来排序的方法不一样。原来的常用排序算法比如插入排序,快速排序等都通过交换元素和递归等手段。而counting sort和radix sort都采用一种类似于映射的方式来实现排序的效果。当然,这种方式之所以会达到O(n)的量级,主要的原因在于这些个排序算法有一个限制,就是首先他们数据的取值范围是在[0, k],数据的个数为n,且n >= k。
counting sort
推导思路
counting sort的过程是基于一个很直观的思考。在前面提到过,我们有n个元素,所有元素的取值范围在[0, k]这个区间。那么,假设我们有一个数组b,它的长度为k的话,那么对于数组中间的任意一个元素i,它在排序后的位置肯定就映射到b[i]的这个点上。只是可能有多个重复的值对应到同一个点。取一个最特殊的情况,假设我们正好也是有k个元素,而且每个元素也都仅出现一次。那么,按照我们这个映射的思路,每个元素放到对应数组索引的位置,排序的结果就生成了。
再在我们前面说的这个特殊情况的基础上考虑让它更加通用化一点。前面的直接映射是在于每个值都只出现唯一一次。而实际上可能有一个数字出现了若干次而有的数字完全没有出现过。但是,不管它出现没出现,他们所有的值的范围是在[0, k]之间。那么,如果我们定义一个b[k]这样的数组来映射,如果某个元素i出现的次数多于一次的话,我们可以将它出现的次数设置为b[i]的数值。如下图所示:
这样,我们这个数组里就保存了一个所有元素映射后的结果。只不过有的点是对应了多个同样的值。如果这个时候再返回所有排序后的结果,相信只要通过一个循环,从最小到最大。碰到b[i]值为0的则表示没有,直接跳过。大于0的表示出现了多个,就重复输出多个i。那么,这个映射的方法也就出来了。最终映射的结果如下图:
通过前面的讨论,我们可以得出如下的代码:
public static void countingSort(int[] a, int[] b, int k) { int[] c = new int[k]; for(int i = 0; i < a.length; i++) c[a[i]] = c[a[i]] + 1; int count = 0; for(int j = 0; j < c.length; j++) { while(c[j] > 0) { b[count++] = j; c[j]--; } } }
这是一种通过记录结果然后重新构造的方式来返回结果。当然,我们也可以直接返回数组b。
嗯.....慢着慢着。如果你看过书上counting sort的代码的话,你会发现,这和书上说的完全不一样啊。虽然实际的实现方式有点差别,实际上,我们这种方法和书上的思路是一样的。现在我们再来看看书上的写法吧。
书上说
书上说的counting sort大致是分为三个步骤。1. 统计数字的映射,和我们前面的方法一样。 2. 对数组进行累加,每个元素表示原来数组中从开头到当前元素的和。3. 再根据原来的数组来映射出新的排序后的结果。说到这里,大家可能对第2,3步还是不太清楚。没关系,我们一点点的来看。
首先,按照原来的统计方式,我们可以得到一个统计结果的数组。以原来的数据为例,我们可以通过如下代码:
for(int i = 0; i < a.length; i++) c[a[i]] = c[a[i]] + 1;
得到一个结果数组,如下图:
然后,我们再通过如下的代码,进行累加:
for(int i = 1; i < k; i++) c[i] = c[i] + c[i - 1];
这样,我们可以得到一个如下的数组:
我们来看这么一个累加的步骤的意义。每次我们将当前的元素加上前面的元素时,前面的元素表示从最开始元素到当前元素的累加。那么对于结果数组中的任一元素i,c[i]表示从c[0]到c[i]之间所有元素的和。再看我们前面定义的这个数组的含义。它本身是用来保存当前值为i的元素的个数的。那么c[i]则表示从0到i的所有元素的总和。再换一个角度来想想,既然c[i]表示最大值为i的所有元素个数,那么如果有i这么一个元素的话,它最大的索引就是c[i]。
那么,有没有这个元素i呢?这就要看我们的源数组了,假定为a[i]。对于每个存在的元素a[i],我们可以发现它对应的最大索引则为c[a[i]]。然后,再考虑到我们有元素重复的情况,我们可以在每次找到一个对应的c[a[i]]的情况下,把c[a[i]]减一。这相当于我们已经取了这个元素i之后,保证剩下元素的正确性。那么,这几个操作就是我们讲到的第三步。它对应实现的代码如下:
for(int j = a.length - 1; j >= 0; j--) { b[c[a[j]]--] = a[j]; }
将我们前面的这几个步骤统一一下,couting sort在书面上定义的一个完整实现方法如下:
public static void countingSort(int[] a, int[] b, int k) { int[] c = new int[k]; for(int i = 0; i < a.length; i++) c[a[i]] = c[a[i]] + 1; for(int i = 1; i < k; i++) c[i] = c[i] + c[i - 1]; for(int j = a.length - 1; j >= 0; j--) { b[c[a[j]]--] = a[j]; } }
在实际实现中,考虑到我们要用到的数组是从0开始索引的,所以后面第三步映射的时候结果数组b对应的值要减一。
radix sort
radix sort是一个看起来很好理解,实现起来还是有点麻烦的方法。它也有一个强烈的前置依赖条件。就是我要排序的数据具有相同的位数。比如说,我所有的数据都是3位数或者4位数的。然后我们对所有数据从最小一位到最大的位开始排序。下图展示了一个radix sort的流程:
从本身radix sort的定义来看,我们发现他们有一个有意思的特性。对于n个元素,它们对应的每一位的值的范围都是在[0,9] 之间的。没想到,这倒是一个很符合前面counting sort要求的条件。那么,就上counting sort吧。我们将他们每一位按照counting sort排序,这样得到的最后结果就是radix sort了。
当然,这里有一个和纯counting sort不一样的地方。原来每次排序我们是针对整个数字,这次只是针对数字的一个位。每次映射的时候就需要注意这么一个对应的关系。
另外,还有一个需要考虑的就是每次取数据中间的某一位。我们可以通过不断整除的方式来求。这个得出某一位数字的方法如下:
public static int getNthDigit(int value, int n) { for(int i = 0; i < n; i++) { value /= 10; } return value % 10; }
在将前面的几部分整合起来,也不难得出radix sort剩下的部分了:
public static int[] radixSort(int[] a, int bitCount) { int[] c; int[] b = new int[a.length]; for(int k = 0; k < bitCount; k++) { c = new int[10]; for(int i = 0; i < a.length; i++) { int nThDigit = getNthDigit(a[i], k); c[nThDigit] = c[nThDigit] + 1; } for(int i = 1; i < c.length; i++) c[i] = c[i] + c[i - 1]; for(int j = a.length - 1; j >= 0; j--) { int bitDigit = getNthDigit(a[j], k); b[c[bitDigit]--] = a[j]; } for(int i = 0; i < b.length; i++) a[i] = b[i]; } return b; }
总结
counting sort的本质无非是利用数字范围的有限性然后进行映射计数。它能够高效运行的一个前提是他们元素的取值范围不大。它的时间复杂度为O(n)。因为要考虑结果的映射和拷贝,空间复杂度为O(n + k)。假定k是所有元素的取值范围。radix sort有一个要求是所有比较元素长度要一样,他们可以按位进行比较排序。它的时间复杂度为O(nk)。假设k为元素的位数。counting sort和radix sort都是稳定的排序算法。
相关推荐
Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort
Lecture 5 Linear-time Sorting Lower Bounds, Counting Sort, Radix Sort.pdf
珠排序(Bead Sort) 二进制插入排序(Binary Insertion Sort) 比特排序(Bitonic Sort) 乱序排序(Bogo Sort) 冒泡排序(Bubble Sort) 桶排序(Bucket Sort) ...最高有效数字优先的基数排序(Msd Radix Sort)
经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - 选择排序Selection sort 经典排序算法 - ...
计数排序(Counting Sort) 基数排序(Radix Sort) 桶排序(Bucket Sort) 深度优先搜索(Depth-First Search, DFS) 广度优先搜索(Breadth-First Search, BFS) 二分查找(Binary Search) 线性查找(Linear ...
Counting Sort Radix Sort MSD Vs LSD Bucket Sort ####快速排序 QuickSort是分而治之的算法。 大列表分为两部分,分别排序(征服),排序后的列表合并。 在“就地”实施的快速排序中,列表使用相同的数组进行...
1.7 CountingSort: 假设数据分布在0到k之间的。对于每个输入x,确定出小于x的数的个数。假设小于x的数有17个,那么x就应该在第18个输出位置。 1. 8 Radix sort(基数排序):从最低位开始,每位采用稳定的排序算法...
java十大排序算法实现 1. 冒泡排序(Bubble Sort) 2. 选择排序(Selection Sort) ...7. 计数排序(Counting Sort) 8. 桶排序(Bucket Sort) 9. 基数排序(Radix Sort) 10. 希尔排序(Shell Sort)
请参考算法导论第三版英文版Introduction to Algorithms 3rd Edition,本程序为第一章到第八章重要排序等算法的c/c++实现。IDE环境为vc++ 6.0。函数名称与算法导论原文类似。...Counting sort Radix sort 二分法搜索
数据结构与算法-Python语言案例实现十大经典排序算法一、 ... 计数排序(Counting Sort)9. 桶排序(Bucket Sort)10. 基数排序(Radix Sort)三、算法总结 十大经典排序算法 一、 引言 授人以鱼不如授人以渔~ 实践是检
leetcode 和 oj leetcode ...counting sort 基数排序 radix sort 桶排序bucket sort 堆排序 heap_sort 二分查找 69 744 540 278 852[Easy] 贪心法 455 [Medium]435 [Medium]452 [Medium]406 121 122 605
算法的特性和设计原则 2. 数据结构 栈(Stack) 队列(Queue) 链表(Linked List) 树(Tree) 堆(Heap) 字典(Dictionary) 哈希表(Hash Table) 图(Graph) 3. 基本算法思维 枚举 递归 回溯 分治 贪心算法 ...
void radix_counting_sort ( unsigned *input, long length, long radix, long len); 笔记: length表示输入数组的长度 基数表示应该选择数字的哪一部分作为键 len表示一个段应该有多长 如果您
8.3 Radix sort 197 8.4 Bucket sort 200 9 Medians and Order Statistics 213 9.1 Minimum and maximum 214 9.2 Selection in expected linear time 215 9.3 Selection in worst-case linear time 220 III Data ...
8.3 Radix sort 197 8.4 Bucket sort 200 9 Medians and Order Statistics 213 9.1 Minimum and maximum 214 9.2 Selection in expected linear time 215 9.3 Selection in worst-case linear time 220 III Data ...
8.3 Radix sort 197 8.4 Bucket sort 200 9 Medians and Order Statistics 213 9.1 Minimum and maximum 214 9.2 Selection in expected linear time 215 9.3 Selection in worst-case linear time 220 III Data ...
8.3 Radix sort 197 8.4 Bucket sort 200 9 Medians and Order Statistics 213 9.1 Minimum and maximum 214 9.2 Selection in expected linear time 215 9.3 Selection in worst-case linear time 220 III Data ...
8.3 Radix sort 170 8.4 Bucket sort 174 9 Medians and Order Statistics 183 9.1 Minimum and maximum 184 9.2 Selection in expected linear time 185 9.3 Selection in worst-case linear time 189 III Data ...
8.3 Radix sort 197 8.4 Bucket sort 200 9 Medians and Order Statistics 213 9.1 Minimum and maximum 214 9.2 Selection in expected linear time 215 9.3 Selection in worst-case linear time 220 III Data ...