本文主要是介绍排序算法(三)_计数排序、基数排序的Java实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
继续排序相关的内容，上次聊了几个theta(nlgn)的比较型排序，今天聊一下线性时间theta(n)的排序算法。都比较简单，大部分内容来自<算法导论>公开课视频。两个算法分别是计数排序、基数排序，如果不看书的话，真的很难凭空想到。
计数排序：设有待排序数组A，辅助数组B，结果数组C。计数排序的关键有两点：
一、在于辅助数组的设计，辅助数组C上元素的索引对应数组A中的某个具体的元素。而C上的元素C[i]，则表示了A中有C[i]个元素小于等于值i。
二、从辅助数组C到结果数组B的还原，从数组末尾向前还原，直觉上的依据就是将符合条件的元素插入到适合范围的最右侧。很绕口哈，举个例子：C[3]=3，说明A中小于等3的有3个元素，而这3个元素必定分布在1,2,3这3个位置。。哎，扯不清了>.<，还是直接上代码吧。
package com.wly.algorithmbase.sort;
/*** 计数排序，适合于小范围数据分布的排序，时间复杂度O(k+n)* 注意：这里的排序假设前提所有元素都是大于0的正整数* @author wly* @pseudocode* for i <- 1 to k //k表示带排序数组的元素上限值* do c[i] <- 0 //辅助数组，长度为k* for j <- 1 to n //将元素数组映射到辅助数组* do c[A[j]] <- c[A[j]] + 1 * for i <- 2 to k //处理辅助数组，使c[j]表示待排序数组中小于等于j的元素个数* do c[i] <- c[i] + c[i-1]* for j <- n downto 1 //从后往前还原排序数组元素到一个新的数组* do B[C[A[j]]] <- A[i]-1* C[A[j]] <- C[A[j]] - 1 //更新辅助数组，因为有一个小于等于j的元素被还原**/
public class CountingSort {public static void main(String[] args) {//首位加0，同步伪代码int[] A = {0,3,5,1,2,7,4,3,2,1,6,7,2};System.out.println("排序前:");for(int i:A) {System.out.print(i + " ");}System.out.println("\n排序后:");CountingSort countingSort = new CountingSort();int[] B = countingSort.sort(A);for(int i:B) {System.out.print(i + " ");}}/*** 计数排序实现，注意这里的实现和伪代码不同的是，数组是从0开始的* * @param A*/public int[] sort(int[] A) {int k = findMax(A);int[] C = new int[k+1]; //长度加1，同步伪代码int[] B = new int[A.length];//初始化for(int i=0;i<C.length;i++) {C[i] = 0;}//将带排序数组元素重复个数映射到辅助数组中for(int i=1;i<A.length;i++) {C[A[i]] = C[A[i]] + 1;}//处理辅助数组，使c[j]表示待排序数组中小于等于j的元素个数for(int i=1;i<C.length;i++) {C[i] = C[i] + C[i-1];}//从后往前还原排序数组元素到一个新的数组int i = A.length-1;for(;i>0;i--) {B[C[A[i]]] = A[i];C[A[i]] = C[A[i]] - 1;}return B;}public int findMax(int[] A) {int temp = 0;for(int i:A) {if(i > temp) {temp = i;}}return temp;}
}
运行结果:
排序前:
0 3 5 1 2 7 4 3 2 1 6 7 2
排序后:
0 1 1 2 2 2 3 3 4 5 6 7 7 基数排序：一句话，从低位往高位排序，如果相同则保持位置。算法的原理是当对第T位进行排序时，后面的T-1都已经完成排序了，即影响排序结果的之后第T位。或者说第T为的对排序的影响大于后面T-1位数，只有在第T位相同时，采用T-1位的比较结果做补充。
由于基数排序是从低到高一位一位进行排序的，那么可以使用上文中讲到的计数排序来完成每一位的排序(实际上可以将2位数视为一个比较单元，用计数排序进行排序)。
package com.wly.algorithmbase.sort;/*** 基数排序* @author wly**/
public class RadixSort {public static void main(String[] args) {byte[][] A = {{0,0,0,0,0,0,0,0,0},{1,2,3,4,5,6,4,8,9},{1,5,3,4,5,6,7,8,9},{3,2,3,4,5,6,7,8,6},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,9,9},{1,2,3,4,5,6,3,8,9},{1,2,3,4,5,2,7,8,9},{1,2,3,4,6,6,7,8,9},{1,2,3,9,5,6,7,8,9},};System.out.println("基数排序前:");for(int i=0;i<A.length;i++) {for(int j=0;j<A[0].length;j++) {System.out.print(A[i][j] + " ");}System.out.println();}System.out.println("\n基数排序后:");RadixSort sort = new RadixSort();sort.sort(A, A[0].length-1);}public void sort(byte[][] A,int p) {byte[][] B = new byte[A.length][A[0].length];int[] C = new int[10];if(p >= 0) {//根据第i为进行排序//初始化for(int i=0;i<C.length;i++) {C[i] = 0;}//将带排序数组元素重复个数映射到辅助数组中for(int i=1;i<A.length;i++) {C[A[i][p]] = C[A[i][p]] + 1;}//处理辅助数组，使c[j]表示待排序数组中小于等于j的元素个数for(int i=1;i<C.length;i++) {C[i] = C[i] + C[i-1];}//从后往前还原排序数组元素到一个新的数组int i = A.length-1;for(;i>0;i--) {B[C[A[i][p]]] = A[i];C[A[i][p]] = C[A[i][p]] - 1;}sort(B,p-1);} else {for(int i=0;i<A.length;i++) {for(int j=0;j<A[i].length;j++) {System.out.print(A[i][j] + " ");}System.out.println();}}}
}运行结果:
基数排序前:
0 0 0 0 0 0 0 0 0
1 2 3 4 5 6 4 8 9
1 5 3 4 5 6 7 8 9
3 2 3 4 5 6 7 8 6
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 9 9
1 2 3 4 5 6 3 8 9
1 2 3 4 5 2 7 8 9
1 2 3 4 6 6 7 8 9
1 2 3 9 5 6 7 8 9 基数排序后:
0 0 0 0 0 0 0 0 0
1 2 3 4 5 2 7 8 9
1 2 3 4 5 6 3 8 9
1 2 3 4 5 6 4 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 9 9
1 2 3 4 6 6 7 8 9
1 2 3 9 5 6 7 8 9
1 5 3 4 5 6 7 8 9
3 2 3 4 5 6 7 8 6 O啦~~~
谢谢!!
这篇关于排序算法(三)_计数排序、基数排序的Java实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
