Java CountingSort
2024-09-01 15:07:25
Java CountingSort
/**
* <html>
* <body>
* <P> Copyright 1994-2018 JasonInternational </p>
* <p> All rights reserved.</p>
* <p> Created on 2018年4月10日 </p>
* <p> Created by Jason</p>
* </body>
* </html>
*/
package cn.ucaner.algorithm.sorts; /**
* Counting sort is an algorithm for sorting a collection of objects according
* to keys that are small integers; that is, it is an integer sorting algorithm.
* It operates by counting the number of objects that have each distinct key
* value, and using arithmetic on those counts to determine the positions of
* each key value in the output sequence.
* <p>
* Family: Counting.<br>
* Space: An Array of length r.<br>
* Stable: True.<br>
* <p>
* Average case = O(n+r)<br>
* Worst case = O(n+r)<br>
* Best case = O(n+r)<br>
* <p>
* NOTE: r is the range of numbers (0 to r) to be sorted.
* <p>
* @see <a href="https://en.wikipedia.org/wiki/Counting_sort">Counting Sort (Wikipedia)</a>
* <br>
* @author Justin Wetherell <phishman3579@gmail.com>
*/
public class CountingSort { private CountingSort() { } public static Integer[] sort(Integer[] unsorted) {
int maxValue = findMax(unsorted);
int[] counts = new int[maxValue + 1];
updateCounts(unsorted, counts);
populateCounts(unsorted, counts);
return unsorted;
} private static int findMax(Integer[] unsorted) {
int max = Integer.MIN_VALUE;
for (int i : unsorted) {
if (i > max)
max = i;
}
return max;
} private static void updateCounts(Integer[] unsorted, int[] counts) {
for (int e : unsorted)
counts[e]++;
} private static void populateCounts(Integer[] unsorted, int[] counts) {
int index = 0;
for (int i = 0; i < counts.length; i++) {
int e = counts[i];
while (e > 0) {
unsorted[index++] = i;
e--;
}
}
}
}
最新文章
- 【转】C# 中 10 个你真的应该学习（和使用！）的功能
- java 遍历arrayList的四种方法
- jQuery 名称冲突
- python-program
- Android系统目录介绍
- 用css 制作三角
- gravity、layout_gravity及orientation
- 在CentOS6.7操作系统上编译安装httpd2.4
- 创建laravel项目时打开浏览器常见错误
- MemcacheQ 的安装与使用
- JAVA中的策略模式
- The sound of silence引发的关于互联网以及教育的利弊思考
- java7增强的try语句关闭资源
- “战术竞技类”外挂打击已开始！揭秘腾讯We Test游戏安全服务新动作！
- Windows--常见端口号
- Javascript URI 解析介绍
- S2算法应用
- libgdx学习记录20——多线程MultiThread资源处理
- Educational Codeforces Round 14 C. Exponential notation 数字转科学计数法
- Zabbix之Python脚本端口自动发现