排序算法排序算法

按存儲媒體：

内部排序：資料量不大、資料在記憶體無需記憶體外資料交換

外部排序：資料量較大，資料在硬碟（檔案排序）

按比較器個數：

串行排序：單處理器（同一時刻比較一個元素）

并行排序：多處理器（同一時刻比較多個元素）

按主要操作：

比較排序：主要操作為比較（如插入排序、交換排序、選擇排序等）

基數排序：不比較元素的大小，僅根據元素本身取值确定位置

按輔助空間：

原地排序：空間複雜度o(1)

非原地排序：空間複雜度超過o(1)

按穩定性：

穩定排序：能夠使任何數值相等的元素，排序後相對次序不變

非穩定排序：不是穩定排序的排序

按自然性：

自然排序：輸入資料越有序，排序的速度越快

非自然排序：不是自然排序的排序

以順序表存儲待排序的資料

每一步将一個待排序的對象，按其關鍵碼大小，插入到前面已經排好序的一組對象的适當位置上，直到對象全部插入為止

找插入位置 ---> 移動原元素 ---> 插入

以順序法查找插入位置

算法思想：

複制插入元素 記錄後移，查找插入位置

注：可借助“哨兵arr[0]”

時間複雜度：o(n^2)

空間複雜度：o(1)

穩定性：穩定

以折半查找法查找插入位置

算法思想同上，折半查找部分見“查找”章節

性能分析：

相較于直接插入排序，折半插入排序減少了比較次數，但沒有減少移動次數，平均性能由于直接插入排序

先将整個待排序的記錄分割為若幹子序列，分别進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序

特點：

縮小增量

多遍插入排序

希爾排序的性能與其增量序列有關，暫無定論

穩定性：不穩定

兩兩比較，若發生逆序則交換，直到所有記錄都排好序為止

每趟不斷将記錄兩兩比較，并按照“前小後大”的順序進行交換

确定中心元素pivot的位置：小于pivot的元素放在其前面，大于pivot的元素放在其後面

再對每個左表和右表進行上述操作，直到每個子表的元素個數為1

取左第一個元素為pivot并存儲，并設定兩個指針low、high 先令arr[high]和pivot比較，若小則将arr[high]指派給arr[low]，并開始從low方向向後比較pivot，若大則指派給arr[high]，再次交換順序并比較，直到 low == high 按2的方法可确定pivot的位置，而被pivot切分的左右子表可再進行查詢其自身的中心元素，直到每個子表隻剩下一個元素

時間複雜度：o(nlogn)

空間複雜度：o(logn)（遞歸）

自然性：非自然

在待排序的資料中選出最大（小）的元素放在其最終的位置

堆的定義：

小根堆：左右孩子大于根的完全二叉樹

大根堆：左右孩子小于根的完全二叉樹

基本思想：

由于堆頂元素大于（小于）左右孩子，故可得到最大值（最小值），再将剩餘元素重新組成堆，得到次大（小）值，以此類推，實作排序

算法思想（以小根堆為例）：

輸出堆頂元素之後，以堆中的最後一個元素代替之 然後将根結點值與左、右子樹的根結點值進行比較，并與其中小者進行交換 重複上述操作，直至葉子結點，将得到新的堆，稱這個堆頂至葉子的調整過程為“篩選”

單結點的二叉樹是堆；在完全二叉樹中所有以葉子結點（序号 i > n/2）為根的子樹是堆

隻需将序号為n/2，n/2 - 1，...，1的結點為根的子樹均調整為堆即可

調整從第n/2個元素開始，将以該元素為根的二叉樹調整為堆 依次往上調整，直到n/2為1時結束

基本思想：将兩個或兩個以上的有序子序列“歸并”為一個有序序列

關鍵問題：如何将兩個有序序列合并為一個有序序列？

解決方案：

設定兩個指針分别指向兩個線性表，比較兩指針指向的元素大小，取較大（小）值并向後移動該指針繼續比較，直到其中一個指針超出線性表長度，則複制另一個指針的線性表的剩餘元素

空間複雜度：o(n)

基本思想：配置設定+收集

配置設定：将關鍵字k的記錄放入第k個箱子 收集：按序号将非空的連接配接

時間複雜度：o(k * (n + m))（k為關鍵字個數，m為桶個數）

空間複雜度：o(m + n)