Java实现基于桶式排序思想和计数排序思想实现的基数排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java实现基于桶式排序思想和计数排序思想实现的基数排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2635字，纯文字阅读大概需要4分钟。
内容图文
计数排序
前提：待排序表中的所有待排序关键字必须互不相同；
思想：计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，则该记录在新的有序表中的存放位置即为c。
性能：空间复杂度：o(n)；时间复杂度:o(n^2)；
1
public
int[] countSort(int[] array){
2int[] tempArray = newint[array.length]; //引入辅助数组 3for(int i=0;i<array.length;i++){
4int count = 0;
5for(int j=0;j<array.length;j++){
6if(array[i]>array[j]){
7 count++;
8 }
9 }
10 tempArray[count] = array[i];
11 }
12return tempArray;
13 }
桶式排序
桶式排序需要待排序的序列满足以下两个特征：
待排序列所有的值处于一个可枚举的范围之类；
待排序列所在的这个可枚举的范围不应该太大，否则排序开销太大。
排序的具体步骤如下：
（1）对于这个可枚举范围构建一个buckets数组，用于记录“落入”每个桶中元素的个数；
（2）将（1）中得到的buckets数组重新进行计算，按如下公式重新计算：
buckets[i] = buckets[i] +buckets[i-1] (其中1<=i<buckets.length);
1
public
static
void bucketSort(int[] data) {
2//得到待排序元素中的最大值和最小值 3int max=data[0],min=data[0];
4for(int i=1;i<data.length;i++){
5if(data[i]>max){
6 max = data[i];
7 }
8if(data[i] < min){
9 min = data[i];
10 }
11 }
1213// 缓存数组 14int[] tmp = newint[data.length];
15// buckets用于记录待排序元素的信息
16// buckets数组定义了max-min+1个桶 17int[] buckets = newint[max-min+1];
18// 计算每个元素在序列出现的次数 19for (int i = 0; i < data.length; i++) {
20 buckets[data[i] - min]++;
21 }
22// 计算“落入”各桶内的元素在有序序列中的位置 23for (int i = 1; i < max - min; i++) {
24 buckets[i] = buckets[i] + buckets[i - 1];25 }
26// 将data中的元素完全复制到tmp数组中 27 System.arraycopy(data, 0, tmp, 0, data.length);
28// 根据buckets数组中的信息将待排序列的各元素放入相应位置 29for (int k = data.length - 1; k >= 0; k--) {
30data[--buckets[tmp[k] - min]] = tmp[k];
31 }
32 }
基于桶式排序思想和计数排序思想实现基数排序：
将待排序元素中的每组关键字依次进行桶分配。
1
public
int[] radixSortBuckets(int[] array, int radix) {
2// 找到待排序序列中的最大元素 3int max = array[0];
4for (int i = 1; i < array.length; i++) {
5if (array[i] > max) {
6 max = array[i];
7 }
8 }
9// 确定最大元素的位数maxBits10int maxBits = 0;
11while (max > 0) {
12 max = max/10;
13 maxBits++;
14 }
1516int[] tempArray = newint[array.length]; //用于暂存元素17int[] buckets = newint[radix]; //用于桶式排序18int rate = 1;
19// 进行maxBits次分配和收集20for(int i=0; i< maxBits;i++){
21// 将array中的元素完全复制到arrayTemp数组中22 System.arraycopy(array, 0, tempArray, 0, array.length);
23 Arrays.fill(buckets, 0); // 重置buckets数组
2425//分配：计算每个待排序元素的子关键字，并将其次数加到对应的桶中26for(int j=0;j<tempArray.length;j++){
27 buckets[(tempArray[j]/rate)%radix] ++;
28 }
29// 计算“落入”各桶内的元素在有序序列中的位置30for(int k=1;k<buckets.length;k++){
31 buckets[k] = buckets[k]+buckets[k-1];
32 }
3334// 收集：按子关键字对指定的数据进行排序35for(int m=tempArray.length-1;m>=0;m--){
36int subKey = (tempArray[m]/rate)%radix;
37 array[--buckets[subKey]] = tempArray[m];
38 }
3940 rate *= radix;
41 }
42return array;
43 }
原文：http://www.cnblogs.com/CherishFX/p/4650691.html
内容总结
以上是互联网集市为您收集整理的Java实现基于桶式排序思想和计数排序思想实现的基数排序全部内容，希望文章能够帮你解决Java实现基于桶式排序思想和计数排序思想实现的基数排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。