《算法與數(shù)據(jù)結(jié)構(gòu)》第8章排序及基本算法ppt151

《《算法與數(shù)據(jù)結(jié)構(gòu)》第8章排序及基本算法ppt151》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》第8章排序及基本算法ppt151（151頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、算 法 與 數(shù) 據(jù) 結(jié) 構(gòu)第 8章 排 序 及 基 本 算 法 排 序 及 基 本 算 法n為 了 便 于 檢 索 ， 人 們 通 常 希 望 能 在 計(jì) 算 機(jī) 中 保 存 的 數(shù) 據(jù) 是按 關(guān) 鍵 字 值 大 小 排 列 的 有 序 表 。n這 是 因 為 對(duì) 于 有 序 表 可 以 采 用 檢 索 效 率 較 高 的 二 分 法 檢 索算 法 ， 其 平 均 檢 索 長(zhǎng) 度 為 log2(n+1)-1;而 對(duì) 于 無(wú) 序 表 只 能 進(jìn)行 順 序 檢 索 ， 其 平 均 檢 索 長(zhǎng) 度 為 (n+1)/2。n又 如 為 了 方 便 檢 索 ， 需 要 構(gòu) 造 二 叉 檢 索 樹(shù) 、 B樹(shù)

2、 和 B+樹(shù) 等 樹(shù)表 ， 構(gòu) 造 這 些 樹(shù) 表 的 過(guò) 程 本 身 就 是 一 個(gè) 排 序 的 過(guò) 程 。 n在 現(xiàn) 今 的 計(jì) 算 機(jī) 系 統(tǒng) 中 ， 有 相 當(dāng) 大 的 一 部 分 CPU時(shí) 間 開(kāi) 銷(xiāo)是 用 于 對(duì) 數(shù) 據(jù) 的 排 序 整 理 上 的 。n因 此 ， 學(xué) 習(xí) 和 研 究 各 種 排 序 算 法 ， 分 析 并 設(shè) 計(jì) 出 高 效 適 用的 排 序 算 法 ， 是 擺 在 計(jì) 算 機(jī) 科 學(xué) 工 作 者 面 前 的 重 要 課 題 之一 。 第 8章 排 序 及 基 本 算 法8.1 排 序 的 基 本 概 念8.2 插 入 排 序8.3 交 換 排 序8.4 選 擇

3、排 序8.5 歸 并 排 序8.6 基 數(shù) 排 序8.7 各 種 內(nèi) 部 排 序 方 法 的 比 較 和 選 擇8.8 外 部 排 序 簡(jiǎn) 介 8.1 排 序 的 基 本 概 念 n 排 序 是 數(shù) 據(jù) 處 理 中 的 重 要 運(yùn) 算 ， 其 功 能 是 將 一 組數(shù) 據(jù) 元 素 （ 或 記 錄 ） 的 任 意 序 列 ， 經(jīng) 重 新 排 列 整 理成 為 按 關(guān) 鍵 字 值 大 小 有 序 的 序 列 。n 排 序 的 實(shí) 際 應(yīng) 用 領(lǐng) 域 也 是 非 常 廣 泛 的 。 例 如 在 實(shí)際 問(wèn) 題 的 數(shù) 據(jù) 處 理 中 常 會(huì) 遇 到 這 樣 的 情 況 ， 需 要 把若 干 名 字 如

4、 人 名 、 地 名 、 國(guó) 名 、 書(shū) 名 、 校 名 、 物 名等 按 字 母 順 序 列 表 ； 需 要 把 若 干 數(shù) 值 如 各 種 考 試 分?jǐn)?shù) 、 田 賽 的 長(zhǎng) 度 、 徑 賽 的 時(shí) 間 等 按 成 績(jī) 次 序 排 名 ；需 要 把 若 干 不 同 屬 性 的 記 錄 按 照 某 種 方 法 排 列 次序 。 所 有 這 些 都 是 排 序 問(wèn) 題 ， 都 需 要 把 一 組 數(shù)據(jù) 元 素 或 記 錄 按 照 某 種 特 定 的 次 序 排 列 起 來(lái) 。 排 序 的 基 本 概 念 （ 續(xù) ） n 排 序 的 確 切 定 義 可 以 描 述 為 ：n設(shè) （ R1， R2 R

5、n） 是 某 文 件 的 n個(gè) 記 錄 ， 其 相 應(yīng) 的 關(guān) 鍵字 為 （ K1， K2 Kn） 。n排 序 （ sort） 是 這 樣 一 種 操 作 ， 它 確 定 文 件 中 n個(gè) 記 錄的 一 種 排 列 （ Rj1， Rj2 Rjn） ， 使 得 其 相 應(yīng) 關(guān) 鍵 字 滿 足遞 增 （ 即 不 減 ） 關(guān) 系 Kj1Kj2Kjn或 遞 減 （ 即 不 增 ） 關(guān)系 Kj1Kj2Kjn。 n若 關(guān) 鍵 字 滿 足 遞 增 （ 即 不 減 ） 關(guān) 系 時(shí) ， 稱 作 按 關(guān) 鍵 字 升序 排 序 (ascending sort)；n若 關(guān) 鍵 字 滿 足 遞 減 （ 即 不 增 ）

6、關(guān) 系 時(shí) ， 稱 作 按 關(guān) 鍵 字 降序 排 序 (descending sort)。 排 序 的 基 本 概 念 （ 續(xù) ） n在 前 面 定 義 中 ， 關(guān) 鍵 字 Ki(i=1， 2 n)稱 作 排 序碼 （ sort code） 。n排 序 碼 可 以 是 記 錄 的 主 關(guān) 鍵 字 ， 也 可 以 是 次 關(guān) 鍵字 ， 或 者 是 多 個(gè) 關(guān) 鍵 字 的 組 合 （ 即 組 合 關(guān) 鍵 字 ） 。n當(dāng) 排 序 碼 是 主 關(guān) 鍵 字 時(shí) ， 由 于 主 關(guān) 鍵 字 可 以 惟 一標(biāo) 識(shí) 一 個(gè) 記 錄 ， 所 以 排 序 結(jié) 果 是 惟 一 的 。n當(dāng) 排 序 碼 是 次 關(guān) 鍵

7、 字 時(shí) ， 同 一 關(guān) 鍵 字 值 可 能 標(biāo) 識(shí)了 兩 個(gè) 或 兩 個(gè) 以 上 的 記 錄 ， 所 以 排 序 結(jié) 果 不 惟 一 。 排 序 的 基 本 概 念 （ 續(xù) ） n若 相 同 關(guān) 鍵 字 值 的 記 錄 在 排 序 前 后 的 相 對(duì) 位 置 不會(huì) 發(fā) 生 改 變 ， 即 若 Ri與 Rj的 關(guān) 鍵 字 相 同 （ Ki=Kj） 且在 排 序 前 Ri在 Rj之 前 ， 排 序 后 的 Ri仍 在 Rj之 前 ， 則稱 所 用 的 排 序 算 法 是 穩(wěn) 定 的 (stable)；n否 則 ， 若 排 序 前 后 相 同 關(guān) 鍵 字 值 的 記 錄 其 相 對(duì) 位置 可 能

8、發(fā) 生 改 變 ， 即 排 序 之 后 的 序 列 中 有 可 能 出現(xiàn) Rj在 Ri之 前 的 情 況 ， 則 稱 所 用 的 排 序 算 法 是 不 穩(wěn)定 的 。 n當(dāng) 排 序 碼 是 組 合 關(guān) 鍵 字 時(shí) ， 通 常 稱 作 多 關(guān) 鍵 字 排序 ， 其 排 序 結(jié) 果 的 惟 一 性 取 決 于 組 合 關(guān) 鍵 字 是 否能 惟 一 標(biāo) 識(shí) 一 個(gè) 記 錄 。 排 序 的 分 類(lèi) n根 據(jù) 排 序 過(guò) 程 中 待 排 序 文 件 存 放 的 位 置 不 同 ， 可 以把 排 序 分 為 內(nèi) 部 和 外 部 排 序 兩 大 類(lèi) 。n內(nèi) 部 排 序 是 指 待 排 序 文 件 放 在 內(nèi)

9、 存 中 進(jìn) 行 排 序的 排 序 ； 內(nèi) 部 排 序 適 用 于 記 錄 個(gè) 數(shù) 不 很 多 的 較 小待 排 序 文 件 的 排 序 ；n外 部 排 序 是 指 在 待 排 序 文 件 很 大 時(shí) ， 內(nèi) 存 中 不能 一 次 容 納 全 部 記 錄 ， 還 要 借 助 于 外 存 存 放 待 排序 文 件 ， 在 排 序 過(guò) 程 中 需 要 對(duì) 外 存 進(jìn) 行 訪 問(wèn) 的 排序 ； 外 部 排 序 則 適 用 于 記 錄 個(gè) 數(shù) 太 多 不 能 一 次 全部 放 入 內(nèi) 存 的 較 大 待 排 序 文 件 的 排 序 。 排 序 的 分 類(lèi) （ 續(xù) ） n按 排 序 中 所 用 策 略

10、的 不 同 ：n內(nèi) 部 排 序 通 常 可 以 分 為 插 入 排 序 、 選 擇 排 序 、交 換 排 序 、 歸 并 排 序 和 分 配 排 序 這 五 類(lèi) ， 每 一類(lèi) 中 不 同 的 排 序 算 法 都 是 基 于 同 一 策 略 的 不 同方 法 。n外 部 排 序 多 是 采 用 多 路 歸 并 方 法 進(jìn) 行 排 序 。 內(nèi) 部 排 序 文 件 的 組 織 形 式n 每 種 內(nèi) 部 排 序 方 法 均 可 在 不 同 的 存 儲(chǔ) 結(jié) 構(gòu) 上 實(shí) 現(xiàn) 。通 常 待 排 序 文 件 的 組 織 形 式 有 三 種 方 式 ：n以 一 維 數(shù) 組 作 為 組 織 形 式 ， 排 序 過(guò)

11、 程 是 對(duì) 記 錄 本 身 進(jìn)行 物 理 重 排 ， 通 過(guò) 比 較 和 判 定 把 記 錄 移 動(dòng) 到 合 適 的 位 置 ；n以 鏈 表 （ 動(dòng) 態(tài) 鏈 表 或 靜 態(tài) 鏈 表 ） 作 為 組 織 形 式 ， 排 序過(guò) 程 中 無(wú) 需 移 動(dòng) 記 錄 ， 僅 需 修 改 指 針 即 可 ， 通 常 把 這 類(lèi)排 序 稱 為 表 排 序 ； n為 待 排 序 文 件 組 織 一 個(gè) 輔 助 表 ， 如 組 織 一 張 含 關(guān) 鍵 字和 指 向 記 錄 指 針 的 索 引 表 ， 在 排 序 過(guò) 程 中 只 需 對(duì) 輔 助 表的 表 目 進(jìn) 行 物 理 重 排 ， 不 需 移 動(dòng) 記 錄 本

12、 身 ， 在 排 序 結(jié) 束后 按 輔 助 表 調(diào) 整 記 錄 位 置 。 排 序 的 基 本 概 念 （ 續(xù) ）n排 序 的 方 法 很 多 ， 每 一 種 方 法 都 有 自 己 的 優(yōu) 缺 點(diǎn) ，適 用 于 在 不 同 的 環(huán) 境 下 使 用 ， 很 難 說(shuō) 哪 一 種 方 法是 最 好 的 方 法 。n由 于 所 需 的 輔 助 空 間 的 量 一 般 都 不 大 ， 所 以 排 序的 時(shí) 間 代 價(jià) 是 衡 量 排 序 算 法 的 最 重 要 的 因 素 。 n內(nèi) 部 排 序 的 時(shí) 間 代 價(jià) 主 要 用 關(guān) 鍵 字 的 比 較 次 數(shù) 和 記 錄的 移 動(dòng) 次 數(shù) 來(lái) 衡 量 ；

13、n而 外 部 排 序 的 時(shí) 間 代 價(jià) 主 要 用 訪 問(wèn) 外 存 儲(chǔ) 器 的 次 數(shù) 來(lái)衡 量 。 排 序 的 基 本 概 念 （ 續(xù) ）n在 本 章 主 要 討 論 內(nèi) 部 排 序 算 法 ， 以 記 錄 數(shù) 組 作 為待 排 序 文 件 的 組 織 形 式 ， 并 假 定 關(guān) 鍵 字 均 為 整 數(shù) ，按 遞 增 次 序 討 論 排 序 算 法 （ 即 討 論 升 序 排 序 問(wèn) 題 ） 。n待 排 序 文 件 中 記 錄 結(jié) 構(gòu) 類(lèi) 型 定 義 如 下 ： typedef struct int key; /*關(guān) 鍵 字*/ elemtype otheritems; /*其它 域*/

14、recordtype /*記 錄 類(lèi) 型 標(biāo) 識(shí) 符*/ 第 8章 排 序 及 基 本 算 法8.1 排 序 的 基 本 概 念8.2 插 入 排 序8.3 交 換 排 序8.4 選 擇 排 序8.5 歸 并 排 序8.6 基 數(shù) 排 序8.7 各 種 內(nèi) 部 排 序 方 法 的 比 較 和 選 擇8.8 外 部 排 序 簡(jiǎn) 介 插 入 排 序n插 入 排 序 的 基 本 方 法 是 ： 每 次 將 一 個(gè) 待 排 序 的 記錄 Ri， 按 其 關(guān) 鍵 字 Ki的 大 小 插 入 到 前 面 已 經(jīng) 排 好 序的 部 分 文 件 中 的 適 當(dāng) 位 置 ， 直 到 全 部 記 錄 插 完 整個(gè)

15、 文 件 已 排 好 序 為 止 。n本 節(jié) 介 紹 的 插 入 排 序 方 法 有 直 接 插 入 排 序 和 希 爾排 序 ； 并 簡(jiǎn) 介 二 分 法 插 入 排 序 、 二 路 插 入 排 序 和共 享 棧 插 入 排 序 。 8.2 插 入 排 序8.2.1 直 接 插 入 排 序8.2.2 希 爾 排 序8.2.3 其 它 插 入 排 序 簡(jiǎn) 介 直 接 插 入 排 序 n直 接 插 入 排 序 （ straight insertion sort） 是 一 種 最 簡(jiǎn)單 的 排 序 方 法 。n它 的 基 本 思 路 是 ：n依 次 把 待 排 序 的 記 錄 逐 個(gè) 插 入 已 排

16、 好 序 的 序 列 中 。n一 開(kāi) 始 ， 第 一 個(gè) 記 錄 是 一 個(gè) 長(zhǎng) 度 為 1的 有 序 序 列 ； n從 第 二 個(gè) 記 錄 起 ， 每 次 用 第 i(i=2， 3 n)個(gè) 記 錄 的 關(guān) 鍵字 Ki與 前 面 有 序 序 列 中 記 錄 的 關(guān) 鍵 字 Ki-1、 Ki-2 K1進(jìn) 行比 較 ， 從 而 找 到 Ki所 在 記 錄 應(yīng) 該 插 入 的 位 置 并 依 次 后 移各 記 錄 后 插 入 之 ， 使 得 有 序 序 列 的 長(zhǎng) 度 加 1；n這 樣 插 入 n-1次 就 會(huì) 得 到 n個(gè) 記 錄 的 有 序 序 列 ， 從 而 完 成整 個(gè) 文 件 的 排 序

17、工 作 。 直 接 插 入 排 序 舉 例n例 如 ， 已 知 待 排 序 文 件 中 記 錄 的 關(guān) 鍵 字 序 列 為 （ 23，48， 32， 107， 86， 75， ， 68） ， 直 接 插 入 排 序 的 過(guò)程 可 示 意 如 下 ： n其 中 ， 方 括 號(hào) 表 示 已 排 好 序 的 序 列 ， i表 示 插 入 第 i個(gè) 記 錄 。 直 接 插 入 排 序 （ 續(xù) ） n 在 插 入 第 i個(gè) 記 錄 時(shí) ， 用 Ki和 前 面 已 排 好 序 記 錄 的 關(guān) 鍵 字比 較 ， 若 Ki小 則 后 移 一 個(gè) 記 錄 ， 直 到 Ki不 小 于 時(shí) 插 入 位 置 找到 了

18、 ， 直 接 插 入 Ki完 成 第 i個(gè) 記 錄 的 插 入 。n由 于 后 移 操 作 會(huì) 覆 蓋 第 i個(gè) 記 錄 ， 在 算 法 描 述 中 可 在 進(jìn) 行第 i個(gè) 記 錄 插 入 之 前 ， 先 保 存 其 于 R0中 再 進(jìn) 行 比 較 后 移 操 作 ；這 個(gè) 附 加 的 R0還 可 起 到 “ 監(jiān) 視 哨 ” 的 作 用 ， 即 當(dāng) Ki小 于 前 面有 序 序 列 中 的 每 一 個(gè) 關(guān) 鍵 字 時(shí) ， 在 和 R0中 關(guān) 鍵 字 （ 它 本 身 ）比 較 時(shí) 不 會(huì) 小 于 ， 既 找 到 了 正 確 的 插 入 位 置 ， 又 避 免 了 循環(huán) 控 制 變 量 的 越 界

19、 檢 查 。 n設(shè) 置 監(jiān) 視 哨 是 一 種 程 序 設(shè) 計(jì) 技 巧 ， 既 使 程 序 控 制 簡(jiǎn) 單 ， 又節(jié) 省 了 測(cè) 試 時(shí) 間 提 高 了 檢 索 效 率 。 直 接 插 入 排 序 的 算 法 描 述 n 直 接 插 入 排 序 的 算 法 描 述 如 下 ： void insertsorting(recordtype R,int n) int i,j; for(i=2;i=n;i+) R0=Ri; j=i-1; while(R0.key R0和 R0=Ri） ,無(wú) 需 記 錄 后 移 ；其 比 較 次 數(shù) 為 n-1次 ， 移 動(dòng) 操 作 次 數(shù) 為 2（ n-1） 次 ，算

20、 法 的 時(shí) 間 復(fù) 雜 度 為 O(n)。 直 接 插 入 排 序 的 算 法 分 析 (續(xù) ) n在 最 壞 的 情 況 下 是 待 排 序 文 件 中 各 記 錄 為 關(guān) 鍵 字 的逆 序 排 列 （ 即 遞 減 序 列 ） ， 每 一 趟 中 需 要 和 前 面 已排 好 序 的 i-1個(gè) 記 錄 以 及 監(jiān) 視 哨 中 R0進(jìn) 行 關(guān) 鍵 字 值的 比 較 ， 即 第 i趟 中 需 進(jìn) 行 i次 比 較 操 作 ；n向 后 移 動(dòng) 次 數(shù) 為 i-1次 ， 加 上 與 監(jiān) 視 哨 之 間 的 兩 次 移動(dòng) ， 第 i趟 需 要 移 動(dòng) 記 錄 i+1次 ； 總 的 比 較 次 數(shù) 為

21、 次 ， 總 的 移 動(dòng) 次 數(shù) 為 次 ， 算法 的 時(shí) 間 復(fù) 雜 度 為 O(n2)。 直 接 插 入 排 序 的 算 法 分 析 (續(xù) ) n若 初 始 文 件 中 各 記 錄 是 隨 機(jī) 排 列 ， 即 關(guān) 鍵 字 的 各 種排 列 的 出 現(xiàn) 概 率 相 同 時(shí) ， 我 們 可 取 上 述 最 好 與 最 壞情 況 的 平 均 值 作 為 比 較 和 移 動(dòng) 的 平 均 次 數(shù) ， 約 為 n2/4,由 此 可 得 直 接 插 入 排 序 的 時(shí) 間 復(fù) 雜 度 為 O(n2)。n由 于 直 接 插 入 排 序 在 整 個(gè) 排 序 過(guò) 程 中 只 需 一 個(gè) 記 錄的 輔 助 空

22、間 （ 即 R0） ， 所 以 其 空 間 復(fù) 雜 度 為 O(1)。由 于 對(duì) 于 相 同 關(guān) 鍵 字 值 的 記 錄 在 排 序 前 后 相 對(duì) 位 置不 會(huì) 發(fā) 生 變 化 （ 如 上 例 中 的 48和 ） ， 所 以 直 接 插 入排 序 是 一 種 穩(wěn) 定 的 排 序 方 法 。 8.2 插 入 排 序8.2.1 直 接 插 入 排 序8.2.2 希 爾 排 序8.2.3 其 它 插 入 排 序 簡(jiǎn) 介 希 爾 排 序n希 爾 排 序 （ shells method） ， 又 稱 作 縮 小 增 量 排 序（ diminishing increatment） 。 它 是 1959年

23、 由 D.L.Shell提 出 來(lái)的 對(duì) 直 接 插 入 排 序 的 一 種 改 進(jìn) 方 法 。n希 爾 排 序 是 不 穩(wěn) 定 的 排 序 算 法 。 n由 直 接 插 入 排 序 的 分 析 可 知 ， 在 待 排 序 文 件 已 按 關(guān) 鍵 字 值遞 增 有 序 時(shí) 的 時(shí) 間 復(fù) 雜 度 為 O(n)， 在 逆 序 時(shí) 的 時(shí) 間 復(fù) 雜 度 為O(n2)。n換 句 話 說(shuō) ， 如 果 待 排 序 文 件 能 夠 基 本 有 序 ， 則 文 件 中 的 大多 數(shù) 記 錄 都 不 需 要 進(jìn) 行 插 入 （ 即 后 移 ） 操 作 ， 整 個(gè) 排 序 的 時(shí)間 開(kāi) 銷(xiāo) 就 可 以 大 大

24、 減 少 。 n另 外 ， 當(dāng) n的 值 很 小 時(shí) ， n2的 值 受 n的 值 的 影 響 也 不 太 大 ， 直接 插 入 排 序 的 效 率 也 比 較 高 。 希 爾 排 序 正 是 基 于 這 兩 點(diǎn) 考 慮而 得 到 的 對(duì) 直 接 插 入 排 序 的 一 種 改 進(jìn) 方 法 。 希 爾 排 序 的 方 法n希 爾 排 序 的 方 法 是 ：n先 選 取 一 個(gè) 小 于 n的 整 數(shù) d1作 為 第 一 個(gè) 增 量 ， 把待 排 序 文 件 中 的 全 部 記 錄 分 成 d1個(gè) 組 ， 將 所 有 距離 為 d1倍 數(shù) 的 記 錄 放 在 同 一 個(gè) 組 中 ， 在 各 組 內(nèi)

25、 進(jìn)行 直 接 插 入 排 序 ；n然 后 選 取 第 二 個(gè) 增 量 d2d1， 重 復(fù) 上 述 的 分 組 和排 序 工 作 ； 如 此 不 斷 地 選 取 更 小 的 增 量 d3，d4 并 重 復(fù) 上 述 的 分 組 和 排 序 工 作 ， n直 到 所 選 取 增 量 di=1(didi-1d2d1)時(shí) 所 有 記錄 放 在 同 一 組 中 進(jìn) 行 直 接 插 入 排 序 后 為 止 。 希 爾 排 序 的 方 法 （ 續(xù) ）n希 爾 排 序 方 法 的 一 開(kāi) 始 組 數(shù) 較 多 而 組 中 記 錄 較 少 ， 各 組 中記 錄 的 直 接 插 入 排 序 是 處 在 n值 很 小

26、 的 情 況 下 進(jìn) 行 ， 有 著 較高 的 效 率 ； 并 且 在 不 滿 足 次 序 時(shí) 的 移 動(dòng) ， 是 用 較 少 的 移 動(dòng) 次數(shù) 而 得 到 了 記 錄 的 較 大 移 動(dòng) 距 離 。n隨 著 di減 小 ， 組 數(shù) 變 少 組 中 記 錄 個(gè) 數(shù) 變 多 的 同 時(shí) ， 組 中 記 錄也 逐 步 變 得 基 本 有 序 ， 使 得 在 一 趟 中 進(jìn) 行 直 接 插 入 排 序 時(shí) 的效 率 大 大 地 提 高 。n所 以 希 爾 排 序 始 終 是 在 較 高 的 效 率 下 工 作 。 希 爾 排 序 中 增量 di的 選 擇 可 以 有 不 同 的 取 法 ， 一 般

27、是 采 用 希 爾 在 最 早 時(shí) 提出 的 方 法 ， 即 d1=,di+1=(i=2， 3， 4 )。 n但 也 有 人 提 出 不 同 的 di選 取 方 法 ， 如 克 努 特 （ Knuth） 提 出的 方 法 是 d1=,di+1=(i=2， 3， 4 )。 如 何 選 取 增 量 序 列 才 能 產(chǎn)生 最 好 的 排 序 效 果 ， 至 今 仍 無(wú) 法 從 數(shù) 學(xué) 角 度 得 出 圓 滿 的 結(jié) 論 ；然 而 逐 步 縮 小 增 量 和 最 后 一 次 增 量 為 1是 大 家 不 爭(zhēng) 的 事 實(shí) 。 希 爾 排 序 舉 例n設(shè) 待 排 序 文 件 中 有 10個(gè) 記 錄 ， 初

28、 始 關(guān) 鍵 字 序列 為 (52,38,66,87,77,16,30,62,07)， 增 量 序 列 依次 為 5,3,1， 排 序 過(guò) 程 如 下 ： 希 爾 排 序 舉 例 （ 續(xù) ） 希 爾 排 序 舉 例 （ 續(xù) ）n第 一 趟 排 序 時(shí) d1=5， 把 待 排 序 文 件 分 成 五 組 ， 即（ R1， R6） 、 （ R2， R7） 、 （ R3， R8） 、 （ R4， R9）和 （ R5， R10） ， 各 組 中 第 一 個(gè) 記 錄 都 自 成 長(zhǎng) 度 為 1的有 序 區(qū) ， 依 次 把 各 組 的 第 二 個(gè) 記 錄 插 入 有 序 區(qū) 中 得 到第 一 趟 排 序

29、結(jié) 果 ；n第 二 趟 排 序 時(shí) d2=3， 把 待 排 序 文 件 分 成 三 組 ， 即（ R1， R4， R7， R10） 、 （ R2， R5， R8） 和 （ R3， R6，R9） ， 對(duì) 各 組 進(jìn) 行 直 接 插 入 排 序 后 得 到 第 二 趟 排 序 結(jié)果 ； n第 三 趟 排 序 時(shí) d3=1， 整 個(gè) 待 排 序 文 件 為 一 組 ， 對(duì) 整個(gè) 文 件 做 直 接 插 入 排 序 得 到 的 第 三 趟 排 序 結(jié) 果 ， 使 整個(gè) 待 排 序 文 件 按 關(guān) 鍵 字 值 有 序 ， 即 得 到 最 終 的 排 序 結(jié)果 。 希 爾 排 序 的 算 法 描 述 (不

30、 設(shè) 置 監(jiān) 視 哨 )n 若 不 設(shè) 置 監(jiān) 視 哨 ， 希 爾 排 序 的 算 法 可 描 述 如 下 ： void shellsorting(recordtype R,int n) int i,j,d; d = n; do d = (d+1)/2; for(i = d+1;i d) /*shellsorting end*/ 希 爾 排 序 （ 續(xù) ）n需 要 說(shuō) 明 的 是 ， 算 法 中 沒(méi) 有 調(diào) 用 直 接 插 入 排 序 算 法insertsorting， 而 是 獨(dú) 立 設(shè) 計(jì) 直 接 插 入 排 序 的 部 分 ； 這是 因 為 希 爾 排 序 中 距 離 為 d的 倍 數(shù)

31、的 記 錄 為 一 組 ， 組中 成 員 記 錄 之 間 有 間 隔 不 連 續(xù) 不 能 直 接 調(diào) 用 的 緣 故 。n另 外 ， 在 for循 環(huán) 中 的 分 組 執(zhí) 行 直 接 插 入 排 序 的 過(guò) 程 ，是 依 次 先 插 入 d個(gè) 組 中 的 第 二 個(gè) 記 錄 ， 再 插 入 d個(gè) 組 中的 第 三 個(gè) 記 錄 最 后 插 入 d個(gè) 組 中 的 最 后 一 個(gè) 記 錄 ；是 d個(gè) 組 的 交 替 插 入 過(guò) 程 ， 而 不 是 一 個(gè) 組 的 直 接 插 入排 序 完 成 后 再 進(jìn) 行 下 一 組 ， 這 樣 有 利 于 算 法 設(shè) 計(jì) 的 簡(jiǎn)潔 性 和 算 法 描 述 的 方

32、 便 性 。 希 爾 排 序 （ 續(xù) ）n 如 果 考 慮 設(shè) 置 監(jiān) 視 哨 ， 很 自 然 地 會(huì) 考 慮 到 仿 照 直 接 插 入 排 序算 法 中 的 監(jiān) 視 哨 設(shè) 置 辦 法 。 對(duì) 于 增 量 為 d的 一 趟 希 爾 排 序 ， 待排 序 文 件 被 分 成 d 組 ， 各 組 中 記 錄 之 間 的 距 離 為 d； 需 要 在 R1到 Rd處 設(shè) 置 監(jiān) 視 哨 ， 而 在 Rd+1到 Rd+n處 安 排 待 排 序 文 件中 的 n個(gè) 記 錄 。 由 于 在 各 趟 排 序 中 的 增 量 d1,d2 di是 逐 次 縮 小的 ， 而 待 排 序 文 件 中 各 記 錄

33、 的 位 置 空 間 安 排 好 之 后 不 宜 變 動(dòng)（ 移 動(dòng) 需 時(shí) 間 開(kāi) 銷(xiāo) ） ， 所 以 d可 選 為 di中 的 最 大 值 d1， 即 一 次 性安 排 監(jiān) 視 哨 空 間 并 固 定 不 變 ；n另 外 ， 監(jiān) 視 哨 中 的 值 應(yīng) 在 不 同 組 中 的 不 同 記 錄 插 入 時(shí) 安 排 不同 的 值 （ 即 待 插 入 記 錄 的 值 ） ， 但 是 多 次 更 換 監(jiān) 視 哨 中 的 值 既繁 瑣 又 影 響 效 率 ， 我 們 可 以 考 慮 在 排 序 之 前 一 次 性 設(shè) 置 各 監(jiān) 視哨 的 值 ， 可 設(shè) 置 為 不 超 過(guò) 待 排 序 文 件 中 最

34、 小 關(guān) 鍵 字 值 的 某 一 個(gè)值 如 -maxint。 這 種 監(jiān) 視 哨 的 設(shè) 置 方 法 ， 沒(méi) 有 在 監(jiān) 視 哨 中 保 存各 組 中 的 一 個(gè) 個(gè) 待 插 入 記 錄 ， 但 可 以 統(tǒng) 一 保 存 待 插 入 記 錄 于R0中 。 希 爾 排 序 的 算 法 描 述 (設(shè) 置 監(jiān) 視 哨 )n 設(shè) 置 監(jiān) 視 哨 的 希 爾 排 序 算 法 可 描 述 如 下 ： void shellsort(recordtype R,int n) int i,j,d; for(i=1;i=(n+1)/2;i+) Ri.key = -maxint; d = n; do d = (d+1)

35、/2; for(i=2*d+1;i=d+n;i+) j = i; R0 = Rj; while(R0.key 1); /*shellsort end*/ 希 爾 排 序 的 算 法 分 析n在 前 面 給 出 的 兩 個(gè) 算 法 ， 除 了 是 否 設(shè) 置 監(jiān) 視 哨 外 ， 排序 的 方 法 是 相 同 的 ， 其 時(shí) 間 復(fù) 雜 度 也 是 相 同 的 ； 其 增量 序 列 為 d1= ， di= (i2)。 算 法 中 的 主 要 時(shí) 間開(kāi) 銷(xiāo) 在 于 三 重 循 環(huán) ：n外 層 do-while循 環(huán) 控 制 排 序 趟 數(shù) ， 共 執(zhí) 行 log2n次 。n中 層 的 for循 環(huán)

36、控 制 一 趟 中 各 組 記 錄 的 直 接 插 入 排 序 ， 執(zhí) 行次 數(shù) 依 次 為 次 ； 其 平 均 次 數(shù) 為 ； 即中 層 for循 環(huán) 的 平 均 執(zhí) 行 次 數(shù) 不 超 過(guò) n。 n內(nèi) 層 的 while循 環(huán) 確 定 各 組 中 每 個(gè) 記 錄 的 插 入 位 置 ， 進(jìn) 行 關(guān)鍵 字 的 比 較 和 記 錄 的 移 動(dòng) 操 作 ； 希 爾 排 序 的 算 法 分 析 （ 續(xù) ）n在 最 好 的 情 況 下 只 執(zhí) 行 一 次 比 較 而 無(wú) 記 錄 移 動(dòng) ， 其 一 趟 中總 的 比 較 次 數(shù) 與 中 層 f o r 循 環(huán) 的 執(zhí) 行 次 數(shù) 相 同 ，為 ；n而

37、 一 趟 中 執(zhí) 行 插 入 的 次 數(shù) 為 n-di， 即 平 均 比 較 次 數(shù) 不 超過(guò) ,更 不 會(huì) 超 過(guò) log2n次 ；n由 于 希 爾 排 序 算 法 中 開(kāi) 始 時(shí) 兩 個(gè) 記 錄 一 組 ， 以 后 隨 著 組 數(shù)的 減 少 組 中 記 錄 增 多 也 逐 步 基 本 有 序 ， 所 以 在 n較 大 時(shí) 的 其它 情 況 下 的 平 均 比 較 次 數(shù) 也 是 接 近 于 最 好 情 況 下 的 次 數(shù) log2n或 是 它 的 線 性 函 數(shù) ， 而 移 動(dòng) 次 數(shù) 或 平 均 移 動(dòng) 次 數(shù) 是 遠(yuǎn) 遠(yuǎn) 小 于比 較 次 數(shù) 和 平 均 比 較 次 數(shù) 的 ； n由

38、此 得 內(nèi) 層 while循 環(huán) 的 平 均 執(zhí) 行 次 數(shù) 為 O(log2n)階 函 數(shù) 。 由算 法 分 析 的 乘 法 法 則 可 知 ， 前 面 給 出 的 兩 個(gè) 希 爾 排 序 算 法 ，shellsorting和 shellsort的 時(shí) 間 復(fù) 雜 度 為 O(n(log2n)2)。 8.2 插 入 排 序8.2.1 直 接 插 入 排 序8.2.2 希 爾 排 序8.2.3 其 它 插 入 排 序 簡(jiǎn) 介 1.二 分 法 插 入 排 序 n 由 第 七 章 的 討 論 我 們 知 道 ， 對(duì) 有 序 表 采 用 二 分 法 檢 索 ， 檢索 性 能 大 大 優(yōu) 于 順 序

39、檢 索 。n如 果 我 們 把 直 接 插 入 排 序 中 的 由 后 向 前 順 序 檢 索 尋 找 插 入位 置 的 方 法 改 為 用 二 分 法 檢 索 來(lái) 實(shí) 現(xiàn) ， 當(dāng) n較 大 時(shí) 就 可 以 大幅 度 地 降 低 關(guān) 鍵 字 的 比 較 次 數(shù) 。 我 們 把 經(jīng) 過(guò) 這 種 改 進(jìn) 后 的 插入 排 序 方 法 ， 稱 作 二 分 法 插 入 排 序 （ binary insertion sort） 。n二 分 法 插 入 排 序 與 直 接 插 入 排 序 相 比 較 ， 僅 是 減 少 了 尋 找插 入 位 置 時(shí) 的 關(guān) 鍵 字 比 較 次 數(shù) ， 記 錄 的 移 動(dòng)

40、次 數(shù) 沒(méi) 有 改 變 ，其 時(shí) 間 復(fù) 雜 度 仍 為 O(n 2)；n所 需 的 輔 助 存 儲(chǔ) 空 間 也 與 直 接 插 入 排 序 相 同 ， 也 是 穩(wěn) 定 的排 序 方 法 （ 在 檢 索 位 置 出 現(xiàn) 關(guān) 鍵 字 值 相 等 時(shí) 需 后 移 插 入 位 置指 示 器 變 量 ， 否 則 為 不 穩(wěn) 定 方 法 ） 。 2.二 路 插 入 排 序 n二 路 插 入 排 序 （ 2-way insertion sort） 是 在 二 分 法 插 入 排 序基 礎(chǔ) 上 的 進(jìn) 一 步 改 進(jìn) ， 改 進(jìn) 的 目 標(biāo) 是 減 少 排 序 過(guò) 程 中 記 錄 的移 動(dòng) 次 數(shù) ， 但

41、為 此 多 開(kāi) 銷(xiāo) 了 n個(gè) 記 錄 大 小 的 輔 助 存 儲(chǔ) 空 間 。n其 具 體 方 法 是 ：n另 設(shè) 一 個(gè) 和 R同 類(lèi) 型 的 數(shù) 組 S， 先 將 R1賦 給 S1， 并 將S1看 成 是 在 已 排 好 序 序 列 中 處 于 中 間 位 置 的 記 錄 ；n然 后 從 R中 第 二 個(gè) 記 錄 起 ， 依 次 插 入 到 S1之 前 或 S1之后 的 有 序 序 列 中 去 ， n若 待 插 記 錄 的 關(guān) 鍵 字 小 于 S1.key則 插 入 S1之 前 的 有 序表 中 ， 否 則 插 入 S1之 后 的 有 序 表 中 。n在 算 法 實(shí) 現(xiàn) 時(shí) ， 把 S數(shù) 組

42、 看 成 是 一 個(gè) 循 環(huán) 數(shù) 組 ， 并 設(shè) 兩 個(gè) 指針 first和 final分 別 指 示 排 序 過(guò) 程 中 得 到 的 有 序 序 列 中 的 第 一個(gè) 記 錄 和 最 后 一 個(gè) 記 錄 在 S中 的 位 置 。 二 路 插 入 排 序 舉 例 二 路 插 入 排 序 舉 例 （ 續(xù) ） 二 路 插 入 排 序 （ 續(xù) ） n在 二 路 插 入 排 序 中 ， 記 錄 的 移 動(dòng) 次 數(shù) 約 為 n2/8， 比直 接 插 入 排 序 減 少 移 動(dòng) 次 數(shù) 約 一 半 。 它 只 能 減 少 移動(dòng) 次 數(shù) 而 不 能 絕 對(duì) 避 免 移 動(dòng) 記 錄 ， 若 要 大 幅 度 降

43、 低移 動(dòng) 次 數(shù) ， 可 改 變 存 儲(chǔ) 結(jié) 構(gòu) 為 靜 態(tài) 鏈 表 ， 進(jìn) 行 表 插入 排 序 。n此 外 ， 二 路 插 入 排 序 中 ， 當(dāng) R1為 待 排 序 文 件 中 最小 或 最 大 關(guān) 鍵 字 的 記 錄 時(shí) ， 完 全 失 去 優(yōu) 越 性 退 化 為直 接 插 入 排 序 的 時(shí) 間 效 率 。 n二 路 插 入 排 序 ， 是 一 種 穩(wěn) 定 的 排 序 方 法 。 3.共 享 棧 插 入 排 序 n共 享 棧 插 入 排 序 （ shared stack insertion sort）也 是 對(duì) 直 接 插 入 排 序 的 一 種 改 進(jìn) 方 法 。n其 基 本 思

44、 想 是 ：n把 待 排 序 的 記 錄 數(shù) 組 R看 作 是 一 個(gè) 靜 態(tài) 的 共 享 棧 （ 棧 1和棧 2） ， 棧 1按 數(shù) 組 下 標(biāo) 由 小 到 大 方 向 增 長(zhǎng) ， 棧 2按 數(shù) 組 下標(biāo) 由 大 到 小 方 向 增 長(zhǎng) ； 棧 1中 按 關(guān) 鍵 字 升 序 排 列 壓 入 待 排序 記 錄 ， 棧 2中 按 關(guān) 鍵 字 降 序 排 列 壓 入 待 排 序 記 錄 。 n一 開(kāi) 始 先 比 較 R1和 Rn的 關(guān) 鍵 字 值 大 小 ， 若 R1Rn則 交 換 ； top1=1,top2=n；n然 后 把 R2到 Rn-1逐 一 插 入 兩 個(gè) 棧 中 ， 插 入 的 過(guò) 程

45、 中始 終 保 證 棧 1的 棧 頂 記 錄 的 關(guān) 鍵 字 值 都 不 大 于 棧 2 的 棧 頂記 錄 的 關(guān) 鍵 字 值 。 共 享 棧 插 入 排 序 （ 續(xù) ）n為 此 需 要 區(qū) 分 以 下 三 種 情 況 并 作 相 應(yīng) 處 理 ：n當(dāng) 待 插 入 記 錄 Ri的 關(guān) 鍵 字 值 不 小 于 棧 1 的 棧 頂 記 錄 的 關(guān)鍵 字 值 且 不 大 于 棧 2的 棧 頂 記 錄 的 關(guān) 鍵 字 值 時(shí) ， 將 待 插 記 錄壓 入 棧 1 中 。 即 R i . k e y R t o p 1 . k e y 且Ri.keyRtop2.key時(shí) 進(jìn) 棧 1， 只 須 改 變 to

46、p1的 值 為top1+1即 可 。n當(dāng) Ri.keytop2.key時(shí) ， 由 棧 2反 復(fù) 傳 送 記 錄 到 棧 1，直 到 Ri.keytop2.key時(shí) 將 Ri插 入 棧 2。 由 棧 2傳 送 到棧 1一 個(gè) 記 錄 ， 需 要 把 Ri+1到 Rtop2-1的 記 錄 后 移 一 個(gè)位 置 。 共 享 棧 插 入 排 序 舉 例 共 享 棧 插 入 排 序 舉 例 （ 續(xù) ） 共 享 棧 插 入 排 序 （ 續(xù) ）n共 享 棧 插 入 排 序 不 需 要 增 加 額 外 的 存 儲(chǔ) 開(kāi) 銷(xiāo) ， 在 時(shí)間 性 能 上 與 二 路 插 入 排 序 相 當(dāng) ， 而 且 有 效 地 避

47、 免 了因 R1為 待 排 序 記 錄 中 關(guān) 鍵 字 值 為 最 大 或 最 小 記 錄時(shí) 完 全 失 去 優(yōu) 越 性 的 不 足 。n若 增 加 存 儲(chǔ) 開(kāi) 銷(xiāo) 另 設(shè) 與 R相 同 類(lèi) 型 的 數(shù) 組 作 為 共 享?xiàng)?， 則 可 以 進(jìn) 一 步 減 少 移 動(dòng) 次 數(shù) ， 且 排 序 結(jié) 果 不 象二 路 插 入 排 序 那 樣 要 使 用 循 環(huán) 數(shù) 組 解 釋 。n共 享 棧 插 入 排 序 是 一 種 穩(wěn) 定 的 排 序 方 法 。 第 8章 排 序 及 基 本 算 法8.1 排 序 的 基 本 概 念8.2 插 入 排 序8.3 交 換 排 序8.4 選 擇 排 序8.5 歸

48、并 排 序8.6 基 數(shù) 排 序8.7 各 種 內(nèi) 部 排 序 方 法 的 比 較 和 選 擇8.8 外 部 排 序 簡(jiǎn) 介 交 換 排 序n交 換 排 序 的 基 本 方 法 是 ， 兩 兩 比 較 待 排 序 記 錄的 關(guān) 鍵 字 值 ， 并 交 換 那 些 不 滿 足 順 序 要 求 的 記 錄對(duì) ， 直 到 全 部 待 排 序 記 錄 都 已 滿 足 順 序 要 求 時(shí) 為止 。n本 節(jié) 介 紹 兩 種 交 換 排 序 的 方 法 ：n一 種 是 冒 泡 排 序 ， n一 種 是 快 速 排 序 。 8.3 交 換 排 序8.3.1 冒 泡 排 序8.3.2 快 速 排 序 冒 泡 排

49、 序n冒 泡 排 序 （ bubble sort） 也 稱 作 起 泡 排 序 ， 是一 種 簡(jiǎn) 單 的 排 序 方 法 。n它 是 通 過(guò) 相 鄰 記 錄 之 間 的 關(guān) 鍵 字 比 較 和 記 錄 交 換 ，使 關(guān) 鍵 字 值 較 小 的 記 錄 由 底 部 向 上 移 動(dòng) ， 而 關(guān) 鍵字 值 較 大 的 記 錄 由 頂 部 向 下 移 動(dòng) ， 就 象 水 中 的 氣泡 向 上 飄 浮 （ 冒 泡 ） 一 樣 。 冒 泡 排 序 算 法n冒 泡 排 序 的 具 體 做 法 是 ：n將 關(guān) 鍵 字 縱 向 排 列 ， 然 后 自 下 而 上 地 對(duì) 相 鄰 兩 個(gè) 記 錄 的關(guān) 鍵 字 進(jìn)

50、 行 比 較 ， 若 為 逆 序 （ 即 Rj-1.keyRj.key，j=n,n-12） 則 交 換 兩 個(gè) 記 錄 ， 直 到 全 部 記 錄 都 比 較 和 交換 完 畢 （ 即 j=2） ， 第 一 趟 冒 泡 排 序 結(jié) 束 ；n此 時(shí) 最 小 關(guān) 鍵 字 值 的 記 錄 上 浮 到 了 R1的 位 置 上 。 然 后對(duì) n-1個(gè) 記 錄 重 復(fù) 類(lèi) 似 的 操 作 ， 次 小 關(guān) 鍵 字 值 的 記 錄 上 浮到 R2的 位 置 上 。 n重 復(fù) 進(jìn) 行 這 樣 的 過(guò) 程 ， 直 到 沒(méi) 有 記 錄 需 要 交 換 為 止 （ 最多 需 n-1趟 冒 泡 排 序 ） ， 整 個(gè)

51、待 排 序 文 件 就 按 關(guān) 鍵 字 值 升序 排 列 完 畢 。 冒 泡 排 序 算 法 舉 例n例 如 ， 對(duì) 于 8個(gè) 記 錄 的 關(guān) 鍵 字 序 列 （ 46， 26， 43， 18，74， 21, ,57） ， 冒 泡 排 序 的 過(guò) 程 如 下 圖 所 示 ： 冒 泡 排 序 算 法 （ 續(xù) ）n由 該 冒 泡 排 序 的 實(shí) 例 ， 也 證 實(shí) 了 至 多 需 要 n-1趟 冒 泡排 序 即 可 完 成 整 個(gè) 排 序 。n事 實(shí) 上 存 在 不 需 要 n-1趟 就 可 以 完 全 排 好 序 的 情 況 ，如 上 例 的 第 五 趟 排 序 后 就 已 經(jīng) 排 好 序 了

52、；n其 識(shí) 別 辦 法 是 ， 若 某 一 趟 冒 泡 排 序 過(guò) 程 中 沒(méi) 有 進(jìn) 行記 錄 的 位 置 交 換 ， 則 說(shuō) 明 待 排 序 文 件 已 經(jīng) 完 全 排 好 序了 。 n為 此 ， 需 在 算 法 中 引 入 一 個(gè) 交 換 狀 態(tài) 變 量 flag， 在每 一 趟 排 序 之 前 置 flag為 0， 每 次 交 換 時(shí) 給 flag加 1，若 一 趟 結(jié) 束 時(shí) flag為 0則 終 止 算 法 。 冒 泡 排 序 的 算 法 描 述 void bubblesort(recordtype R,int n) int i,j,flag; recordtype temp; f

53、or(i=1;i= i+1;j-) if(Rj-1.key Rj.key) temp=Rj-1; Rj-1=Rj; Rj=temp; flag=flag+1; /*置 已 交 換 標(biāo) 志 */ if(flag=0) break; /*bubblesort end */ 冒 泡 排 序 算 法 分 析n冒 泡 排 序 也 是 一 種 穩(wěn) 定 的 排 序 方 法 。n其 時(shí) 間 復(fù) 雜 度 可 以 如 下 分 析 ：n在 最 好 的 情 況 下 ， 是 初 始 記 錄 的 關(guān) 鍵 字 已 遞 增 有 序 時(shí) ，只 需 一 趟 排 序 ， 比 較 次 數(shù) 為 n-1， 沒(méi) 有 交 換 記 錄 即 記

54、 錄 的移 動(dòng) 次 數(shù) 為 0；n在 最 壞 的 情 況 下 ， 是 初 始 記 錄 遞 減 有 序 （ 即 逆 序 ） 時(shí) ，需 進(jìn) 行 n-1趟 排 序 ， 比 較 次 數(shù) 為 ， 交 換 次數(shù) 為 ， 每 次 交 換 需 三 次 移 動(dòng) 記 錄 ， 其 移 動(dòng)次 數(shù) 為 。 n在 平 均 情 況 下 ， 關(guān) 鍵 字 的 比 較 次 數(shù) 和 記 錄 的 移 動(dòng) 次 數(shù) 大約 為 最 壞 情 況 下 的 一 半 ， 因 此 冒 泡 排 序 算 法 的 時(shí) 間 復(fù) 雜 度為 O(n2)。 冒 泡 排 序 算 法 分 析 （ 續(xù) ）n上 述 的 冒 泡 排 序 算 法 還 可 以 作 一 些 改

55、 進(jìn) 來(lái) 提 高 排 序速 度 ， 比 如 ：n在 每 趟 排 序 中 記 住 最 后 一 次 發(fā) 生 交 換 記 錄 的 位 置 K， 因 為位 置 K之 前 的 記 錄 都 已 排 好 了 序 ， 下 一 趟 的 排 序 可 以 終 止于 位 置 K而 不 必 進(jìn) 行 到 預(yù) 定 的 下 界 位 置 i。n在 排 序 過(guò) 程 中 交 替 變 化 掃 描 比 較 的 方 向 ， 即 前 一 趟 由 后向 前 掃 描 ， 后 一 趟 則 由 前 向 后 掃 描 ， 而 不 是 一 直 都 由 后 向前 掃 描 。 由 后 向 前 掃 描 比 較 交 換 一 趟 ， 可 使 最 輕 的 氣 泡

56、上浮 到 頂 部 ， 但 只 能 使 最 重 的 氣 泡 下 沉 一 個(gè) 位 置 ； 由 前 向 后掃 描 比 較 交 換 一 趟 ， 可 使 最 重 的 氣 泡 下 沉 到 底 部 ， 但 只 能使 最 輕 的 氣 泡 上 浮 一 個(gè) 位 置 。 交 替 變 化 掃 描 方 向 可 以 加 速最 輕 和 最 重 的 氣 泡 向 兩 端 迅 速 沉 浮 ， 有 利 于 加 速 排 序 過(guò) 程 。 8.3 交 換 排 序8.3.1 冒 泡 排 序8.3.2 快 速 排 序 快 速 排 序n快 速 排 序 （ quick sort） 也 稱 作 分 區(qū) 交 換 排 序 ， 是 對(duì) 冒 泡排 序 的

57、 一 種 改 進(jìn) 排 序 方 法 。 它 是 目 前 各 種 內(nèi) 部 排 序 方 法 中 較快 的 方 法 ， 故 稱 之 為 快 速 排 序 。n快 速 排 序 的 基 本 思 想 是 ：n在 待 排 序 文 件 的 n個(gè) 記 錄 中 ， 任 取 一 個(gè) 記 錄 （ 通 常 是 選取 第 一 個(gè) 記 錄 ） 作 為 基 準(zhǔn) ；n經(jīng) 過(guò) 一 趟 排 序 后 以 基 準(zhǔn) 記 錄 的 關(guān) 鍵 字 把 全 部 記 錄 分 為 兩部 分 ， 所 有 關(guān) 鍵 字 值 比 基 準(zhǔn) 記 錄 關(guān) 鍵 字 值 小 的 記 錄 都 排列 在 基 準(zhǔn) 記 錄 之 前 ， 而 所 有 關(guān) 鍵 字 值 比 基 準(zhǔn) 記

58、錄 關(guān) 鍵 字值 大 的 記 錄 都 排 列 在 基 準(zhǔn) 記 錄 之 后 ； n然 后 對(duì) 基 準(zhǔn) 記 錄 前 后 的 這 兩 個(gè) 部 分 分 別 重 復(fù) 這 樣 的 過(guò) 程 ，得 到 本 趟 排 序 的 兩 個(gè) 新 到 位 的 基 準(zhǔn) 和 四 個(gè) 部 分 如 此重 復(fù) 上 述 過(guò) 程 ， 直 到 每 一 個(gè) 部 分 只 剩 下 一 個(gè) 記 錄 （ 即 全部 到 位 ） 時(shí) 為 止 。 快 速 排 序 算 法n設(shè) 兩 個(gè) 指 示 器 變 量 i和 j， 分 別 指 向 待 排 序 區(qū) 間 的 第 一 個(gè) 記錄 和 最 后 一 個(gè) 記 錄 ；n先 將 第 一 個(gè) 記 錄 移 到 暫 存 變 量

59、temp中 ， 然 后 j從 區(qū) 間 的 最后 一 個(gè) 記 錄 起 向 前 掃 描 ， 直 到 找 到 滿 足 Rj.keytemp.key的 記 錄 時(shí) ， 將 Ri移 入 Rj中 ； n就 這 樣 j自 j-1從 后 向 前 掃 描 一 次 移 入 一 個(gè) Rj于 Ri中 ，i自 i+1從 前 向 后 掃 描 一 次 移 入 一 個(gè) Ri于 Rj中 ， 反 復(fù) 交替 的 掃 描 和 移 動(dòng) 記 錄 ；n直 到 i=j時(shí) 把 temp移 入 Ri中 （ 區(qū) 間 中 第 一 個(gè) 記 錄 應(yīng) 在 的位 置 ） ， 它 把 整 個(gè) 待 排 序 區(qū) 間 分 割 為 相 互 獨(dú) 立 的 兩 個(gè) 更 小

60、的 區(qū) 間 。 快 速 排 序 的 算 法 描 述n這 種 把 一 個(gè) 待 排 序 區(qū) 間 通 過(guò) 基 準(zhǔn) 記 錄 （ 第 一 個(gè) 記 錄 ） 分 割成 為 兩 個(gè) 區(qū) 間 的 一 次 分 割 排 序 算 法 如 下 ： int divideareasort(recordtype R,int s,int t) int i,j; recordtype temp; i=s; j=t; temp=Rs; do while(Rj.key=temp.key) if(ij) Ri=Rj; i+; 快 速 排 序 的 算 法 描 述 （ 續(xù) ） while(Ri.key=temp.key) if(ij) R

61、j=Ri; j-; while(ij); Ri=temp; return i; /*divideareasort end*/ 快 速 排 序 的 算 法 描 述 （ 續(xù) ）n 對(duì) 于 待 排 序 文 件 R利 用 一 次 分 割 區(qū) 間 排 序 算 法 時(shí) ， 令s=1和 t=n即 可 完 成 第 一 趟 排 序 ； 由 此 得 到 的 兩 個(gè) 更 小 的 區(qū)間 R1i-1和 Ri+1n， 繼 續(xù) 利 用 算 法 divideareasort分 割 為 更 小 的 四 個(gè) 區(qū) 間 ； 如 此 一 直 進(jìn) 行 下 去 ， 直 到 都 分 割為 只 有 一 個(gè) 記 錄 時(shí) 排 序 結(jié) 束 。 調(diào)

62、用 divideareasort對(duì) R 進(jìn) 行 快 速 排 序 的 遞 歸 算 法 可 描 述 如 下 ： void quicksort(recordtype R,int s,int t) int i; if(st) i=divideareasort(R,s,t); quicksort(R,s,i-1); quicksort(R,i+1,t); /*quicksort end*/ 快 速 排 序 的 算 法 舉 例n下 面 我 們 使 用 快 速 排 序 算 法 對(duì) 關(guān) 鍵 字 序 列 （36，73，65，97，13，27， ，29） 排 序 ， 在 下 面 的 排 序 過(guò) 程 示 例 中 ，

63、先 給 出 第 一 趟 中 的 區(qū) 間 分 割 的 整 個(gè) 過(guò) 程 ， 然 后 給 出 各 趟 的排 序 結(jié) 果 ； 用 方 括 號(hào) 表 示 區(qū) 間 ， 用 方 框 表 示 暫 存 變 量temp的 關(guān) 鍵 字 值 （ 并 未 參 加 交 換 ， 在 分 割 完 成 后 才 放 入 最 終 位置 上 ） 。 快 速 排 序 的 算 法 舉 例 （ 續(xù) ） 快 速 排 序 的 算 法 舉 例 （ 續(xù) ） 快 速 排 序 的 算 法 舉 例 （ 續(xù) ） 快 速 排 序 的 算 法 分 析n快 速 排 序 過(guò) 程 中 各 趟 中 所 選 擇 的 基 準(zhǔn) 可以 用 一 棵 二 叉 樹(shù) 來(lái) 表 示 ，

64、如 上 例 中 的 基準(zhǔn) 二 叉 樹(shù) 如 右 圖 所 示 。 基 準(zhǔn) 二 叉 樹(shù) 反 映了 快 速 排 序 的 遞 歸 調(diào) 用 過(guò) 程 ， 也 便 于 我們 對(duì) 快 速 排 序 算 法 進(jìn) 行 性 能 分 析 。 n快 速 排 序 的 基 準(zhǔn) 二 叉 樹(shù) 是 關(guān) 鍵 字 的 一 棵 二 叉 檢 索 樹(shù) ， 其 中序 遍 歷 序 列 就 是 關(guān) 鍵 字 的 升 序 排 列 。 n在 最 好 的 情 況 下 ， 基 準(zhǔn) 二 叉 樹(shù) 是 一 棵 理 想 的 平 衡 二 叉 檢 索樹(shù) ， 深 度 為 ， 遞 歸 所 需 棧 的 存 儲(chǔ) 開(kāi) 銷(xiāo) 為 O(log2n)，時(shí) 間 開(kāi) 銷(xiāo) 為 結(jié) 點(diǎn) 數(shù) 乘

65、平 均 檢 索 長(zhǎng) 度 ， 即 O(nlog2n)。 快 速 排 序 的 算 法 分 析 （ 續(xù) ）n在 最 壞 情 況 下 ， 基 準(zhǔn) 二 叉 樹(shù) 是 一 棵 單 枝 二 叉 檢 索 樹(shù) ， 深 度為n， 存 儲(chǔ) 開(kāi) 銷(xiāo) 為O(n)， 時(shí) 間 開(kāi) 銷(xiāo) 為O(n2)。n在 平 均 情 況 下 ， 基 準(zhǔn) 二 叉 樹(shù) 是 一 棵 隨 機(jī) 的 二 叉 檢 索 樹(shù) ， 由于 二 叉 檢 索 樹(shù) 的 平 均 檢 索 長(zhǎng) 度 為O(log2n)， 故 時(shí) 間 開(kāi) 銷(xiāo) 也是O(nlog2n)。n為 了 避 免 初 始 關(guān) 鍵 字 序 列 有 序 或 基 本 有 序 時(shí) 快 速 排 序 蛻 化為 冒 泡 排

66、 序 （ 即 基 準(zhǔn) 二 叉 樹(shù) 為 單 枝 或 近 似 單 枝 二 叉 樹(shù) ） 的 情況 ， 通 常 采 取 “ 三 者 取 中 ” 的 基 準(zhǔn) 記 錄 選 取 辦 法 改 進(jìn) 之 。 n所 謂 三 者 取 中 是 指 在Rs、Rt和R(s+t)/2三 者 中選 取 關(guān) 鍵 字 值 居 中 的 記 錄 作 為 分 割 區(qū) 間 的 基 準(zhǔn) ， 這 種 選 取 基準(zhǔn) 記 錄 的 方 法 可 以 大 大 改 善 快 速 排 序 在 最 壞 情 況 下 的 性 能 。n快 速 排 序 算 法 是 一 種 不 穩(wěn) 定 的 排 序 方 法 。 第 8章 排 序 及 基 本 算 法8.1 排 序 的 基 本 概 念8.2 插 入 排 序8.3 交 換 排 序8.4 選 擇 排 序8.5 歸 并 排 序8.6 基 數(shù) 排 序8.7 各 種 內(nèi) 部 排 序 方 法 的 比 較 和 選 擇8.8 外 部 排 序 簡(jiǎn) 介 選 擇 排 序n選 擇 排 序 的 基 本 方 法 是 ， 每 次 從 待 排 序 文 件 的各 個(gè) 記 錄 中 ， 依 次 選 出 關(guān) 鍵 字 值 最 小 的 記 錄 放 在已 排 好