堆排序：堆排序如何实现？时间复杂度详解
堆排序是利用“堆”（特殊完全二叉树）实现的排序算法，常用大顶堆（父节点≥子节点）。核心思想是“先建堆，再排序”：先将数组转为大顶堆（堆顶为最大值），再反复交换堆顶与末尾元素，调整剩余元素为堆，完成排序。 堆的基本概念：完全二叉树结构，数组中索引i的左子节点2i+1、右子节点2i+2、父节点(i-1)//2。大顶堆父≥子，小顶堆父≤子。 实现分两步：1.构建大顶堆：从最后非叶子节点开始，通过“堆化”（比较父与子节点，交换最大值并递归调整子树）确保大顶堆性质；2.排序：交换堆顶与未排序末尾元素，缩小堆规模后重复堆化，直至完成。 时间复杂度：构建堆O(n)，排序过程O(n log n)，总O(n log n)，空间复杂度O(1)（原地排序）。特点是不稳定，适合大规模数据排序。
閱讀全文使用C++實現選擇排序算法
選擇排序是簡單直觀的排序算法，核心思想是每次從待排序元素中選出最小（或最大）元素，將其放入已排序序列末尾，直至完成排序。基本思路分四步：外層循環控制當前待排序起始位置，內層循環在剩餘元素中尋找最小值，交換操作將最小值移至當前起始位置，重複直至所有元素排序完成。 以數組{64,25,12,22,11}爲例，演示過程：i=0時找到最小值11交換到首位，i=1找到12交換到第二位，i=2找到22交換到第三位，i=3無需交換，最終數組排序完成。 C++代碼通過兩層循環實現：外層循環控制位置i，內層循環找最小值索引minIndex，交換arr[i]與arr[minIndex]。時間複雜度O(n²)，空間複雜度O(1)。 選擇排序實現簡單、無需額外空間，適合小規模數據排序，是理解排序算法的基礎。
閱讀全文使用C++實現插入排序算法
插入排序是簡單直觀的排序算法，核心思想是將元素逐個插入到已排序子數組的合適位置（類似整理撲克牌）。基本思路：從第二個元素開始，取當前元素，與前面已排序元素比較，若前面元素更大則後移，直到找到插入位置，插入後繼續處理下一個元素。 實現時，外層循環遍歷元素，內層循環用臨時變量保存當前元素，通過比較移動前面元素騰出位置，最後插入。時間複雜度最壞O(n²)，最好O(n)，空間複雜度O(1)。適用於小規模數據或基本有序數據，優點是穩定、簡單，是理解複雜排序的基礎。
閱讀全文使用Java實現插入排序算法
插入排序是一種簡單直觀的排序算法，核心思想是將未排序元素逐個插入已排序部分的正確位置，類似整理撲克牌。適合小規模數據，實現簡單。 基本思路：從第2個元素開始，將當前元素記爲“待插入元素”，與已排序部分從後往前比較，若已排序元素更大則後移，直至找到插入位置，重複操作直至所有元素處理完畢。 Java實現需保存待插入元素，通過循環比較並後移元素完成插入。算法時間複雜度：最好O(n)（已排序），最壞和平均O(n²)；空間複雜度O(1)（原地排序）；穩定排序，適用於小規模數據或幾乎有序數據。 其核心在於“逐步插入”，實現簡單，穩定性和原地性使其在小規模排序中表現良好。
閱讀全文