三大线性排序之基数排序
添加时间:2013-7-25 点击量:
一.概念
基数排序也不是基于斗劲和元素移位的，又称桶子法；数据布局教材上起首由扑克牌的排序引入，继而引出多关键字斗劲。
本文是基于计数排序的基数排序，只介绍最低位优先（Least Significant Digit First），谷歌之发明就几乎没有介绍MSD的，所谓LSD就是从数字的最低位逐个斗劲，斗劲的趟数就是最大数字的位数digit，是以须要先用countDigit办法求出位数digit。
局限性：本算法是稳定的，LSD须要应用稳定的算法，因为按位斗劲，是以须要整数，和计数排序不合的是，整数可所以负数，也可以很大，为什么呢？
- 数值较大：因为是按斗劲，统计数字呈现次数时只须要开c[10]就好， 因为就0到9共10个数字。
- 负数：若是有正有负怎么办呢？这个是写的时辰想起来的，不过我立马想到懂得决办法，请各位看官想想，看和我的是否一样：把正负数分隔存入两个数组，负数数组先去掉负号按正数进行由大到小的基数排序，输出的时辰加上负号正序输出；正数数组就直接由小到大排序，然后正序输出，不知各位把守和我想的是否一致。
二.算法描述
有的读者会问为什么LSD须要稳定的排序办法呢？下面就笔者的一点见地略作商量……我刚开端也困惑，困惑的原因在于本来计数排序是直接斗劲数值不是每一位数字，如今斗劲每位数字，如许就把每个数拆分了，若是不稳定排序，则可能下一次排序就把上一次的打乱了。再来说下稳定，有同窗问若是每个数都不雷同是否就不涉及稳定的题目呢？熟悉打听上方解析的读者会立即答复否，因为是按数字斗劲的，而数字只有0到9，必然有雷同的。
如上图，经过个位斗劲后345必然在242后边（因为5>2），实际也确切应当如许，因为二者的十位数字都是4，若是十位排序是不稳定排序，则很可能下一次345就排在242前边了，很明显就错了。
三.算法Java实现
import java.util.Arrays;
public class RadixSort {
//基于计数排序的基数排序算法
public static void radixSort（int[] array，int radix， int digit） {
//array为待排序数组
//radix，代表基数，实际就是几个数字，那就是10喽
//digit代表排序元素的位数，实际意义是排序趟数
int length = array.length;
int[] res = new int[length];
int[] c = new int[radix];//radix就是10，因为0到9共10个数字
int divide = 1;//用于每次把数字缩小10倍
for （int i = 0; i < digit; i++） {
res = Arrays.copyOf（array， length）;
Arrays.fill（c， 0）;
for （int j = 0; j < length; j++） {
int tempKey = （res[j]/divide）％radix;
c[tempKey]++;
}
for （int j = 1; j < radix; j++） {
c [j] = c[j] + c[j-1];
}
for （int j=length-1; j>=0; j--） {
int tempKey = （res[j]/divide）％radix;
array[c[tempKey]-1] = res[j];
c[tempKey]--;
}
divide = divide radix;
}
}
public static int countDigit（int[] array） {
int max = array[0];
for （int i = 1; i < array.length; i++） {
if （array[i] > max） {
max = array[i];
}
}
int time = 0;
while （max > 0） {
max /= 10;
time++;
}
return time;
}
public static void main（String[] args） {
int[] array = {3，2，3，2，5，333，45566，2345678，78，990，12，432，56};
int time = countDigit（array）;
//System.out.println（time）;
radixSort（array，10，time）;
for （int i = 0; i < array.length; i++） {
System.out.print（ + array[i]）;
}
}
}
彼此相爱，却不要让爱成了束缚：不如让它成为涌动的大海，两岸乃是你们的灵魂。互斟满杯，却不要同饮一杯。相赠面包，却不要共食一个。一起歌舞欢喜，却依然各自独立，相互交心，却不是让对方收藏。因为唯有生命之手，方能收容你们的心。站在一起却不要过于靠近。—— 纪伯伦《先知》
彼此相爱，却不要让爱成了束缚：不如让它成为涌动的大海，两岸乃是你们的灵魂。互斟满杯，却不要同饮一杯。相赠面包，却不要共食一个。一起歌舞欢喜，却依然各自独立，相互交心，却不是让对方收藏。因为唯有生命之手，方能收容你们的心。站在一起却不要过于靠近。—— 纪伯伦《先知》一.概念
基数排序也不是基于斗劲和元素移位的，又称桶子法；数据布局教材上起首由扑克牌的排序引入，继而引出多关键字斗劲。
本文是基于计数排序的基数排序，只介绍最低位优先（Least Significant Digit First），谷歌之发明就几乎没有介绍MSD的，所谓LSD就是从数字的最低位逐个斗劲，斗劲的趟数就是最大数字的位数digit，是以须要先用countDigit办法求出位数digit。
局限性：本算法是稳定的，LSD须要应用稳定的算法，因为按位斗劲，是以须要整数，和计数排序不合的是，整数可所以负数，也可以很大，为什么呢？
- 数值较大：因为是按斗劲，统计数字呈现次数时只须要开c[10]就好， 因为就0到9共10个数字。
- 负数：若是有正有负怎么办呢？这个是写的时辰想起来的，不过我立马想到懂得决办法，请各位看官想想，看和我的是否一样：把正负数分隔存入两个数组，负数数组先去掉负号按正数进行由大到小的基数排序，输出的时辰加上负号正序输出；正数数组就直接由小到大排序，然后正序输出，不知各位把守和我想的是否一致。
二.算法描述
有的读者会问为什么LSD须要稳定的排序办法呢？下面就笔者的一点见地略作商量……我刚开端也困惑，困惑的原因在于本来计数排序是直接斗劲数值不是每一位数字，如今斗劲每位数字，如许就把每个数拆分了，若是不稳定排序，则可能下一次排序就把上一次的打乱了。再来说下稳定，有同窗问若是每个数都不雷同是否就不涉及稳定的题目呢？熟悉打听上方解析的读者会立即答复否，因为是按数字斗劲的，而数字只有0到9，必然有雷同的。
如上图，经过个位斗劲后345必然在242后边（因为5>2），实际也确切应当如许，因为二者的十位数字都是4，若是十位排序是不稳定排序，则很可能下一次345就排在242前边了，很明显就错了。
三.算法Java实现
import java.util.Arrays;
public class RadixSort {
//基于计数排序的基数排序算法
public static void radixSort（int[] array，int radix， int digit） {
//array为待排序数组
//radix，代表基数，实际就是几个数字，那就是10喽
//digit代表排序元素的位数，实际意义是排序趟数
int length = array.length;
int[] res = new int[length];
int[] c = new int[radix];//radix就是10，因为0到9共10个数字
int divide = 1;//用于每次把数字缩小10倍
for （int i = 0; i < digit; i++） {
res = Arrays.copyOf（array， length）;
Arrays.fill（c， 0）;
for （int j = 0; j < length; j++） {
int tempKey = （res[j]/divide）％radix;
c[tempKey]++;
}
for （int j = 1; j < radix; j++） {
c [j] = c[j] + c[j-1];
}
for （int j=length-1; j>=0; j--） {
int tempKey = （res[j]/divide）％radix;
array[c[tempKey]-1] = res[j];
c[tempKey]--;
}
divide = divide radix;
}
}
public static int countDigit（int[] array） {
int max = array[0];
for （int i = 1; i < array.length; i++） {
if （array[i] > max） {
max = array[i];
}
}
int time = 0;
while （max > 0） {
max /= 10;
time++;
}
return time;
}
public static void main（String[] args） {
int[] array = {3，2，3，2，5，333，45566，2345678，78，990，12，432，56};
int time = countDigit（array）;
//System.out.println（time）;
radixSort（array，10，time）;
for （int i = 0; i < array.length; i++） {
System.out.print（ + array[i]）;
}
}
}
