This is one problem introduced in "Introduction to Algorithm".
We can use radix-sort to solve it.
package alg;
import java.util.ArrayList;
import java.util.Iterator;
/*
* This example shows how to use radix sort algorithm to sort N integers in the range of 0 ~ N^2-1.
*/
public class RadixSortExample {
void sort(int a[], int N){
int len = a.length;
ArrayList<ArrayList<Integer>> bucket= new ArrayList<ArrayList<Integer>>(N);
for(int i = 0; i<N;i++){
bucket.add(new ArrayList<Integer>(len));
}
ArrayList<Integer> temp = new ArrayList<Integer>(len);
for(int i = 0; i< len; i++){
temp.add(new Integer(a[i]));
}
for(int i = 0; i<len; i++){
int digit0 = temp.get(i).intValue() % N;
bucket.get(digit0).add(temp.get(i));
}
temp.clear();
for(int i = 0; i<N; i++){
Iterator<Integer> it = bucket.get(i).iterator();
while(it.hasNext()) temp.add(it.next());
}
for(int i = 0; i<N;i++){
bucket.get(i).clear();
}
for(int i = 0; i<len; i++){
int digit1 = temp.get(i).intValue() / N;
bucket.get(digit1).add(temp.get(i));
}
temp.clear();
for(int i = 0; i<N; i++){
Iterator<Integer> it = bucket.get(i).iterator();
while(it.hasNext()) temp.add(it.next());
}
Iterator<Integer> it = temp.iterator();
while(it.hasNext()) System.out.println(it.next());
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int a []= {63,20,43,15,56,9,1,28};
RadixSortExample r = new RadixSortExample();
r.sort(a,8);
}
}
分享到:
相关推荐
| _O(2^n)_ | _O(n)_ | Hard | 馃摉 | 421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an...
- The coordinates of the observed events are integers in the range \([-1000000, 1000000]\). - The number of events \( n \) and the number of causes \( m \) satisfy \( 1 \leq n, m \leq 100000 \). ##...
These questions cover a range of fundamental concepts in Java, including database technology, object-oriented programming, data structures, and concurrency. Understanding these topics is crucial for ...
1. Introduction to Zend Framework 1.1. 概述 1.2. 安装 2. Zend_Acl 2.1. 简介 2.1.1. 关于资源(Resource) 2.1.2. 关于角色(Role) 2.1.3. 创建访问控制列表(ACL) 2.1.4. 注册角色(Role) 2.1.5. 定义访问...
4. **Numbers and Integers**: Number是双精度浮点数,Integer是整型数据,Interval和Interval2用于定义数值范围。 5. **Shaders**: 着色器用于控制物体表面的视觉效果,如颜色、纹理和光照。 6. **Strings and ...