计数排序算法原理简介

前言

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

概念介绍

  • 计数排序算法是一个非基于比较的排序算法,故在排序的过程中不存在元素之间的比较和交换操作
  • 计数排序算法是一种以空间换取时间的做法,所以在一定范围内的整数排序时,它是快于任何比较排序算法

原理讲解

我们以[1 7 8 7 9 8 10 4]这个序列为例说明计数排序算法的实现原理

  1. 当未开始排序时,效果如下图

    在这里插入图片描述

  2. 先找到待排序序列中最大值10和最小值1,此时效果如下图

    在这里插入图片描述

  3. 新建一个长度为N=最大值10-最小值1+1=10的数组,新数组中值中值均为0,此时效果如下图

    在这里插入图片描述

  4. 开始遍历待排序的序列,第一个元素为1,故将值为1的元素放到新数组位置为1的地方,其值为元素1在原序列中出现的次数1次。此时效果如下图

    在这里插入图片描述

  5. 继续遍历,第二个元素为7,故将值为7的元素放到新数组位置为7的地方,其值为元素7在原序列中出现的次数1次。此时效果如下图

    在这里插入图片描述

  6. 继续遍历,第三个元素为8,故将值为8的元素放到新数组位置为8的地方,其值为元素8在原序列中出现的次数1次。此时效果如下图

    在这里插入图片描述

  7. 继续遍历,第四个元素为7,故将值为7的元素放到新数组位置为7的地方,其值为元素7在原序列中出现的次数第2次。此时效果如下图

    在这里插入图片描述

  8. 继续遍历,第五个元素为9,故将值为9的元素放到新数组位置为9的地方,其值为元素9在原序列中出现的次数1次。此时效果如下图

    在这里插入图片描述

  9. 继续遍历,第六个元素为8,故将值为8的元素放到新数组位置为8的地方,其值为元素8在原序列中出现的次数第2次。此时效果如下图

    在这里插入图片描述

  10. 继续遍历,第七个元素为10,故将值为10的元素放到新数组位置为10的地方,其值为元素10在原序列中出现的次数1次。此时效果如下图

    在这里插入图片描述

  11. 继续遍历,第八个元素为4,故将值为4的元素放到新数组位置为4的地方,其值为元素4在原序列中出现的次数1次。此时效果如下图

    在这里插入图片描述

  12. 至此,整个待排序数组遍历完毕,此时效果如下图

    在这里插入图片描述

    新数组中的每一个值,代表了其下标在待排序数组中出现的次数。

  13. 最后,我们遍历新数组,输出新数组元素的下标值,对应下标的值是几就输出几次。此时效果如下图

    在这里插入图片描述

时间复杂度

  • 计数排序的时间复杂度为O(n+k)。其中n为待排序元素个数,k为待排序元素最大值

空间复杂度

  • 计数排序的空间复杂度为n+O(k)。其中n为待排序元素个数,k为待排序元素最大值

算法优缺点

  • 优点:速度快
  • 缺点:

    • 需要提前知道待排序元素最大值
    • 需要大量内存消耗

效果展示

在这里插入图片描述

以上是 计数排序算法原理简介 的全部内容, 来源链接: utcz.com/a/25014.html

回到顶部