十大经典排序算法详解(三)-堆排序,计数排序,桶排序,基数排序(四)

简介: 十大经典排序算法详解(三)-堆排序,计数排序,桶排序,基数排序

4-基数排序


算法思想:


基数排序的实现步骤非常好理解,但是想要真正理解他的算法思想就稍微有点难度了.那么接下来就来讲解基数排序的算法思想.


首先基数排序是根据数位来进行排序的.他是从个位开始,然后按照每一位的数进行排序,如下图所示:


2021020209431997.png


排完序之后就往前进一位,然后再将所有的数按照这一位所在的数进行排序,如下图所示:


20210202094438123.png


重复这个过程直到所有的位数都已经被排过序了.如下图所示:


20210202094543584.png


并且如果这个过程中碰到某个数在这个为上没有数的话就进行补零操作,将该位看成是0.就比方下图我用红框圈出来的部分:


2021020209463992.png


等到所有的位数都已经排序完毕之后,我们就可以看到我们已经排序好的序列了.


这个过程相信大家肯定都很好理解,但是相信大家如果是第一次看这个算法的肯定会有和我当初一样的困惑,那就是为什么基数排序选择的是从低位到高位来进行排序的呢,而不是像我们平常比较数据的大小一样,从高位到低位来比较呢?


这里呢我们先不讲为什么,我们先看下面这两个案例:


从高位到低位进行比较


image.png


  • 从低位到高位进行比较


image.png


对比看了上面两个例子之后相信大家就知道了,很明显我们看到如果是从该我到低位来进行比较的话,我们会发现比较到最后之后序列仍然是无序的,但是从低位到高位进行比较的话,我们就会发现序列到最后已经排好序了.


是不是很奇怪,同样的执行过程,只不过执行的顺序发生了改变,为什么结果就回产生这样的结果呢?产生这个差异的重点就是在我们忽略了一个问题,那就是我们在进行高位到低位比较的时候,高位的权重是高于低位的.就比方下图所示:


20210202100713717.png


正是因为这个原因,所以我们采取的是从低位到高位比较的过程.


说完基本思想之后,我们来说一下算法的实现步骤:


1.我们第一次遍历序列.找出序列中的最大值MAX,找到MAX之后我们可以确定我们需要比较多少数位了.


2.这时候我们就需要按照元素在该位数对应的数字将元素存入到相应的容器之中.如下图所示:


20210202102718980.png


3.之后我们再按照容器的顺序将元素重新弹出构成我们接下来需要排序的序列,如下图所示:


20210202104039532.png


这个从容器弹出的过程需要注意一点,那就是遵循先进先出的原则,所以这个容器选择队列或者是链表比较合适,不能选择栈,因为栈是先进后出,拿取元素的时候回非常麻烦.


4.最后只需要重复2,3步骤,直到最高位也比较完毕,那么整个基数排序就已经完成了.


接下来我们还是通过下面的图来动态演示一下基数排序的过程:

个位排序:


20210202104801736.png


十位排序:


20210202104824284.png


百位排序:


20210202104908836.png


千位排序:


20210202104957210.png


在了解完基数排序的基本思想之后,按照惯例我们还是来简单分析一下基数排序的特点:


基数排序是稳定的,原因和桶排序以及计数排序的原因一样.

算法图解:


20210119162003373.gif


示例代码:

//将所有的数组合并成原来的数组
  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"); 
  }


2021012915062720.png

复杂度分析:


理解完基数排序的基本思想之后,我们就需要来分析一下他的时间复杂度,空间复杂度.


时间复杂度


看完我们上面的动图演示之后我们可以看到基数排序只需要根据最大元素的位数,遍历相应次数的序列即可,所以我们可以确定基数排序的时间复杂度一定是线性级别的,但是虽然是线性级别的,但是有一个系数的,这个系数就是最大元素的位数K,所以时间复杂度应该是O(n*k)


空间复杂度


空间复杂度我们也可以看出来,主要就是取决于链表的数量以及序列元素的数量,所以空间复杂度为O(n+k)


相关文章
|
2月前
|
算法 搜索推荐
数据结构与算法学习十八:堆排序
这篇文章介绍了堆排序是一种通过构建堆数据结构来实现的高效排序算法,具有平均和最坏时间复杂度为O(nlogn)的特点。
74 0
数据结构与算法学习十八:堆排序
|
2月前
|
算法 搜索推荐 Java
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
28 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
|
2月前
|
搜索推荐 Java Go
深入了解计数排序算法
深入了解计数排序算法
35 4
|
2月前
|
算法 搜索推荐
算法之堆排序
本文介绍了堆排序算法的原理和实现,通过构建最大堆或最小堆,利用堆的性质进行高效的排序,并提供了具体的编程实现细节和示例。
24 0
算法之堆排序
|
2月前
|
搜索推荐 Java Go
深入了解基数排序算法
深入了解基数排序算法
31 3
|
2月前
|
搜索推荐 Java Go
探究桶排序算法
探究桶排序算法
24 1
|
2月前
|
算法 Java Go
深入了解堆排序算法
深入了解堆排序算法
28 1
|
2月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
17 0
|
4月前
|
存储 搜索推荐 算法
Python中的桶排序算法
总结而言,桶排序是一个非常高效的排序算法,尤其适用于数据分布均匀的情况。正确实现和使用桶排序可以在特定情况下获得极高的排序速度。
22 0
|
5月前
|
算法 搜索推荐 C#