10大排序算法.png
基数排序非常适合用于整数排序，尤其是正整数
复杂度：
最好、最坏、平均时间复杂度：O(d*(n+k)),d是最大值得位数，k是进制
空间复杂度：O(n+k) ,k是进制
稳定性：稳定排序执行流程：
依次对个位数、十位数、百位数、千位数...进行排序(从低位到高位)
基数排序.png
private void sort(){
//找出最大值
int max = list[0];
for(int i = 1; i < list.length;i++) {
if(list[i] > max ) {
max = list[I];
}
}
/**
x /1% 10得到个位数 x/10%10得到十位数 x/100%10得到百位数
个位数： 593 / 1 % 10 = 3
十位数： 593 / 10 % 10 = 9
百位数: 593 / 100 % 10 = 5
*/
//排序
for(int divider = 1; divider <= max; divider *=10) {
countingSort(divider);
}
}
//对个 、十、 百、 千...位进行排序, 统计0 ~ 9出现的次数
private void countingSort(int divider) {
//1.开辟内存空间，存储次数
int counts = new int[10];
//2.1统计每个整数出现的次数
for(int i = 0;i < list.length;i++) {
int idx = list[i]/divider%10;
counts[idx]++;
}
//2.2累加次数，每遍历一位就拿前一位的次数加当前元素出现次数
for(int i = 1;i < counts.length;i++) {
counts[i] = counts[i] + counts[i-1];
}
//3.从后往前遍历元素，将它放在有序序列中的合适位置
//技巧：从后往前遍历可以保证稳定性，相同数字相对位置不变
int[] output = new int[list.length];
for(int i = array.length - 1; i >=0;i--) {
//array[i] : list数组i位置的元素在counts数组中的索引
//counts[list[i]]: 索引位存储的次数
//--(counts[list[i]]): 索引位存储的次数减1后再把得到的值存起来, 这个减1后得到的值就是 list数组i位置的元素将来在有序序列中的索引
int idx = --(counts[list[i]/divider%10]);
// 将元素放在有序序列中的合适位置
output[idx] = list[I];
}
//4.将排好序的数组覆盖掉array
for(int i = 0;i < list.length;i++) {
list[i] = output[I];
}
基数排序-另一种思路
执行流程：
- 创建一个二维数组list，list中添加10个数组(因为基数范围是[0,9])，这10个数组的长度最好是原数组的长度
2.遍历原数组获取其中元素的个、十、百、千位数值，按顺序([0,9])存储到list中
3.遍历list获取每个数组中的元素放进原数组中就得到了有序序列
基数排序-另一种思路.png
时间复杂度：O(dn)
空间复杂度：O(kn+k)
d: 最大值的位数
k: 进制
private void sort() {
//1.寻找最大值
int max = list[0];
for(int i = 1;i < list.length;i++) {
if(array[I] > max) {
max = list[I];
}
}
//2.排序
//桶数组
int[][] buckets = new int[10][list.length];
//每个桶元素的数量
int bucketSizes = new int[buckets.length];
for(int divider = 1;divider <= max; divider *10) {
//2.1.将数组元素放到对应的桶里面去
for(int i = 0;i < list.length;i++) {
int no = list[i]/divider%10;
buckets[no][bucketSizes[no]++] = list[i];
}
//2.2.从桶里面取出元素放进原数组
int idx = 0;
for(int i = 0;i < buckets.length;i++) {
for(int j = 0;j < bucketSizes[I];j++) {
list[idx++] = buckets[i][j];
}
bucketSizes[i] = 0;
}
}
}
