`
standalone
  • 浏览: 620917 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

sort n integers of range 0~n^2-1 in O(n) time

 
阅读更多

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);
    }

}

 

分享到:
评论

相关推荐

    LeetCode最全代码

    | _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...

    POJ 1727 Advanced Causal Measurements (ACM)解题报告

    - 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 \). ##...

    java英文笔试

    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 ...

    ZendFramework中文文档

    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. 定义访问...

    grasshopper中文版运算器名称对照.pdf

    4. **Numbers and Integers**: Number是双精度浮点数,Integer是整型数据,Interval和Interval2用于定义数值范围。 5. **Shaders**: 着色器用于控制物体表面的视觉效果,如颜色、纹理和光照。 6. **Strings and ...

Global site tag (gtag.js) - Google Analytics