空间怎么上传网站,花都网站制作,微信分销小程序,如何注册互联网服务平台排序算法1-CSDN博客 排序算法1中提及的是较为基础(暴力实现#xff0c;复杂度较高)的排序算法#xff0c;不适合于数据量较大的场景#xff0c;比如序列长度达到1e5 接下来以蓝桥另一道题目来理解其它的排序算法 蓝桥3226 蓝桥账户中心 样例 5 1 5 9 3 7 4、快速排序 快速排… 排序算法1-CSDN博客 排序算法1中提及的是较为基础(暴力实现复杂度较高)的排序算法不适合于数据量较大的场景比如序列长度达到1e5 接下来以蓝桥另一道题目来理解其它的排序算法 蓝桥3226 蓝桥账户中心 样例 5 1 5 9 3 7 4、快速排序 快速排序是一种高效的排序算法采用分治法Divide and Conquer(二分思想)策略来对一个序列进行排序。 快速排序的最坏运行情况是 O(n²)比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)且 O(nlogn) 记号中隐含的常数因子很小比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以对绝大多数顺序性较弱的随机数列而言快速排序总是优于归并排序。 算法步骤 1. 从数列中挑出一个元素称为 “基准”pivot一般选择乱序数组的第一个元素; 2. 重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。 3.在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作。值得注意的是从每次‘分区’的过程中看除了筛选相较于‘基准值’小或者大的数以外不做额外的排序 4.递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序递归的最底部情形是数列的大小是零或一也就是永远都已经被排序好了。 从递归的性质看递归的结构特点是基于栈的计算顺序满足‘后进先出’也就是输入乱序数组后会每一轮选出一个基准值然后筛选相较于‘基准值’小或者大的数小的放入左边序列大的放入右边序列之后递归处理这两个序列基准值在本轮后都不再进入排序过程中因为本轮结束后基准值的位置是正确的后面就是一直递归到两边的排序数组长度都为1又每一轮都有一个基准值被选出排序的序列迭代地完成了排序。 # li[left,right]按照小于等于(等于基准值的元素放在左边或者右边都可以)基准值、基准值、大于等于基准值
# 定义一个函数返回每一轮筛选的基准值下标
def num_partition(li,left,right):# left为每一轮基准值的初始化下标# 放置 小于等于 基准值元素的下标idx left1# 除选出的序列第一个元素作为基准值遍历当前序列剩下的元素for i in range(left1,right1):if li[i] li[left]:# 放左边li[idx],li[i] li[i],li[idx]# 本轮基准值下标后移1idx 1# 小于等于本轮基准值的元素为li[left1,idx-1]上述设定小于等于都放左边li[left],li[idx-1] li[idx-1],li[left]return idx-1# 基于定义好的返回每轮基准值下标的函数实现快速排序
def quick_sort(li,left,right):# print(li)# left right时排序完成if left right:# 选本轮基准值mid num_partition(li,left,right)# 基于 二分 的思想# 递归左边quick_sort(li,left,mid-1)# 递归右边quick_sort(li,mid1,right)n int(input())
li list(map(int,input().split()))
quick_sort(li,0,n-1) # n-1:len(li)-1
print( .join(map(str,li))) 5、归并排序 归并排序Merge Sort是一种基于分治法的比较排序算法其基本思想是将数组分成两个子数组分别对这两个子数组进行排序然后将它们合并成一个有序数组。归并排序在时间复杂度和稳定性方面表现优异。归并排序的实现由两种方法 自上而下的递归所有递归的方法都可以用迭代重写所以就有了第 2 种方法自下而上的递归 和选择排序一样归并排序的性能不受输入数据的影响但表现比选择排序好的多因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。 算法步骤 1.申请空间使其大小为两个已经排序序列之和该空间用来存放合并后的序列 2.设定两个指针最初位置分别为两个已经排序序列的起始位置 3.比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置 4.重复步骤 3 直到某一指针达到序列尾 5.将另一序列剩下的所有元素直接复制到合并序列尾。 从输出结果来看归并排序因为是递归地排序所以要从后往前看 从树状结构来理解这个递归过程 # 定义函数用于合并两个序列。后续merge_sort函数递归调用 把序列一路递归到长度为1的两个来跑merge
def merge(li1,li2):result []while len(li1)!0 and len(li2)!0:if li1[0]li2[0]:result.append(li1.pop(0))else:result.append(li2.pop(0))result.extend(li1)result.extend(li2)return resultdef merge_sort(li):# 一路递归到序列剩下一个元素print(li)if len(li)2:return li# 基于二分的思想mid len(li)//2left merge_sort(li[:mid])right merge_sort(li[mid:])return merge(left,right)n int(input())
li list(map(int,input().split()))
print( .join(map(str,merge_sort(li)))) 6、计数排序 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序计数排序要求输入的数据必须是有确定范围的整数。 计数排序与桶排序的区别 1. 基本概念 计数排序计数排序是一种线性时间复杂度的排序算法适用于已知范围的整数排序。它通过一个额外的数组来记录每个元素的出现次数然后根据这些计数重新构建排序后的数组。 桶排序桶排序是一种分布排序算法它将元素分布到有限数量的桶中每个桶再分别排序。所有桶中的元素收集起来以后就是有序的。 2. 适用条件 计数排序 适用于整数排序。 需要知道输入数据的最小值和最大值。空间复杂度较高因为需要一个额外的计数数组。时间复杂度为 O(nk)其中 n 是数据的数量k 是数据的范围。 桶排序 适用于任意类型的数据只要可以比较大小。 不需要知道输入数据的最小值和最大值。空间复杂度取决于桶的数量和数据分布。时间复杂度为 O(nk)其中 n 是数据的数量k 是桶的数量。 3. 实现步骤 计数排序 找到输入数据中的最小值和最大值。 创建一个计数数组并初始化为零。遍历输入数据统计每个值的出现次数。根据计数数组重建排序后的数据。 桶排序 创建若干个空桶。 将输入数据分配到各个桶中。对每个桶进行单独排序。依次从各个桶中取出数据得到有序的结果。 值得注意的是如果不通过一些内存的优化策略使用计数排序会报内存错误。 内存错误MemoryError 是因为计数排序需要为数据范围maxvalue - minvalue 1分配一个大小为 O(k) 的数组。当数据的范围即 maxvalue - minvalue非常大时分配的计数数组可能需要超出可用内存。 原因分析 1.数据范围过大 计数排序创建的 count 数组其长度为 maxvalue - minvalue 1与数据的范围成正比。如果 maxvalue 和 minvalue 之间的差距非常大比如几百万甚至更大那么需要创建一个超大数组导致内存溢出。 2.不是所有数据都连续 计数排序默认假设数据是连续的。如果输入数据是稀疏的如 1 和 1000000 之间只有少量值这种实现方式会浪费大量内存。 示例 假设输入数据 m [1, 1000000]那么计数数组的大小会是 1000000 - 1 1 1000000。即使实际数据量只有 2 个数仍然会为 100 万个位置分配内存。 一个可行的策略是哈希表代替计数数组改用一个字典哈希表来记录元素的出现次数这样可以避免为稀疏数据分配多余的空间。 def counting_sort_optimized(m):# 统计每个元素的出现次数count {}for num in m:if num in count:count[num] 1else:count[num] 1# 根据统计结果生成排序后的数组sorted_m []for key in sorted(count): # 按键值升序排序sorted_m.extend([key] * count[key])return sorted_mn int(input())
m list(map(int, input().split()))
a counting_sort_optimized(m)
print( .join(map(str, a)))7、桶排序 桶排序Bucket Sort是一种基于分布的排序算法也称为箱排序。它通过将数据分到若干个有序的“桶”中然后对每个桶进行单独排序最后将所有桶中的数据合并起来得到最终的排序结果。桶排序适用于数据分布均匀且数据量较大的情况其时间复杂度为 O(nk)其中 n 是待排序元素的数量k 是桶的数量。 桶排序是计数排序的升级版。它利用了函数的映射关系高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效我们需要做到这两点 1.在额外空间充足的情况下尽量增大桶的数量 2.使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。 3.同时对于桶中元素的排序选择何种比较排序算法对于性能的影响至关重要。 什么时候最快 当输入的数据可以均匀的分配到每一个桶中。 什么时候最慢 当输入的数据被分配到了同一个桶中。 例子演示序列[11,22,33,44,45,56,77,88,99] def bucket_sort(m,bucket_count):# m序列bucket_count多少个桶minvalue,maxvalue min(m),max(m)# 桶的大小bucket_size (maxvalue - minvalue1)// bucket_count1# 存放每个桶 []代表一个桶res [[] for _ in range(bucket_count1)]for i in m: # m个桶idx (i - minvalue)//bucket_sizeres[idx].append(i)# ans存放排序结果ans []for res_i in res:res_i.sort()ans res_ireturn ansn int(input())
m list(map(int,input().split()))
a bucket_sort(m,min(n,10000))
print( .join(map(str,a)))
