C语言数据结构系列堆排序篇C语言数据结构系列二十二堆排序——原地排序一、前言二、堆排序2.1 思想2.2 步骤2.3 代码实现三、复杂度分析四、下篇预告C语言数据结构系列二十二堆排序——原地排序本篇目标掌握堆排序的原理与实现摘要堆排序是一种基于堆数据结构的原地比较排序算法。本文介绍其核心思想——建大顶堆后反复交换堆顶与末尾元素并给出 C 语言实现时间复杂度 O(nlogn)空间复杂度 O(1)属于不稳定排序。一、前言哈喽小伙伴们今天我们来学习堆排序Heap Sort——利用堆结构进行排序二、堆排序2.1 思想建大顶堆然后依次将堆顶最大值与末尾交换2.2 步骤建大顶堆交换堆顶和末尾调整堆重复直到有序2.3 代码实现voidheapify(intarr[],intn,inti){intlargesti;intleft2*i1;intright2*i2;if(leftnarr[left]arr[largest])largestleft;if(rightnarr[right]arr[largest])largestright;if(largest!i){inttemparr[i];arr[i]arr[largest];arr[largest]temp;heapify(arr,n,largest);}}voidheapSort(intarr[],intn){for(intin/2-1;i0;i--)heapify(arr,n,i);for(intin-1;i0;i--){inttemparr[0];arr[0]arr[i];arr[i]temp;heapify(arr,i,0);}}三、复杂度分析时间空间稳定性O(nlogn)O(1)❌四、下篇预告下一篇我们将学习非比较排序计数、基数、桶 堆排序是原地排序不需要额外空间