堆排序：堆排序如何實現？時間複雜度詳解
堆排序是利用“堆”（特殊完全二叉樹）實現的排序算法，常用大頂堆（父節點≥子節點）。核心思想是“先建堆，再排序”：先將數組轉爲大頂堆（堆頂爲最大值），再反覆交換堆頂與末尾元素，調整剩餘元素爲堆，完成排序。 堆的基本概念：完全二叉樹結構，數組中索引i的左子節點2i+1、右子節點2i+2、父節點(i-1)//2。大頂堆父≥子，小頂堆父≤子。 實現分兩步：1.構建大頂堆：從最後非葉子節點開始，通過“堆化”（比較父與子節點，交換最大值並遞歸調整子樹）確保大頂堆性質；2.排序：交換堆頂與未排序末尾元素，縮小堆規模後重復堆化，直至完成。 時間複雜度：構建堆O(n)，排序過程O(n log n)，總O(n log n)，空間複雜度O(1)（原地排序）。特點是不穩定，適合大規模數據排序。
閱讀全文使用Python實現基數排序算法
基數排序是一種非比較型整數排序算法，核心思想是按數字每一位（從低位到高位）分桶收集。基本步驟：先確定數組中最大數的位數，再從最低位到最高位，對每一位數字進行“分桶”（0-9共10個桶）和“收集”操作，將當前位數字相同的元素放入同一桶，按桶順序收集更新數組，直至所有位處理完畢。Python實現通過循環位數、計算當前位數字分桶並收集，時間複雜度爲O(d×(n+k))（d爲最大數位數，n爲數組長度，k=10），空間複雜度O(n+k)。適合位數少的整數數組，處理負數時可先轉正數排序再恢復符號。
閱讀全文使用Python實現希爾排序算法
希爾排序是插入排序的改進版，通過分組縮小元素間隔，先“粗排”再“精排”提升效率。核心是選擇初始增量（如數組長度的一半），將數組分爲若干組，組內元素間隔爲增量，對每組用插入排序；隨後增量減半，重複分組排序，直至增量爲1時完成“精排”。 其關鍵邏輯是通過分組減少元素移動次數：初始分組大（元素間隔大），先讓數組基本有序；逐步縮小增量，最終以插入排序收尾。時間複雜度平均爲O(n log n)，最壞O(n²)，空間複雜度O(1)，適用於中等規模、元素分佈不均的數組，是原地排序的高效算法。
閱讀全文撲克牌排序啓示：插入排序的生活類比與實現
這篇文章介紹了插入排序算法。核心思想是逐步構建有序序列：默認首個元素已排序，從第二個元素起，將每個元素（待插入元素）插入到前面已排序序列的正確位置（需移動較大元素騰出空間）。以數組`[5,3,8,4,2]`爲例，演示了從後往前比較、移動元素的過程，關鍵步驟爲：遍歷數組，暫存待插入元素，移動已排序元素，插入位置。 算法特點：優點是簡單直觀、原地排序（空間複雜度O(1)）、穩定且適合小規模或近乎有序數據；缺點是最壞時間複雜度O(n²)，移動操作較多。總結而言，插入排序是理解排序算法的基礎，通過生活類比（如整理撲克牌）幫助理解，適用於簡單場景或小規模數據排序。
閱讀全文