4-基数排序
算法思想:
基数排序的实现步骤非常好理解,但是想要真正理解他的算法思想就稍微有点难度了.那么接下来就来讲解基数排序的算法思想.
首先基数排序是根据数位来进行排序的.他是从个位开始,然后按照每一位的数进行排序,如下图所示:
排完序之后就往前进一位,然后再将所有的数按照这一位所在的数进行排序,如下图所示:
重复这个过程直到所有的位数都已经被排过序了.如下图所示:
并且如果这个过程中碰到某个数在这个为上没有数的话就进行补零操作,将该位看成是0.就比方下图我用红框圈出来的部分:
等到所有的位数都已经排序完毕之后,我们就可以看到我们已经排序好的序列了.
这个过程相信大家肯定都很好理解,但是相信大家如果是第一次看这个算法的肯定会有和我当初一样的困惑,那就是为什么基数排序选择的是从低位到高位来进行排序的呢,而不是像我们平常比较数据的大小一样,从高位到低位来比较呢?
这里呢我们先不讲为什么,我们先看下面这两个案例:
从高位到低位进行比较
- 从低位到高位进行比较
对比看了上面两个例子之后相信大家就知道了,很明显我们看到如果是从该我到低位来进行比较的话,我们会发现比较到最后之后序列仍然是无序的,但是从低位到高位进行比较的话,我们就会发现序列到最后已经排好序了.
是不是很奇怪,同样的执行过程,只不过执行的顺序发生了改变,为什么结果就回产生这样的结果呢?产生这个差异的重点就是在我们忽略了一个问题,那就是我们在进行高位到低位比较的时候,高位的权重是高于低位的.就比方下图所示:
正是因为这个原因,所以我们采取的是从低位到高位比较的过程.
说完基本思想之后,我们来说一下算法的实现步骤:
1.我们第一次遍历序列.找出序列中的最大值MAX,找到MAX之后我们可以确定我们需要比较多少数位了.
2.这时候我们就需要按照元素在该位数对应的数字将元素存入到相应的容器之中.如下图所示:
3.之后我们再按照容器的顺序将元素重新弹出构成我们接下来需要排序的序列,如下图所示:
这个从容器弹出的过程需要注意一点,那就是遵循先进先出的原则,所以这个容器选择队列或者是链表比较合适,不能选择栈,因为栈是先进后出,拿取元素的时候回非常麻烦.
4.最后只需要重复2,3步骤,直到最高位也比较完毕,那么整个基数排序就已经完成了.
接下来我们还是通过下面的图来动态演示一下基数排序的过程:
个位排序:
十位排序:
百位排序:
千位排序:
在了解完基数排序的基本思想之后,按照惯例我们还是来简单分析一下基数排序的特点:
基数排序是稳定的,原因和桶排序以及计数排序的原因一样.
算法图解:
示例代码:
//将所有的数组合并成原来的数组 public static void merge(ArrayList<Integer> list[],int num[]) { int k=0; for(int i=0;i<list.length;i++) { if(list[i]!=null) { for(int j=0;j<list[i].size();j++) { num[k++]=list[i].get(j); System.out.print(num[k-1]+" "); } } //合并完成之后需要将链表清空,否则元素会越来越多 list[i].clear(); } System.out.println(); } //将所有的元素分散到各个链表之中 public static void split(ArrayList<Integer> list[],int num[],int k) { for(int j=0;j<num.length;j++) { list[num[j]/k%10].add(num[j]); } System.out.println("-----------------------------------------------------------------------"); System.out.println("个位开始数,第"+(String.valueOf(k).length())+"位排序结果:"); for(int j=0;j<10;j++) { System.out.println((String.valueOf(k).length())+"号位,数值为"+j+"的链表结果:"+list[j]); } } public static void main(String[] args) { ArrayList<Integer>list[]=new ArrayList [10]; for(int i=0;i<10;i++) { list[i]=new ArrayList<Integer>(); } int []num ={7,14,9,333,201,1,88,6,57,10,56,74,36,234,456}; long startTime=System.currentTimeMillis(); int max=Integer.MIN_VALUE; //第一次遍历获得序列中的最大值 for(int i=0;i<num.length;i++) { if(num[i]>max) max=num[i]; } int k=1; for(int i=0;i<String.valueOf(max).length();i++) { split(list, num, k); System.out.println("第"+(i+1)+"次排序"); merge(list, num); k=k*10; } long endTime=System.currentTimeMillis(); System.out.println("程序运行时间： "+(endTime-startTime)+"ms"); }
复杂度分析:
理解完基数排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.
时间复杂度
看完我们上面的动图演示之后我们可以看到基数排序只需要根据最大元素的位数,遍历相应次数的序列即可,所以我们可以确定基数排序的时间复杂度一定是线性级别的,但是虽然是线性级别的,但是有一个系数的,这个系数就是最大元素的位数K,所以时间复杂度应该是O(n*k)
空间复杂度
空间复杂度我们也可以看出来,主要就是取决于链表的数量以及序列元素的数量,所以空间复杂度为O(n+k)
