计数排序

#计数排序

  • 前提：
  • 1.待排序元素的关键字是整数型
  • 2.元素的取值范围是\[0,k)
  • 流程：
  • 1.创建一个长度为k的辅助数组，统计每个元素的出现次数（辅助数组的下标对应原数组的每个元素值）
  • 2.对辅助数组进行处理，处理如下：设当前元素num下标为i,则num等于下标从0到i所有元素和，也就是前缀和 PS：你应该明白前缀和这个概念，不知道也得直到，白费我口舌在这解释
  • 3.利用辅助数组对原数组进行排序：
  • 先整一个和原数组等长的副数组
  • 从后往前遍历原数组
  • 设原数组yuan\[],辅助数组zhu\[],副数组fu\[]
  • 指向原数组的尾指针k
  • 那么fu\[zhu\[yuan\[k]]-1]=yuan\[k]
  • 这样的结果，即将原数组中的元素放置到副数组中已经排序完成的位置，此外，辅助数组里的zhu\[yuan\[k]]-1,是要作用到辅助数组的对应元素里的
  • 啧，我觉得我这样的口述很难让人信服

    • #计数排序算法实现

  • 看不懂我口述的可以看图，Bro

    • Pasted image 20260614170307.png

    ==时间复杂度=O(n+k)==

    ==空间复杂度=O(n+k)==