数据结构排序算法课件：概述与主要排序方法

注册岩土工程师专业知识模拟试卷十考试须知请考生仔细阅读规则，诚信应考目录EXAMINSTRUCTIONS01.考生须知CandidateGuidelines02.考场规则ExaminationRules03.考试说明ExaminationDescription04.答题须知AnsweringInstructions05.温馨提示Reminders考生须知考生必须凭有效身份证件（身份证、军官证、护照等）进入考场，对号入座。考生应在开考前30分钟进入考场，迟到超过15分钟不得入场。除必要文具（黑色签字笔、2B铅笔、橡皮、计算器）外，其他物品按要求放置。考生须认真核对试卷信息，发现问题应立即向监考人员报告。考试过程中应保持安静，独立作答，严禁任何形式的作弊行为。考场规则考场内禁止吸烟、喧哗、交头接耳、左顾右盼、打手势、做暗号。禁止夹带、抄袭、传递纸条或交换试卷、答题卡。禁止将试卷、答题卡或草稿纸带出考场。考生如遇问题，应举手示意，由监考人员解答。考试结束信号发出后，考生应立即停止答题，并将试卷、答题卡和草稿纸按顺序整理好，放在桌面上，待监考人员收齐后，方可离开考场。考试说明考试科目注册岩土工程师专业知识（试卷十）考试时间请以准考证通知为准考试形式闭卷考试（禁止携带参考资料）试卷满分200分（合格标准通常为120分）考试题型分布包括：单项选择题、多项选择题、案例分析题请各位考生严格遵守考场纪律，合理分配答题时间，预祝考试顺利！答题须知01.考生必须使用黑色签字笔在答题卡指定位置填写姓名、准考证号等信息，确保信息准确无误。02.选择题答案必须用2B铅笔填涂在答题卡上，修改答案时需用橡皮擦干净，保持卡面清洁。03.主观题答案必须用黑色签字笔书写在答题卡指定区域内，字迹要工整、清晰，超出区域无效。04.严禁在答题卡上做任何与答题无关的标记，不得折叠、污损答题卡，否则按违规处理。05.草稿纸由考场统一发放，仅供演算使用，考试结束后由监考人员统一收回，不得带出考场。请严格遵守以上规定，认真审题，规范作答，预祝各位考生取得优异成绩。温馨提示请考生提前熟悉考场位置，合理安排出行时间，避免迟到。建议考生携带必要的保暖衣物和饮用水，做好个人防护。考试期间，请保持冷静，认真审题，仔细作答，规范书写。预祝各位考生考试顺利，发挥最佳水平，取得优异成绩！感谢观看祝各位考生考试顺利！请保持安静，准备开始作答数据结构排序算法课件概述与主要排序方法2026计算机科学与技术课程系列目录/CONTENTS01排序算法概述02初级排序方法03高级排序方法04总结与思考SORTINGALGORITHMSCOURSE01排序算法概述OVERVIEWOFSORTINGALGORITHMS什么是排序？核心定义排序是计算机科学中一种基本的算法，它将一组无序的数据元素，按照特定的顺序（如升序或降序）重新排列成有序序列的过程。主要目的排序的核心价值在于方便后续的查找、统计和处理操作，是数据处理的基础。算法示例原始数据(无序):[5,2,9,1,5,6]处理结果(升序):[1,2,5,5,6,9]排序算法的重要性数据处理的基础排序是许多复杂算法（如查找、搜索、数据分析）的前置步骤，是处理海量数据的必经之路。算法学习的基石涵盖了算法设计的核心思想，如分治法、递归、贪心等，是理解高级算法的基础。提升程序性能高效的排序算法可以显著减少数据处理的时间复杂度，直接提升程序的整体运行效率。面试高频考点技术面试中最常考察的内容之一，是衡量程序员算法基础和逻辑思维能力的重要标准。排序算法的分类按时间复杂度初级排序(O(n²))简单直观，效率较低。如：冒泡、选择、插入排序。高级排序(O(nlogn))效率更高，常用于大规模数据。如：快速、归并、堆排序。按稳定性稳定排序相等元素相对位置不变。如：冒泡、插入、归并排序。不稳定排序相等元素相对位置可能改变。如：选择、快速、堆排序。按是否基于比较比较类排序通过元素间比较确定顺序。绝大多数排序算法属于此类。非比较类排序不通过比较确定顺序。如：计数排序、基数排序。02初级排序方法BASICSORTINGALGORITHMS冒泡排序(BubbleSort)核心原理重复走访待排序数列，一次比较两个相邻元素，若顺序错误则交换。该过程持续进行直到没有交换发生，说明数列已排序完成。因较小元素会经由交换慢慢“浮”到顶端，如同气泡上浮而得名。排序过程示意图时间复杂度平均/最坏O(n²)，最好O(n)空间复杂度O(1)-原地排序算法稳定性稳定排序(Stable)冒泡排序-代码与复杂度PythonImplementationdefbubble_sort(arr):n=len(arr)foriinrange(n):swapped=Falseforjinrange(0,n-i-1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]swapped=Trueifnotswapped:breakreturnarr时间复杂度TimeComplexity最好O(n)(有序)/最坏O(n²)(逆序)空间复杂度SpaceComplexity仅需常数级额外空间：O(1)稳定性Stability冒泡排序是一种稳定的排序算法💡核心思想：通过相邻元素的比较与交换，使较大的数逐渐“浮”到数组末端。引入swapped标志可优化最佳情况性能。选择排序(SelectionSort)核心原理首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。图示：选择排序第一轮过程AlgorithmVisualization|TimeComplexity:O(n²)选择排序-代码与复杂度defselection_sort(arr):n=len(arr)foriinrange(n):min_idx=iforjinrange(i+1,n):ifarr[j]<arr[min_idx]:min_idx=jarr[i],arr[min_idx]=arr[min_idx],arr[i]returnarr时间复杂度最好、最坏和平均情况均为O(n²)空间复杂度仅需常数级额外空间，为O(1)算法稳定性不稳定排序（相同元素相对位置可能改变）核心思想：每次从未排序部分中找到最小（大）元素，存放到已排序部分的末尾，以此类推直到全部排序完成。插入排序(InsertionSort)核心原理通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。算法特性通常采用in-place排序(O(1)额外空间)。扫描时需反复后移已排序元素，为新元素腾出空间。形象比喻：如同整理手中的扑克牌，将每一张新摸到的牌插入到正确的位置。插入排序-代码与复杂度PythonImplementationdefinsertion_sort(arr):foriinrange(1,len(arr)):key=arr[i]j=i-1whilej>=0andkey<arr[j]:arr[j+1]=arr[j]j-=1arr[j+1]=keyreturnarr时间复杂度TimeComplexity最好O(n)|最坏/平均O(n²)空间复杂度SpaceComplexityO(1)-原地排序算法，仅需常数级额外空间稳定性Stability稳定排序(Stable)-相等元素相对位置不变插入排序是一种简单直观的排序算法，适用于小规模数据或基本有序的数据集合。其工作原理类似于整理扑克牌，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。03高级排序方法ADVANCEDSORTINGALGORITHMS快速排序(QuickSort)核心原理：分治法(DivideandConquer)快速排序的基本思想是通过一趟排序将待排数据分割成独立的两部分：分区：选定基准值，将数据分为“小于基准”和“大于基准”的两部分。递归：分别对这两部分数据重复上述过程，直至整个序列有序。这种分而治之的策略使其成为实践中高效的排序算法。图示：分区与递归过程演示平均时间复杂度:O(nlogn)空间复杂度:O(logn)排序性质:不稳定排序快速排序-代码与复杂度defquick_sort(arr,low=0,high=None):ifhighisNone:high=len(arr)-1iflow<high:pi=partition(arr,low,high)quick_sort(arr,low,pi-1)quick_sort(arr,pi+1,high)returnarrdefpartition(arr,low,high):pivot=arr[high];i=low-1forjinrange(low,high):ifarr[j]<=pivot:i+=1;arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[high]=arr[high],arr[i+1]returni+1时间复杂度最好/平均：O(nlogn)|最坏：O(n²)空间复杂度递归调用栈深度：O(logn)稳定性不稳定排序（相同值元素相对位置可能改变）QuickSort:DivideandConquerAlgorithm归并排序(MergeSort)核心原理：分治法(DivideandConquer)归并排序通过递归将问题分解为更小的子问题，直至子序列有序，再通过合并操作将有序子序列逐层合并，最终得到完全有序的序列。关键步骤解析分解(Divide)：将数组递归拆分为单元素子数组。合并(Merge)：将两个有序子数组合并为更大的有序数组。图示：归并排序的“分解”与“合并”全过程归并排序-代码与复杂度defmerge_sort(arr):iflen(arr)>1:mid=len(arr)//2left=arr[:mid];right=arr[mid:]merge_sort(left);merge_sort(right)i=j=k=0whilei<len(left)andj<len(right):ifleft[i]<right[j]:arr[k]=left[i];i+=1else:arr[k]=right[j];j+=1k+=1whilei<len(left):arr[k]=left[i];i+=1;k+=1whilej<len(right):arr[k]=right[j];j+=1;k+=1returnarr时间复杂度最好/最坏/平均均为O(nlogn)空间复杂度需要额外临时数组存储，为O(n)稳定性属于稳定排序算法，不改变相对顺序核心思想：采用分治法（DivideandConquer），将数组递归分割，再将有序子数组合并。堆排序(HeapSort)核心数据结构：堆(Heap)近似完全二叉树结构，满足子节点键值始终小于（或大于）父节点。基本思想与步骤将待排序序列构造成最大堆，堆顶即为最大值。将堆顶与末尾元素交换，剩余元素重新调整为最大堆。最终结果反复执行交换与调整，最终得到有序序列。堆排序过程示意图：构建大顶堆与交换堆排序-代码与复杂度defheap_sort(arr):n=len(arr)foriinrange(n//2-1,-1,-1):heapify(arr,n,i)foriinrange(n-1,0,-1):arr[i],arr[0]=arr[0],arr[i]heapify(arr,i,0)returnarrdefheapify(arr,n,i):largest=i;l=2*i+1;r=2*i+2ifl<nandarr[i]<arr[l]:largest=lifr