关于建设工程的网站,郑州网站排名优化,网络营销推广目的,免费视频网站推广软件简介#xff1a;计数排序是一个非基于比较的排序算法#xff0c;该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时#xff0c;它的复杂度为Ο(nk)#xff08;其中k是整数的范围#xff09;#xff0c;快于任何比较排序算法。当然这是一种…简介计数排序是一个非基于比较的排序算法该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时它的复杂度为Ο(nk)其中k是整数的范围快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法而且当O(k)O(nlog(n))的时候其效率反而不如基于比较的排序基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序堆排序。
历史攻略
Python基础入门 1 - 230题
Golang基础练习 1 - 40题
算法思想
计数排序对输入的数据有附加的限制条件
1、输入的线性表的元素属于有限偏序集S
2、设输入的线性表的长度为n|S|k表示集合S中元素的总数目为k则kO(n)。
在这两个条件下计数排序的复杂性为O(n)。
计数排序的基本思想是对于给定的输入序列中的每一个元素x确定该序列中值小于x的元素的个数此处并非比较各元素的大小而是通过对元素值的计数和计数值的累加来确定。一旦有了这个信息就可以将x直接存放到最终的输出序列的正确位置上。例如如果输入序列中只有17个元素的值小于x的值则x可以直接存放在输出序列的第18个位置上。当然如果有多个元素具有相同的值时我们不能将这些元素放在输出序列的同一个位置上因此上述方案还要作适当的修改。
Python语言描述
def count_sort(input_list):length len(input_list)if length 2:return input_listmax_num max(input_list)count [0] * (max_num 1)for element in input_list:count[element] 1output_list []for i in range(max_num 1):for j in range(count[i]): # count[i]表示元素i出现的次数如果有多次通过循环重复追加 output_list.append(i)return output_list案例源码5题
# -*- coding: utf-8 -*-
# time: 2023/12/17 10:18
# file: count_sort_demo.py
# 公众号: 玩转测试开发from typing import List# 1051. 高度检查器
# 学校打算为全体学生拍一张年度纪念照。根据要求学生需要按照非递减的高度顺序排成一行。
# 排序后的高度情况用整数数组expected表示其中expected[i]是预计排在这一行中第i位的学生的高度下标从0开始。
# 给你一个整数数组heights 表示当前学生站位的高度情况。heights[i]是这一行中第i位学生的高度下标从0开始。
# 返回满足heights[i] ! expected[i]的下标数量 。
#
# 示例1输入heights [1, 1, 4, 2, 1, 3]
# 输出3
# 解释
# 高度[1, 1, 4, 2, 1, 3]
# 预期[1, 1, 1, 2, 3, 4]
# 下标
# 2 、4 、5
# 处的学生高度不匹配。
# 示例2
# 输入heights [5, 1, 2, 3, 4]
# 输出5
# 解释
# 高度[5, 1, 2, 3, 4]
# 预期[1, 2, 3, 4, 5]
# 所有下标的对应学生高度都不匹配。
# 示例3
# 输入heights [1, 2, 3, 4, 5]
# 输出0
# 解释
# 高度[1, 2, 3, 4, 5]
# 预期[1, 2, 3, 4, 5]
# 所有下标的对应学生高度都匹配。class Solution1051:def heightChecker(self, heights: List[int]) - int:# 先赋值给其他# 排序本身# 遍历对比n heights[:]heights.sort()count 0for i, v in enumerate(n):if v ! heights[i]:count 1return counts1051 Solution1051()
r1051 s1051.heightChecker([1, 1, 4, 2, 1, 3])
print(fr1051:{r1051}) # r1051:3# 561. 数组拆分
# 给定长度为 2n 的整数数组 nums 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn)
# 使得从 1 到 n 的 min(ai, bi) 总和最大。
# 返回该 最大总和 。
# 示例 1
# 输入nums [1,4,3,2]
# 输出4
# 解释所有可能的分法忽略元素顺序为
# 1. (1, 4), (2, 3) - min(1, 4) min(2, 3) 1 2 3
# 2. (1, 3), (2, 4) - min(1, 3) min(2, 4) 1 2 3
# 3. (1, 2), (3, 4) - min(1, 2) min(3, 4) 1 3 4
# 所以最大总和为 4
# 示例 2
# 输入nums [6,2,6,5,1,2]
# 输出9
# 解释最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) min(2, 5) min(6, 6) 1 2 6 9class Solution561:def arrayPairSum(self, nums: List[int]) - int:# 排序。一次22取。排序后双数位为最小。隔取求和nums.sort()count int(len(nums) / 2)return sum([i for i in nums[0::2]])s561 Solution561()
r561 s561.arrayPairSum([1, 1, 4, 2, 1, 3])
print(fr561:{r561}) # r561:5# 1122. 数组的相对排序
# 给你两个数组arr1 和 arr2arr2 中的元素各不相同arr2 中的每个元素都出现在 arr1 中。
# 对 arr1 中的元素进行排序使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。
# 未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
# 示例 1
# 输入arr1 [2,3,1,3,2,4,6,7,9,2,19], arr2 [2,1,4,3,9,6]
# 输出[2,2,2,1,4,3,3,9,6,7,19]
# 示例 2:
# 输入arr1 [28,6,22,8,44,17], arr2 [22,28,8,6]
# 输出[22,28,8,6,17,44]class Solution1122:def relativeSortArray(self, arr1: List[int], arr2: List[int]) - List[int]:# 字典arr1的元素和个数# 遍历arr2,将符合的全部加入结果列表。加入后移除字典中对应的键值对。# 遍历字典。将剩余的值重新排序并入结果列表import collectionstmp_dict dict(collections.Counter(arr1))result []for i in arr2:if i in tmp_dict:loop tmp_dict[i]for count in range(loop):result.append(i)tmp_dict.pop(i)others [k for k, v in tmp_dict.items() for i in range(v)]others.sort()return result otherss1122 Solution1122()
r1122 s1122.relativeSortArray([2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19], [2, 1, 4, 3, 9, 6])
print(fr1122:{r1122}) # r1122:[2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]# 912. 排序数组
# 给你一个整数数组 nums请你将该数组升序排列。
# 示例 1
# 输入nums [5,2,3,1]
# 输出[1,2,3,5]
# 示例 2
# 输入nums [5,1,1,2,0,0]
# 输出[0,0,1,1,2,5]class Solution912:def sortArray(self, nums: List[int]) - List[int]:return sorted(nums)s912 Solution912()
r912 s912.sortArray([2, 1, 4, 3, 9, 6])
print(fr912:{r912}) # r912:[1, 2, 3, 4, 6, 9]# 274. H 指数
# 给你一个整数数组 citations 其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
# 根据维基百科上 h 指数的定义h 代表“高引用次数” 一名科研人员的 h 指数 是指他她至少发表了 h 篇论文
# 并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值h 指数 是其中最大的那个。
# 示例 1
# 输入citations [3,0,6,1,5]
# 输出3
# 解释给定数组表示研究者总共有 5 篇论文每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
# 由于研究者有 3 篇论文每篇 至少 被引用了 3 次其余两篇论文每篇被引用 不多于 3 次所以她的 h 指数是 3。
# 示例 2
# 输入citations [1,3,1]
# 输出1class Solution274:def hIndex(self, citations: List[int]) - int:loop len(citations)if sum(citations) 0:return 0if loop 1:return 1for i in range(loop, 0, -1):if sum([1 for j in citations if j i]) i:return is274 Solution274()
r274 s274.hIndex([2, 1, 4, 3, 9, 6])
print(fr274:{r274}) # r274:3运行结果
r1051:3
r561:5
r1122:[2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]
r912:[1, 2, 3, 4, 6, 9]
r274:3总结计数排序算法没有用到元素间的比较它利用元素的实际值来确定它们在输出数组中的位置。因此计数排序算法不是一个基于比较的排序算法从而它的计算时间下界不再是O(nlogn)。另一方面计数排序算法之所以能取得线性计算时间的上界是因为对元素的取值范围作了一定限制即kO(n)。如果kn2,n3,…就得不到线性时间的上界。此外我们还看到由于算法第4行使用了downto语句经计数排序输出序列中值相同的元素之间的相对次序与他们在输入序列中的相对次序相同换句话说计数排序算法是一个稳定的排序算法。
