数据基础及结构 2

第九章内部排序内部排序算法的深入解析与性能对比9.1排序算法概述数据处理的核心支柱排序算法是检索效率的基石。从电商价格筛选到社交媒体时间线，无序数据会导致检索效率急剧下降，排序确保了信息的快速呈现。内部排序算法进阶从基础的冒泡排序到高效的快速排序与堆排序。本章将深入探讨不同算法的特性，建立起针对不同场景的算法选择决策框架。海量数据处理处理数十万条数据，实现毫秒级响应时间复杂度优化从O(n²)到O(nlogn)，提升系统性能上限内存内部排序深入内存操作细节，掌握数据交换核心逻辑9.1.1排序的定义与基本概念核心定义：有序化过程排序是将数据元素的任意序列，重新排列为按关键字有序的序列。数学上，即确定排列p1...pn，使得关键字满足Kp1≤Kp2≤...≤Kpn。关键字：排序的依据关键字可以是主关键字（唯一确定记录，排序结果唯一）或次关键字（可能重复，结果不唯一）。它是决定记录排列顺序的关键数据项。排序分类：基于存储位置内部排序：待排序记录全部存放在内存中进行。本章主要聚焦此类算法。外部排序：数据量过大，内存无法容纳，需借助外存（磁盘等）辅助完成排序。9.1.2排序算法的性能分析指标时间复杂度核心定义：衡量算法运行效率的关键指标，描述了算法执行时间随数据规模增长的变化趋势。应用意义：直接决定了处理大规模数据时的响应速度，是选择算法的首要考量因素。空间复杂度核心定义：衡量算法在执行过程中临时占用内存空间的大小，反映了算法的资源消耗情况。应用意义：在内存受限的嵌入式设备或处理海量数据时，空间复杂度是必须权衡的重要指标。稳定性核心定义：排序前后，关键字相同的记录的相对位置是否保持不变。应用意义：如电商平台销量排序，确保销量相同的商品按上架时间排列，保证数据的一致性。9.2插入排序核心思想：逐步构建有序序列类似于手工整理扑克牌，将未排序元素逐一插入到已排序子序列的合适位置，保持前端子序列始终有序。本章主要内容直接插入排序基本的顺序查找插入方式折半插入排序利用折半查找优化插入位置希尔排序基于分组的改进插入排序9.2.1直接插入排序基本思想将序列分为已排序区和未排序区，初始时第一个元素视为已排序。每次从未排序区取下一个元素(key)，自后向前扫描已排序序列。找到第一个不大于key的位置，将key插入其后，保证有序区向右扩展。重复上述步骤，直到全部排序完成。排序过程示意13547扫描并插入后的结果：13457蓝色块：已排序区|橙色块：当前待插入元素|灰色块：未排序区9.2.1直接插入排序-算法实现template<typenameT>voidDirectInsertSort(vector<T>&arr){//从第二个元素开始（索引1），因为第一个元素默认已排序for(inti=1;i<arr.size();i++){Tkey=arr[i];//当前待插入元素intj=i-1;//从已排序区的最后一个元素开始比较

//向左扫描已排序区，为key寻找插入位置while(j>=0&&arr[j]>key){arr[j+1]=arr[j];//大于key的元素后移j--;}arr[j+1]=key;//插入元素到正确位置}}9.2.1直接插入排序-示例演示初始状态：[7|3,5,2,4]（竖线左侧为已排序区）第1趟(插入3)：比较7>3，7右移，结果[3,7|5,2,4]第2趟(插入5)：比较7>5，移位插入，结果[3,5,7|2,4]第3趟(插入2)：依次比较7、5、3均大于2，右移后插入，结果[2,3,5,7|4]第4趟(插入4)：比较至3停止，插入3后，结果[2,3,4,5,7]（排序完成）9.2.1直接插入排序-性能分析时间复杂度最坏情况(逆序)O(n²)，需移动大量元素最好情况(基本有序)O(n)，只需少量比较平均情况O(n²)，效率与冒泡排序相当空间复杂度O(1)直接插入排序是典型的原地排序算法。在排序过程中，仅需要一个常数级的辅助空间（如临时变量）来存储待插入的元素，不需要额外开辟大量存储空间。稳定性稳定排序在排序过程中，当遇到相等的元素时，算法不会改变它们原有的相对次序。这一特性在处理包含复杂对象的排序时非常重要。9.2.2折半插入排序核心思想与改进基本定义：直接插入排序的改进版。核心在于利用二分查找替代顺序查找，以确定插入位置。核心优势：显著减少了关键字的比较次数，将比较复杂度从O(n)降低至O(logn)，提升查找效率。执行步骤：保存待插入元素，划定查找区间[low,high]通过二分法快速定位插入点将插入点右侧元素统一后移，完成插入二分查找定位过程示意已排序序列：3579待插入元素：66初始范围:[3,9]，中间值为76<7，缩小范围到左半区[3,5]6>5，确定插入位置在5和7之间9.2.2折半插入排序-算法实现template<typenameT>voidBinaryInsertSort(vector<T>&arr){for(inti=1;i<arr.size();i++){Ttemp=arr[i];//当前待插入元素intlow=0,high=i-1;//在已排序区[0,i-1]中二分查找//二分查找插入位置while(low<=high){intmid=low+(high-low)/2;if(arr[mid]>temp)high=mid-1;elselow=mid+1;}//将插入位置后的元素后移for(intj=i-1;j>high;j--)arr[j+1]=arr[j];arr[high+1]=temp;}}9.2.2折半插入排序-示例演示初始状态待排数组：[6|1,4,2,5]第1趟：插入1查找位置：0→结果：[1,6|4,2,5]第2趟：插入4查找位置：1→结果：[1,4,6|2,5]第3趟：插入2查找位置：1→结果：[1,2,4,6|5]第4趟：插入5查找位置：3→结果：[1,2,4,5,6](排序完成)9.2.2折半插入排序-性能分析时间复杂度优化点：比较次数显著减少，但移动元素次数与直接插入排序相同。复杂度：最坏、平均、最好情况下均为O(n²)。空间复杂度复杂度：O(1)。性质：属于原地排序算法，仅需常数级额外空间。稳定性结论：稳定排序。说明：与直接插入排序相同，关键字相同的元素在排序前后相对位置保持不变。9.2.3希尔排序(缩小增量排序)核心思想：分组插入排序1.分组：选取增量gap，将序列按下标间隔gap分为若干组。2.组内排序：对每个分组独立进行直接插入排序。3.缩小增量：不断缩小gap(如减半)，重复分组排序过程。4.最终排序：当gap=1时，对基本有序的序列进行最后一次插入排序。图解：增量分组过程阶段一：gap=3(间隔分组)91537482阶段二：gap=1(整体排序)12345789💡核心优势：通过预排序使序列基本有序，最后一次gap=1的插入排序效率极高。9.2.3希尔排序-算法实现template<typenameT>voidShellSort(vector<T>&arr){//初始gap为数组长度一半，每次减半直至1for(intgap=arr.size()/2;gap>0;gap/=2){//对每个gap分组进行插入排序for(inti=gap;i<arr.size();i++){Ttemp=arr[i];//当前待插入元素intj=i;

//按gap跨度进行插入移动while(j>=gap&&arr[j-gap]>temp){arr[j]=arr[j-gap];//大元素后移j-=gap;//跳转到前一个分组元素}arr[j]=temp;//插入元素}}}9.2.3希尔排序-示例演示Step1:初始增量Gap=4将序列分为4组，对每组进行插入排序，使序列达到“局部有序”状态。初始数组：[9,8,7,6,5,4,3,2,1]排序后：[5,3,1,2,4,7,8,6,9]Step2:缩小增量Gap=2再次分组排序，进一步减少逆序对，序列更加接近有序状态。输入数组：[5,3,1,2,4,7,8,6,9]排序后：[1,2,3,4,5,6,7,8,9]Step3:最终增量Gap=1对整个序列做一次直接插入排序，此时序列已基本有序，排序快速完成。输入数组：[1,2,3,4,5,6,7,8,9]最终结果：[1,2,3,4,5,6,7,8,9]9.2.3希尔排序-性能分析时间复杂度核心依赖：增量序列的选择最坏情况：O(n²)实际表现：通常接近O(n^1.3)或O(nlogn)，优于直接插入排序空间复杂度算法特性：原地排序算法(In-place)复杂度：O(1)解释：仅使用常数级别的额外辅助空间稳定性分析结论：不稳定排序原因：元素是跨组移动的，这可能导致相等元素的相对次序发生改变。9.3交换排序交换排序是一类通过不断交换元素位置来实现序列有序化的排序方法。冒泡排序(BubbleSort)简单直观的交换排序典型快速排序(QuickSort)高效且应用广泛的排序算法9.3.1冒泡排序基本思想核心逻辑：每趟比较相邻元素，将最大（或最小）的元素逐步“冒泡”到序列的一端。执行过程：从前向后扫描，若左元素大于右元素则交换。每完成一趟，当前未排序区的最大值即被安置在末尾。终止条件：重复遍历过程，直到没有交换发生或遍历完所有元素。过程示意：大数上浮31524(Max)图示：较大的数值（气泡）通过交换逐步移动到右侧（顶部）9.3.1冒泡排序-算法实现template<typenameT>voidBubbleSort(vector<T>&arr){//遍历n-1次（每次确定一个最大值位置）for(inti=0;i<arr.size()-1;i++){boolswapped=false;//本趟交换标志for(intj=0;j<arr.size()-1-i;j++){//相邻元素比较if(arr[j]>arr[j+1]){swap(arr[j],arr[j+1]);//交换逆序对swapped=true;//标记发生交换}}

//本趟无交换说明已完全有序，提前终止if(!swapped)break;}}9.3.1冒泡排序-示例演示初始状态数组：[5,1,4,2,8]第1趟最大值“8”冒泡到末尾，结果：[1,4,2,5,8]第2趟对前4个元素排序，“5”就位，结果：[1,4,2,5,8]第3趟对前3个元素排序，“4”就位，结果：[1,2,4,5,8]第4趟检测到本趟无交换，说明数组已有序，算法提前结束。9.3.1冒泡排序-性能分析时间复杂度最坏情况(逆序)：O(n²)平均情况：O(n²)最好情况(优化后)：O(n)（原序或近似有序时）空间复杂度复杂度：O(1)属于原地排序算法，仅使用常数级辅助空间，不需要额外的存储空间。稳定性性质：稳定排序排序过程中，相等元素的相对次序在排序前后保持不变。9.3.2快速排序核心思想：分治(Divide&Conquer)1.选基准(PivotSelection)从序列中选择一个元素作为“基准”，通常选择第一个、最后一个或中间元素。2.划分(Partition)重新排列序列，使小于基准的元素在左，大于基准的在右，基准归位。3.递归(Recursion)递归地对基准左侧和右侧的子序列重复上述操作，直至子序列长度为1。原理示意图：分区过程初始序列与基准选择(Pivot=5)37528划分后结果(Partitioned)32578小于基准大于基准9.3.2快速排序-算法实现template<typenameT>voidQuickSort(vector<T>&arr,intlow,inthigh){if(low<high){Tpivot=arr[low];//选择第一个元素为基准inti=low,j=high;//双指针

while(i<j){//从右向左找第一个小于pivot的元素while(i<j&&arr[j]>=pivot)j--;if(i<j)arr[i++]=arr[j];//移到左区

//从左向右找第一个大于pivot的元素while(i<j&&arr[i]<=pivot)i++;if(i<j)arr[j--]=arr[i];//移到右区}arr[i]=pivot;//基准归位

//递归排序左右分区QuickSort(arr,low,i-1);QuickSort(arr,i+1,high);}}9.3.2快速排序-示例演示Step1:初始划分(基准:6)原始数组：[6,1,4,7,3,9]操作：双指针扫描交换，将6置于正确位置结果：[3,1,4,6,7,9]Step2:递归左子区(基准:3)左子数组：[3,1,4]操作：选3为基准，划分后小数左移，大数右移结果：[1,3,4]Step3:递归右子区(基准:7)右子数组：[7,9]操作：选7为基准，9大于7，无需交换结果：[7,9]Step4:最终结果操作：合并所有有序子区间左子区[1,3,4]+基准6+右子区[7,9]最终排序结果：[1,3,4,6,7,9]9.3.2快速排序-性能分析时间复杂度平均情况：O(nlogn)最坏情况：O(n²)注：最坏情况通常发生在输入有序且选择首尾元素作为基准时。空间复杂度平均情况：O(logn)最坏情况：O(n)注：空间消耗主要来源于递归调用栈的深度。稳定性分析稳定性：不稳定原因：由于元素是跨区间交换的，相等元素的相对次序可能会发生改变。9.4选择排序核心思想：反复从待排序序列中选择最小（或最大）元素，将其放置到已排序序列末尾，逐步完成排序。本章内容：重点介绍两种典型的选择排序方法：简单选择排序和堆排序。9.4.1简单选择排序基本思想每一趟从待排序的数据元素中选出最小值（或最大值）。将选出的最小值与当前未排序部分的第一个元素交换位置。重复进行n-1趟，每趟确定一个元素的最终位置，直至所有元素有序。过程示意：寻找最小值并交换13725Step1:查找

在未排序区间[7,2,5]中找到最小值2。Step2:交换

将最小值2与未排序区间的第一个元素7交换位置。9.4.1简单选择排序-算法实现template<typenameT>voidSelectionSort(vector<T>&arr){for(inti=0;i<arr.size()-1;i++){intmin_idx=i;//当前最小元素索引

//在未排序区[i+1,n-1]查找最小元素for(intj=i+1;j<arr.size();j++){if(arr[j]<arr[min_idx]){min_idx=j;}}

//将最小元素交换到已排序区末尾if(min_idx!=i){swap(arr[i],arr[min_idx]);}}}9.4.1简单选择排序-示例演示示例数组：[64,25,12,22,11]第1趟：选择最小元素11遍历数组找到最小值11，与首位64交换。结果：[11,25,12,22,64]第2趟：选择剩余最小元素12在剩余元素中找到最小值12，与第二位25交换。结果：[11,12,25,22,64]第3趟：选择剩余最小元素22找到最小值22，与第三位25交换。结果：[11,12,22,25,64]第4趟：验证与完成剩余最小元素25已在正确位置，无需交换。最终结果：[11,12,22,25,64]9.4.1简单选择排序-性能分析时间复杂度O(n²)无论数据初始状态如何，都需要进行n(n-1)/2次比较。空间复杂度O(1)属于原地排序算法，仅使用常数级辅助空间。稳定性不稳定排序由于跳跃式交换，相等元素的相对次序可能发生改变。9.4.2堆排序基本思想与核心步骤1.构建最大堆将待排序序列构造成最大堆，此时堆顶元素为全局最大值。2.交换堆顶与末尾元素将堆顶最大值与数组末尾元素交换，使最大值就位。3.调整堆在剩余未排序元素上重新调整为最大堆，准备下一次交换。4.重复操作重复步骤2和3，直到堆中只剩一个元素。最大堆结构示意图10050403020图示：最大堆结构（父节点大于子节点）9.4.2堆排序-算法实现核心函数：Heapify(堆化)template<typenameT>voidHeapify(vector<T>&arr,intn,inti){intlargest=i;//初始化最大元素为根intleft=2*i+1;//左子节点索引intright=2*i+2;//右子节点索引//如果左子节点大于根if(left<n&&arr[left]>arr[largest])largest=left;//如果右子节点大于当前最大值if(right<n&&arr[right]>arr[largest])largest=right;//如果最大值不是根，交换并递归调整if(largest!=i){swap(arr[i],arr[largest]);Heapify(arr,n,largest);//递归调整受影响的子树}}主函数：HeapSort(堆排序)template<typenameT>voidHeapSort(vector<T>&arr){//构建最大堆（从最后一个非叶子节点开始）for(inti=arr.size()/2-1;i>=0;i--)Heapify(arr,arr.size(),i);//逐个提取堆顶元素（最大值）到数组末尾for(inti=arr.size()-1;i>0;i--){swap(arr[0],arr[i]);//将当前堆顶移到末尾Heapify(arr,i,0);//调整剩余堆}}9.4.2堆排序-示例演示Step1:构建最大堆原始数组：[4,10,3,5,1]调整后：[10,5,3,4,1]注：此时堆顶元素10为最大值Step2:交换堆顶与末尾并调整交换结果：[1,5,3,4,10]重建堆：[5,4,3,1,10]注：10已就位，对前4个元素重新建堆Step3:重复交换与调整交换5和1：[1,4,3,5,10]重建堆：[4,1,3,5,10]注：持续将堆顶最大值移至未排序部分末尾Step4:最终有序数组排序完成：[1,3,4,5,10]总结：通过不断提取堆顶最大值并调整剩余元素，最终实现整体有序。9.4.2堆排序-性能分析时间复杂度O(nlogn)建堆过程复杂度为O(n)，后续每次调整堆的复杂度为O(logn)，共需n-1次调整。空间复杂度O(1)属于原地排序算法，仅使用常数级的辅助空间，空间利用率极高。稳定性不稳定排序在堆调整过程中，元素交换可能会改变相等元素的相对次序，因此不具备稳定性。9.5归并排序分治核心思想采用“分而治之”策略，将原序列递归分解为两个子序列，直到子序列长度为1，再进行合并。递归与合并过程从底向上合并有序子序列，将两个有序数组合并为一个有序数组，最终得到完整的有序序列。本章主要内容重点讲解最基础的二路归并排序算法，并扩展介绍多路归并排序的原理与应用。9.5.1二路归并排序基本思想与核心步骤1.分解(Divide)将待排序数组从中间一分为二，划分为左右两个子数组。2.解决(Conquer)递归地对左右两个子数组分别进行二路归并排序，直至子数组长度为1。3.合并(Merge)将两个已排序的子数组合并，形成一个更大的有序数组，自底向上完成排序。分治过程示意图原始数组：[8,4,5,7,1,3,6,2][8,4,5,7][1,3,6,2]...递归排序至长度为1，然后合并...最终有序数组：[1,2,3,4,5,6,7,8]9.5.1二路归并排序-算法实现核心函数：Merge(合并)template<typenameT>voidMerge(vector<T>&arr,intl,intm,intr){//创建左右子数组vector<T>L(arr.begin()+l,arr.begin()+m+1);vector<T>R(arr.begin()+m+1,arr.begin()+r+1);inti=0,j=0,k=l;//索引：左数组、右数组、原数组//比较左右数组元素，取较小者放入原数组while(i<L.size()&&j<R.size()){if(L[i]<=R[j])arr[k++]=L[i++];elsearr[k++]=R[j++];}//复制剩余元素while(i<L.size())arr[k++]=L[i++];while(j<R.size())arr[k++]=R[j++];}主函数：MergeSort(归并排序)template<typenameT>voidMergeSort(vector<T>&arr,intl,intr){if(l<r){intm=l+(r-l)/2;//防止整数溢出MergeSort(arr,l,m);//排序左半部MergeSort(arr,m+1,r);//排序右半部Merge(arr,l,m,r);//合并两部分}}9.5.1二路归并排序-示例演示第一步：分解(Divide)初始数组：[38,27,43,3,9,82,10]将数组递归地一分为二，直到无法再分最终分解为单个元素的子数组：[38],[27],[43],[3],[9],[82],[10]

单个元素天然有序，准备进入合并阶段第二步：合并(Merge)两两合并：[38]+[27]→[27,38]；[3]+[9]→[3,9]；[82]+[10]→[10,82]组间合并：[27,38]+[43]→[27,38,43]；[3,9]+[10,82]→[3,9,10,82]最终合并：[27,38,43]+[3,9,10,82]→最终有序数组排序结果：[3,9,10,27,38,43,82]9.5.1二路归并排序-性能分析时间复杂度O(nlogn)分解过程的时间复杂度为O(logn)，每一层合并的总时间为O(n)。由于总共有logn层，因此总体时间复杂度为线性对数级。空间复杂度O(n)算法需要额外的辅助空间来存储左右子数组的合并结果，这是归并排序的主要缺点，在处理海量数据时可能成为瓶颈。稳定性稳定排序在合并过程中，当左右子数组元素相等时，优先复制左子数组的元素，从而保持了相等元素的相对次序，这是其重要优势。9.5.2多路归并排序基本思想与核心步骤1.初始化最小堆将每个有序子序列的首个元素及其所属序列信息插入堆中，构建最小堆。2.提取最小值与插入取出堆顶最小值加入结果集，并从该值所属序列取下一个元素插入堆。3.结束条件重复上述过程，直到堆为空，所有元素合并完成。最小堆工作原理示意minAB通过最小堆，我们可以在O(logk)的时间复杂度内找到k个序列中的最小值。相比线性扫描的O(k)，这种方法在k较大时效率显著提升。9.5.2多路归并排序-算法实现template<typenameT>vector<T>MultiWayMergeSort(vector<vector<T>>&arrays){//定义堆元素类型：<元素值,序列索引,元素索引>usingHeapElement=tuple<T,int,int>;//最小堆比较函数（lambda表达式）autocomp=[](constHeapElement&a,constHeapElement&b){returnget<0>(a)>get<0>(b);//大于比较器实现最小堆};//创建最小堆priority_queuepriority_queue<HeapElement,vector<HeapElement>,decltype(comp)>minHeap(comp);vector<T>result;//归并结果//初始化：将每个序列的第一个元素加入堆for(inti=0;i<arrays.size();i++){if(!arrays[i].empty()){minHeap.push(make_tuple(arrays[i][0],i,0));}}//不断取出堆顶最小元素while(!minHeap.empty()){auto[val,arrIdx,elemIdx]=minHeap.top();//C++17结构化绑定minHeap.pop();result.push_back(val);//添加到结果//从取出元素所属序列取下一个元素if(elemIdx+1<arrays[arrIdx].size()){minHeap.push(make_tuple(arrays[arrIdx][elemIdx+1],arrIdx,elemIdx+1));}}returnresult;}9.5.2多路归并排序-示例演示Step1:初始化堆原始序列：序列A:[1,4,7]序列B:[2,5,8]序列C:[3,6,9]

操作：将各序列首元素放入最小堆，堆顶为最小值1。Step2:循环提取与补充第一次提取：取出堆顶1，加入结果。从序列A补充4，堆变为[2,4,3]。

第二次提取：取出堆顶2，加入结果。从序列B补充5，堆变为[3,4,5]。Step3:最终结果重复操作：依次取出3,4,5,6,7,8,9，并不断从对应序列补充元素，直到所有元素处理完毕。

合并结果：[1,2,3,4,5,6,7,8,9]9.5.2多路归并排序-性能分析时间复杂度O(nlogk)其中n是总元素数，k是归并段数。每次堆操作耗时O(logk)，共进行n次操作。空间复杂度O(k+n)k为堆的大小，n为存储最终结果所需的空间。主要消耗在于存储结果的数组。稳定性稳定排序若堆中元素值相等，优先选择原序列中位置靠前的元素，即可保证算法的稳定性。9.6基数排序基数排序是一种非比较型整数排序算法，通过按位数切割数字并逐位比较来实现。本章将重点讲解多关键字排序思想及链式基数排序的实现。9.6.1多关键字排序基本思想：次关键字优先(LSD)1.先按优先级最低的关键字（最次位）进行排序。2.再按优先级次高的关键字进行排序。3.依此类推，直到按最高优先级的关键字排序完成。关键前提：每一趟排序都必须是稳定的，才能保证最终结果的正确性。示例：学生记录排序过程Step1:原始数据(年级/成绩)[3,85][2,90][3,95][2,85][1,90]Step2:按次关键字(成绩)排序(LSD)[3,85][2,85][2,90][1,90][3,95]Step3:按主关键字(年级)排序(稳定)[1,90][2,85][2,90][3,85][3,95]9.6.1多关键字排序-算法实现//多关键字排序（先按成绩排序，再按年级排序）voidMultiKeySortEfficient(vector<Student>&students){sort(students.begin(),students.end(),[](constStudent&a,constStudent&b){//先按主关键字（年级）比较if(a.grade!=b.grade){returna.grade<b.grade;}//年级相同再按次关键字（成绩）比较returna.score<b.score;});}9.6.1多关键字排序-示例演示初始记录待排序数据：[三年级，85][一年级，90][三年级，90][一年级，85]第1趟：按次关键字(成绩)排序后结果：[一年级，85][三年级，85][一年级，90][三年级，90]第2趟：按主关键字(年级)使用稳定排序后结果：[一年级，85][一年级，90][三年级，85][三年级，90]9.6.1多关键字排序-性能分析核心：稳定性多关键字排序的最终结果正确性，完全依赖于每一轮排序算法的稳定性。必须全程使用稳定排序，否则会打乱次关键字顺序。时间复杂度复杂度取决于每轮算法。若每轮使用O(n)的稳定排序（如计数排序），则总时间复杂度为：

O(d*n)其中d为关键字个数，n为数据规模。典型应用场景适用于字段分明、排序层次清晰的场景：数据库记录排序（如先按部门，再按薪资）复杂对象属性排序多级分类数据整理9.6.2链式基数排序基本思想：分配与收集1.分配(Distribution)从最低位到最高位，依次按当前位数字，将元素插入到0-9号链表桶的尾部。2.收集(Collection)按桶号0到9的顺序，依次将各个链表桶中的元素链接起来，形成新的有序序列。原理示意：链表桶结构桶0桶1桶2桶3图示：按数字某一位的值分配到对应桶中，随后顺序收集9.6.2链式基数排序-原理详解（第一轮：按个位排序）初始序列：[170,45,75,90,2,802,24,66]

第一步：分配（按个位数字）•个位为0：170,90•个位为2：2,802•个位为4：24•个位为5：45,75•个位为6：66•其他桶位（1,3,7,8,9）为空

第二步：收集（按桶的顺序）依次从桶0到桶9收集元素，得到新序列：[170,90,2,802,24,45,75,66]9.6.2链式基数排序-原理详解（第二轮：按十位排序）上一轮结果：[170,90,2,802,24,45,75,66]第一步：分配（按十位数字）•十位为0：2,802•十位为2：24•十位为4：45•十位为6：66•十位为7：170,75•十位为9：90第二步：收集（按桶的顺序）依次从桶0到桶9收集元素，得到新序列：[2,802,24,45,66,170,75,90]9.6.2链式基数排序-原理详解（第三轮：按百位排序）上一轮结果:[2,802,24,45,66,170,75,90]第一步：分配（按百位数字）百位为0:2,24,45,66,75,90百位为1:170百位为8:802其他桶位（2-7,9）为空。第二步：收集（按桶的顺序）依次从桶0到桶9收集元素，得到最终有序序列：[2,24,45,66,75,90,170,802]9.6.2链式基数排序-算法实现intgetMaxDigit(constvector<int>&arr){intmax_val=*max_element(arr.begin(),arr.end());returnto_string(max_val).size();//转换为字符串取长度}voidRadixSort(vector<int>&arr){intmax_digits=getMaxDigit(arr);//最大位数vector<list<int>>buckets(10);//10个数字桶（0-9）

//从最低位到最高位处理for(intdigit=0;digit<max_digits;digit++){//分配阶段：按当前位数字放入对应桶for(intnum:arr){intd=(num/static_cast<int>(pow(10,digit)))%10;buckets[d].push_back(num);}

//收集阶段：按桶顺序（0-9）收集元素arr.clear();for(auto&bucket:buckets){arr.insert(arr.end(),bucket.begin(),bucket.end());bucket.clear();//清空桶用于下一轮}}}9.6.2链式基数排序-性能分析时间复杂度O(n×d)其中n是元素个数，d是最大数字的位数。每一趟分配和收集的时间都是O(n)，总共进行d趟。空间复杂度O(n+k)其中k是桶的数量（通常为10）。主要空间用于存储待排序元素和辅助排序的桶结构。稳定性分析稳定排序分配时元素插入桶尾，收集时按顺序链接，保证了相等元素的相对次序不变。9.7各种内部排序方法的比较选择合适的排序算法需要综合考量性能指标。本章将从时间复杂度、空间复杂度和稳定性三个维度，对常见内部排序算法进行全面对比分析。时间复杂度衡量算法执行效率，分析最好、最坏及平均情况下的运行时间。空间复杂度评估算法运行所需的额外内存空间，区分原地排序与非原地排序。算法稳定性考察关键字相等的记录在排序前后的相对位置是否保持不变。9.7.1时间性能对比表9-1各种排序方法时间复杂度比较排序算法最好情况时间复杂度平均情况时间复杂度最坏情况时间复杂度冒泡排序O(n)O(n²)O(n²)直接插入排序O(n)O(n²)O(n²)选择排序O(n²)O(n²)O(n²)希尔排序O(n)*O(n^1.3~1.5)*O(n²)*归并排序O(nlogn)O(nlogn)O(nlogn)快速排序O(nlogn)O(nlogn)O(n²)堆排序O(nlogn)O(nlogn)O(nlogn)计数排序O(n+k)O(n+k)O(n+k)基数排序O(d(n+k))O(d(n+k))O(d(n+k))*注：希尔排序的复杂度依赖于具体步长序列，上表中的结果参考常见分析。9.7.2空间性能对比表9-2各种排序方法空间复杂度比较排序算法额外空间复杂度是否原地排序冒泡排序O(1)是直接插入排序O(1)是选择排序O(1)是希尔排序O(1)是归并排序O(n)否快速排序O(logn)是堆排序O(1)是计数排序O(n+k)否基数排序O(d(n+k))否9.7.3稳定性表9-3各种排序方法稳定性比较排序方法是否稳定直接插入排序稳定折半插入排序稳定希尔排序不稳定冒泡排序稳定快速排序不稳定简单选择排序不稳定堆排序不稳定二路归并排序稳定多路归并排序稳定基数排序稳定9.8排序算法在深度学习中的应用注意力机制优化在Transformer架构中，通过排序筛选关键信息，降低计算复杂度，提升模型效率。推荐系统排序基于用户兴趣提取Top-N候选集，实现精准推荐与结果排序，提升业务转化效果。BeamSearch解码在文本生成任务中，通过排序保留最优候选路径，平衡生成质量与多样性。本章将深入探讨排序算法在深度学习系统中的具体