排序算法2

排序算法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 = left+1# 除选出的序列第一个元素作为基准值，遍历当前序列剩下的元素for i in range(left+1,right+1):if li[i] <= li[left]:# 放左边li[idx],li[i] = li[i],li[idx]# 本轮基准值下标后移1idx += 1# 小于等于本轮基准值的元素为li[left+1,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,mid+1,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(n+k)，其中 n 是数据的数量，k 是数据的范围。

桶排序：

        适用于任意类型的数据（只要可以比较大小）。

        不需要知道输入数据的最小值和最大值。空间复杂度取决于桶的数量和数据分布。时间复杂度为 O(n+k)，其中 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(n+k)，其中 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 - minvalue+1)// bucket_count+1# 存放每个桶 []代表一个桶res = [[] for _ in range(bucket_count+1)]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)))