数据结构之桶排序

今天药忘吃喽~ 2022-08-11 21:29 156阅读 0赞

package com.zhiru;
    /*
     * 桶排序
     * 思路：将读入数据序列放入不同的桶中，
     * 桶个数=数据中最大的数据+1；
     * 对每个桶进行排序【排序方法任意】
     * 最后顺序输出各个桶中数据。
     * 平均时间复杂度O(n*logn)，最好时间复杂度O(n)
     * 空间复杂度O(N+M)N:代排序数据大小，M:桶个数.
     * 桶排序：用空间换时间.
     * 桶排序是稳定的排序算法。
     */
    public class BucketSort {
    	private int[] bucketSize;// 每个桶的大小
    	private int divisor;// 除数，最接近哈希表大小的质数
    	private int[][] table;// 整个哈希表数组。
    
    	public BucketSort(int d, int size) {
    		divisor = d;
    		bucketSize = new int[size];
    		table = new int[size][];
    		for (int i = 0; i < size; i++) {
    			table[i] = new int[size];
    		}
    	}
    
    	public void insertToTable(int val) {
    		int j = val % divisor;
    		table[j][bucketSize[j]++] = val;
    	}
    
    	public void buildTable(int[] a) {
    		if (a != null) {
    			for (int i = 0; i < a.length; i++) {
    				insertToTable(a[i]);
    			}
    		}
    	}
    
    	public int getTableLen() {
    		return table.length;
    	}
    
    	// 冒泡排序。。。
    	public int[] sort(int[] a) {
    		if (a != null && a.length > 0) {
    			int i, j;
    			for (i = 0; i < a.length - 1; i++) {
    				for (j = 0; j < a.length - i - 1; j++) {
    					if (a[j] >= a[j + 1]) {
    						int tmp = a[j];
    						a[j] = a[j + 1];
    						a[j + 1] = tmp;
    					}
    
    				}
    
    			}
    			return a;
    		}
    		return null;
    
    	}
    
    	// 对整个表排序>
    	public void sortTable() {
    		for (int i = 0; i < table.length; i++) {
    			table[i] = sort(table[i]);
    		}
    	}
    
    	public void prtTable() {
    		for (int i = 0; i < table.length; i++) {
    			if (table[i] != null) {
    				for (int j = 0; j < table[i].length; j++) {
    					if (table[i][j] != 0)
    						System.out.print(table[i][j] + " ");
    				}
    				// System.out.print("\n");
    			}
    
    		}
    		System.out.print("\n");
    	}
    
    	public static void main(String[] args) {
    		int[] a = { 21, 25, 49, 25, 16, 8 };
    		BucketSort bs = new BucketSort(50, 50);
    		bs.buildTable(a);
    		// bs.prtTable();
    		// bs.sort(a);
    		bs.sortTable();
    		bs.prtTable();
    	}
    }

8 16 21 25 25 49