算法基础之排序算法九之基数排序

Posted by Naah on Saturday, Sep 09,2017 09:31:05
目录 x

基数排序

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序

算法复杂度:O (nlog®m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。稳定

算法思想: 1. 取得最大数的位数有多少,建立二维数组 2. 循环位数次,每次通过位数进行筛选,结束后按0-9顺序,进行输出 a. 当进行十位数筛选时,由于个位数十位为0,所以都在0的二维中,所以输出时先输出0,所以进行排序,高位依然如此

针对负数以及小数: 1. 针对负数,所有数字加一最小负数的绝对值,排序完成后再减掉 2. 针对小数,所有数字乘以10的小数位次方,排序完成后再除掉

import java.util.ArrayList;

/**
 * 基数排序
 * @author Naah
 *
 */
public class BasicSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] array= {2,2,4,66,56,32,3,34,54,22,67,77,23,5353,3444,55,6,77,88};
		BasicSort sort=new BasicSort();
		sort.basicSort(array);
		for (int i : array) {
			System.out.println(i);
		}
	}
/**
 * 基数排序算法
 * 通过数字的位数进行排序
 * @param array 数组
 */
	public void basicSort(int[] array) {
		//最大值变量
		 int max=0;

		 //获取最大值
		 for (int i = 0; i < array.length; i++) {
			if (array[i]>max) {
				max=array[i];
			}
		}

		 //最大值位数
		 int bits=0;

		 //遍历获取最大值位数
		 while (max>0) {
			bits++;
			max/=10;
		}

		 //创建基数二维数组
		 ArrayList<ArrayList> list=new ArrayList<ArrayList>();

		 //每位数都是0-9,所以一共添加10个ArrayList到list中
		 for (int i = 0; i < 10; i++) {
			list.add(new ArrayList<Integer>());
		}


		 //每位循环一次
		 for (int i = 0; i < bits; i++) {

			 //每次循环一边数组,进行数组排列
			for (int j = 0; j < array.length; j++) {

				//取得该位的数字,(先用大一位取余,然后再取整)
				//i=0,取个位,i=1,取十位,i=2,取百位
				int x=(int) (array[j]%Math.pow(10, i+1)/Math.pow(10, i));

				//取出位数对应的数组
				ArrayList<Integer> eleList=list.get(x);

				//将该数添加到该数组
				eleList.add(array[j]);
			}

			//将排列后的数组进行归并

			//数组引用
			int count=0;

			//循环所有位数
			for (int j = 0; j < 10; j++) {

				//当位数组有值时,循环
				while (list.get(j).size()>0) {

					///取出该位数组
					ArrayList<Integer> eleList=list.get(j);

					//将位数组第一个数填入数组中
					array[count++]=eleList.get(0);

					//移除位数组中第一个值/
					eleList.remove(0);

				}
			}

		}
	}

}