文档章节

基数排序 和桶排序

pczhangtl
 pczhangtl
发布于 2014/09/09 18:04
字数 753
阅读 28
收藏 0
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class RadixSort{

	public static void radixSort(int arr[], int maxDigits){
		int exp = 1;//10^0;
		for(int i =0; i < maxDigits; i++){
			ArrayList bucketList[] = new ArrayList[10];
			for(int k=0; k < 10; k++){
				bucketList[k] = new ArrayList();
			}
			for(int j =0; j < arr.length; j++){
				int number = (arr[j]/exp)%10;
				bucketList[number].add(arr[j]);
			}
			exp *= 10;
			int index =0;
			for(int k=0; k < 10; k++){
				for(int num: (ArrayList<Integer>)bucketList[k]){
					arr[index] = num;
					index++;
				}
			}
		}

		System.out.println("Sorted numbers");
		for(int i =0; i < arr.length; i++){
			System.out.print(arr[i] +", ");
		}
	}
	
	public static void radixSort1( int[] a)
    {
        int i, m = a[0], exp = 1, n = a.length;
        int[] b = new int[10];
        for (i = 1; i < n; i++)
            if (a[i] > m)
                m = a[i];
        while (m / exp > 0)
        {
            int[] bucket = new int[10];
 
            for (i = 0; i < n; i++)
                bucket[(a[i] / exp) % 10]++;
            for (i = 1; i < 10; i++)
                bucket[i] += bucket[i - 1];
            for (i = n - 1; i >= 0; i--)
                b[--bucket[(a[i] / exp) % 10]] = a[i];
            for (i = 0; i < n; i++)
                a[i] = b[i];
            exp *= 10;        
        }
    }    
	
    public static void radixSort(int[] arr){
        if(arr.length == 0)
            return;
        int[][] np = new int[arr.length][2];
        int[] q = new int[0x100];
        int i,j,k,l,f = 0;
        for(k=0;k<4;k++){
            for(i=0;i<(np.length-1);i++)
                np[i][1] = i+1;
            np[i][1] = -1;
            for(i=0;i<q.length;i++)
                q[i] = -1;
            for(f=i=0;i<arr.length;i++){
                j = ((0xFF<<(k<<3))&arr[i])>>(k<<3);
                if(q[j] == -1)
                    l = q[j] = f;
                else{
                    l = q[j];
                    while(np[l][1] != -1)
                        l = np[l][1];
                    np[l][1] = f;
                    l = np[l][1];
                }
                f = np[f][1];
                np[l][0] = arr[i];
                np[l][1] = -1;
            }
            for(l=q[i=j=0];i<0x100;i++)
                for(l=q[i];l!=-1;l=np[l][1])
                        arr[j++] = np[l][0];
        }
    }

    public static void radixSort4(int A[], int B[], int n, int b, int r, int C[]){
    	int j ; 
    	int m = b/r;
    	int radix2 = 1;
    	for(int i = 0; i <r; i++){
    		radix2 *= 2;
    	}
    	for(int i = 0, t = 1; i < m; i++, t*=radix2){
    		for(j = 0; j < radix2; j++){
    			C[j] = 0;
    		}
    		
    		for(j = 0; j < n; j++){
    			C[(A[j]/t)%radix2]++;
    		}
    		
    		for(j = 1; j < radix2; j++){
    			C[j] = C[j - 1] + C[j];
    		}
    		
    		for(j = n -1 ; j >= 0; j--){
    			B[--C[(A[j]/t)%radix2]] = A[j];
    		}
    		
    		for(j = 0; j < n; j++){
    			A[j] = B[j];
    		}
    	}
    }
    /**
	 * place elements in data into order
	 *
	 * @param data array of positive integer values
	 */
	public static void radixSort2(int [ ] data) {
		boolean flag = true;
		int divisor = 1;
		Queue [ ] buckets = new Queue[10];
		for (int i = 0; i < 10; i++)
			buckets[i] = new LinkedList<Integer>();

		while (flag) {
			flag = false;
				// first copy the values into buckets
			for (int i = 0; i < data.length; i++) {
				int hashIndex = (data[i] / divisor) % 10;
				if (hashIndex > 0) flag = true;
				((LinkedList<Integer>)buckets[hashIndex]).addLast(new Integer(data[i]));
			}
				// then copy the values back into vector
			divisor *= 10;
			int i = 0;
			for (int j = 0; j < 10; j++) {
				while (! buckets[j].isEmpty()) {
					Integer ival = (Integer) ((LinkedList<Integer>)buckets[j]).getFirst();
					((LinkedList<Integer>)buckets[j]).removeFirst();
					data[i++] = ival.intValue();
				}
			}
		}
	}
	
	 // Sort the numbers beginning with least-significant digit
    public static int[] radixSort3(int[] input){
 
        // Largest place for a 32-bit int is the 1 billion's place
        for(int place=1; place <= 1000000000; place *= 10){
            // Use counting sort at each digit's place
            input = countingSort(input, place);
        }
 
        return input;
    }
 
    private static int[] countingSort(int[] input, int place){
        int[] out = new int[input.length];
 
        int[] count = new int[10];
 
        for(int i=0; i < input.length; i++){
            int digit = getDigit(input[i], place);
            count[digit] += 1;
        }
 
        for(int i=1; i < count.length; i++){
            count[i] += count[i-1];
        }
 
        for(int i = input.length-1; i >= 0; i--){
            int digit = getDigit(input[i], place);
 
            out[count[digit]-1] = input[i];
            count[digit]--;
        }
 
        return out;
 
    }
 
    private static int getDigit(int value, int digitPlace){
        return ((value/digitPlace ) % 10);
    }
	
    public static void main(String[] args){
        int i;
        int[] arr = new int[10];
        int[] arr1 = new int[10];
        int[] arr2 = new int[256];
        System.out.print("original: ");
        for(i=0;i<arr.length;i++){
            arr[i] = (int)(Math.random() * 1024);
            System.out.print(arr[i] + " ");
        }
        //radixSort(arr);
        //radixSort(arr, 4);
        //radixSort2(arr);
        radixSort4(arr, arr1, 10, 32, 8, arr2);
        System.out.print("\nsorted: ");
        for(i=0;i<arr.length;i++)
            System.out.print(arr[i] + " ");
        System.out.println("\nDone ;-)");
    }
}



© 著作权归作者所有

共有 人打赏支持
pczhangtl
粉丝 46
博文 707
码字总数 113318
作品 0
浦东
高级程序员
私信 提问
计数排序vs基数排序vs桶排序

从计数排序说起 计数排序是一种非基于元素比较的排序算法,而是将待排序数组元素转化为计数数组的索引值,从而间接使待排序数组具有顺序性。 计数排序的实现一般有两种形式:基于辅助数组和基...

超人汪小建
02/18
0
0
常用的内部排序方法-非比较排序

这篇文章中我们来探讨一下常用的非比较排序算法:计数排序,基数排序,桶排序。在一定条件下,它们的时间复杂度可以达到O(n)。   这里我们用到的唯一数据结构就是数组,当然我们也可以利用...

亮亮-AC米兰
2017/01/22
0
0
排序算法——桶排序、计数排序和基数排序

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/87905129 桶排序、计数排序和基数排...

dby_freedom
02/24
0
0
数据结构-基数排序(桶排序)

基数排序和计数排序都属于“非比较排序”,有关计数排序可查看http://blog.csdn.net/sssssuuuuu666/article/details/78677302。 基数排序介绍: 基数排序(radix sort)属于“分配式排序”(...

sssssuuuuu666
2017/12/15
0
0
数据结构基础(15) --基数排序

基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。 实现多关键字排序通常有两种作法: 最低位优先法(LSD) 先对K[0]{基数的最低位}进行排序,并按 K(0) 的不同...

翡青
2015/01/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

欧拉公式

欧拉公式表达式 欧拉公式的几何意 cosθ + j sinθ 是个复数,实数部分也就是实部为 cosθ ,虚数部分也就是虚部为 j sinθ ,对应复平面单位圆上的一个点。 根据欧拉公式和这个点可以用 复指...

sharelocked
56分钟前
2
0
burpsuite无法抓取https数据包

1.将浏览器和burpsuite的代理都设置好 2.在浏览器地址栏输入: http://burp 3.下载下面的证书,并将证书导入浏览器 cacert.der

Frost729
今天
2
0
JeeSite4.x 消息管理、消息推送、消息提醒

实现统一的消息推送接口,包含PC消息、短信消息、邮件消息、微信消息等,无需让所有开发者了解消息是怎么发送出去的,只需了解消息发送接口即可。 所有推送消息均通过 MsgPushUtils 工具类发...

ThinkGem
今天
7
0
OpenML

https://www.openml.org/search?type=data

shengjuntu
今天
2
0
java强引用,软引用,弱引用和虚引用

先来简要说一下这四种引用的特性: 强引用:如果一个对象具有强引用,那垃圾回收器绝不会回收它 软引用:如果一个对象只具有软引用,则内存空间足够,垃圾回收器就不会回收它 弱引用:在垃圾...

woshixin
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部