《奇妙的排序》课件

奇妙的排序排序在计算机世界中无处不在让我们揭开排序的神秘面纱什么是排序？定义实际意义常见场景将无序数据按特定规则重新排列提高数据处理效率通讯录、成绩单、商品价格排序的分类内部排序数据全部加载到内存外部排序数据部分存储在外部设备稳定排序相等元素保持原顺序非比较排序不通过比较确定顺序排序的应用场景数据检索优化列表展示大数据分析二分查找前提是有序用户界面数据呈现排序是数据处理基础步骤排序的基本性能指标空间复杂度排序过程所需额外内存时间复杂度排序算法执行所需时间稳定性相等元素相对位置是否变化第一组排序算法总览插入排序选择排序类似整理扑克牌反复选择最小元素适合小规模近乎有序数据实现简单但效率不高冒泡排序相邻元素比较交换教学常用但实际应用少插入排序原理扑克牌整理类比一张张插入到合适位置已排序区域左侧维持有序状态新元素插入在有序区找到正确位置插入排序流程演示初始状态第一个元素视为已排序取下一元素与已排序元素从右向左比较腾出位置大于新元素的右移插入元素放入合适位置插入排序代码示例def insertion_sortarr:for iin range1,lenarr:key=arr[i]j=i-1while j=0and arr[j]key:arr[j+1]=arr[j]j-=1arr[j+1]=keyreturn arr关键内循环找插入位置右移操作腾出插入空间插入排序优缺点优点缺点实现简单直观大数据集效率低小数据集效率好平均时间复杂度On²近乎有序时接近On逆序时最差性能选择排序原理查找最小值在未排序区域寻找交换位置与未排序区首位交换重复操作缩小未排序区域范围选择排序流程动画初始状态全部为未排序区域查找最小值遍历未排序区域交换元素放到已排序区末尾重复过程直至全部有序选择排序代码实现def selection_sortarr:for iin rangelenarr:min_idx=ifor jin rangei+1,lenarr:if arr[j]arr[min_idx]:min_idx=jarr[i],arr[min_idx]=arr[min_idx],arr[i]return arr双重循环On²时间复杂度交换次数最多n-1次选择排序优缺点交换次数少性能稳定最多n-1次交换无论数据如何都是On²实现简单不稳定排序思路清晰易于理解相等元素可能位置变化冒泡排序原理冒泡原理相邻比较渐进有序大元素像气泡上浮两两比较决定是否交换每轮确定一个最大值位置冒泡排序动画演示相邻元素交换大的向右移一轮冒泡最大元素到末尾重复过程缩小未排序范围完成排序所有元素就位冒泡排序代码示例def bubble_sortarr:n=lenarrfor iin rangen:for jin range0,n-i-1:if arr[j]arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]return arr外循环控制轮数内循环相邻比较交换优化设标志提前终止冒泡排序优缺点优点缺点简单易懂，入门首选时间复杂度On²容易发现最大/最小值交换操作频繁稳定排序大数据排序效率低提前终止优化不适用于实际工程三种基础排序算法对比第二组排序算法总览归并排序快速排序分治思想代表，稳定高效实践中最常用高效算法堆排序利用二叉堆数据结构归并排序原理分治策略归并过程稳定保证问题拆分为小问题递归拆分直至单元素合并时保持相等元素顺序各自解决后合并结果两两合并有序序列完美平衡递归树归并排序流程动画递归返回合并有序序列最终得到完全有序序列直至基本情况两两按序合并递归分解单元素数组已有序序列对半分割归并排序代码实现def merge_sortarr:if lenarr=1:return arrmid=lenarr//2left=merge_sortarr[:mid]right=merge_sortarr[mid:]return mergeleft,rightdef mergeleft,right:result=[]i=j=0while ilenleft andjlenright:if left[i]=right[j]:result.appendleft[i]i+=1else:result.appendright[j]j+=1result.extendleft[i:]result.extendright[j:]return result归并排序优缺点优点稳定性好，时间复杂度稳定Onlogn缺点需要额外On空间，不适合内存受限场景快速排序原理选取基准通常选首/中/末元素划分区域小于基准放左侧递归排序对子区域重复操作快速排序流程动画选取基准元素1通常取第一个或中间元素划分过程2小于基准放左，大于基准放右基准归位3将基准放在最终正确位置递归处理4对左右子数组重复以上步骤快速排序代码实现def quick_sortarr,low,high:if lowhigh:pi=partitionarr,low,highquick_sortarr,low,pi-1quick_sortarr,pi+1,highreturn arrdefpartitionarr,low,high:pivot=arr[high]i=low-1for jin rangelow,high:if arr[j]=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[high]=arr[high],arr[i+1]return i+1快速排序优缺点高效原地排序不稳定平均Onlogn，常数因只需Ologn栈空间相等元素可能交换位置子小最坏情况有序数组时退化为On²堆排序原理二叉堆结构最大堆性质排序过程完全二叉树实现父节点大于等于子节点大顶堆提取最大值堆排序流程可视化构建堆将无序数组转为最大堆交换并调整顶部与末尾交换后重建堆重复过程持续交换调整直至有序堆排序代码实现def heapifyarr,n,i:largest=il=2*i+1r=2*i+2if ln andarr[l]arr[largest]:largest=lif rn andarr[r]arr[largest]:largest=rif largest!=i:arr[i],arr[largest]=arr[largest],arr[i]heapifyarr,n,largestdef heap_sortarr:n=lenarr#构建大顶堆for iin rangen//2-1,-1,-1:heapifyarr,n,i#一个个交换元素for iin rangen-1,0,-1:arr[i],arr

[0]=arr

[0],arr[i]heapifyarr,i,0return arr堆排序优缺点优点优点2原地排序，空间复杂度O1稳定Onlogn时间复杂度1缺点3不稳定排序应用5缺点优先队列实现基础4实际运行通常慢于快排第二组排序综合对比Onlogn On平均时间复杂度归并排序空间三种算法都是额外内存需求O1快排/堆排空间原地排序优势希尔排序原理设置增量按间隔分组，初始较大分组插入排序各组内使用插入排序缩小增量逐步减小直至为1最终排序增量为1时完成排序希尔排序动画演示初始状态间隔为51无序数组，设置初始间隔相隔5个元素分为一组2间隔为14间隔为23普通插入排序完成相隔2个元素分为一组希尔排序代码实现def shell_sortarr:n=lenarrgap=n//2while gap0:for iin rangegap,n:temp=arr[i]j=iwhile j=gap andarr[j-gap]temp:arr[j]=arr[j-gap]j-=gaparr[j]=tempgap//=2return arr希尔排序优缺点优点缺点插入排序改进版增量序列选择复杂适合中等规模数据时间复杂度分析复杂对部分有序效果好不同增量效率差异大原地排序，无需额外空间不稳定排序非比较型排序简介计数排序桶排序统计元素出现次数分桶再排序适用于范围较小的整数适合均匀分布数据基数排序按位数排序适用于整数和字符串计数排序原理统计频率计算每个元素出现次数累加频率确定元素最终位置逆序填充保持稳定性计数排序代码实现def counting_sortarr:max_val=maxarrm=max_val+1count=

[0]*mfor ain arr:count[a]+=1i=0for ain rangem:for cin rangecount[a]:arr[i]=ai+=1return arr时间复杂度On+k空间复杂度Okk是数据范围大小桶排序原理创建桶划分数据范围为多个区间分配元素将元素放入对应桶中桶内排序对每个桶内元素排序合并结果按顺序合并各桶桶排序代码实现def bucket_sortarr:#创建桶bucket_count=lenarrbuckets=[[]for_in rangebucket_count]#分配元素到桶for numin arr:index=intbucket_count*numbuckets[index].appendnum#桶内排序for bucketin buckets:bucket.sort#合并桶result=[]for bucketin buckets:result.extendbucketreturn result基数排序原理按位排序从低位到高位数字分桶按当前位值分配收集元素保持相对顺序重复过程直到最高位处理完毕基数排序代码实现def radix_sortarr:max_num=maxarrexp=1while max_num//exp0:counting_sort_by_digitarr,expexp*=10return arrdefcounting_sort_by_digitarr,exp:n=lenarroutput=

[0]*ncount=

[0]*10for iin rangen:digit=arr[i]//exp%10count[digit]+=1for iin range1,10:count[i]+=count[i-1]i=n-1while i=0:digit=arr[i]//exp%10output[count[digit]-1]=arr[i]count[digit]-=1i-=1for iin rangen:arr[i]=output[i]各排序算法大总结排序算法可视化工具推荐推荐工具VisuAlgo、Algorithm Visualizer、Sorting.at互动性强，便于理解算法执行过程排序在现实中的应用案例数据库索引排队系统数字榜单B树/B+树结构中的有序性优先级排序智能调度高效更新排名信息排序算法面试常见考点算法选择思路如何根据场景选择合适算法优化技巧如何优化快排基准元素选择复杂度分析平均/最坏/最好情况分析手写实现能否准确无误手写关键算法归纳与知识拓展算法优化分布式排序外部排序混合排序算法思想大数据环境下的排序策略处理超大数据集的排序方法本课小结与互动核心收获继续学习路线•掌握各种排序算法原理•深入算法分析•了解算法性能与适用场景•数据结构进阶•提升分析与实现能力•算法设计模式。