排序是組織數據最基本的運算排序的方法也很多本章給出了幾種典型的排序方法見下表
排序類別 插入排序 交換排序 選擇排序 歸並排序 分配排序
排序方法 直接插入 冒泡法 直接選擇 * 歸並排序 箱排序
希爾排序 * 快速排序(分治法) * 堆排序 * 基數排序
這 五類 內部排序方法的基本思想排序過程算法實現時間和空間性能的分析以及各種排序方法的比較和選擇都是本章內容帶*號的幾種排序方法的基本思想及排序過程是本章需重點理解掌握的部分同時這四個排序算法的實現是難點總之這章的內容很多實在是多太多可是大家都不怕
一基本概念( 識記 )
記錄 中用於某一 項 可用來標識一個記錄則稱為 關鍵字項 該數據項的值稱為 關鍵字 (注意其區別)
排序 就是要整理文件中的記錄使之按關鍵字遞增(或遞減)次序排列起來當待排序記錄的關鍵字均不相同時則排序結果是唯一的否則排序的結果不一定唯一如果在待排序文件中存在多個關鍵字相同的記錄經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變則稱這種排序方法是穩定的否則排序算法是不穩定的
這裡的 穩定性的含義 就是指用某種排序方法在對文件進行排序後 關鍵字 相同的 記錄 的 相對次序的穩定性 穩定是 針對 所有 輸入實例 而言的只要存在一個輸入實例在排序後關鍵字相同記錄的相對次序發生變化就足以認定該排序算法是不穩定的
排序過程中整個文件在內存中處理不涉及數據的內外存交換則稱之為內部排序(內排序)反之若存在數據的內外存交換則稱之為外排序
內部排序 方法可分 五類 插入排序選擇排序交換排序歸並排序和分配排序
評價排序算法好壞的標准 主要有 兩條 執行 時間 和所需的 輔助空間 另外算法的復雜程序也是要考慮的一個因素
二插入排序( 綜合應用 )
插入排序 的基本思想是每次將一個待排序的記錄 按其 關鍵字 大小插 入到 前 面已經排好序的子文件中的適當 位 置直到全部記錄插入完成為止
直接插入排序算法比較容易理解其中的哨兵的作用應當深刻理解並能運用
哨兵 (監視哨)有兩個作用 一是作為臨變量存放R[i] (當前要進行比較的關鍵字)的副本 二是在查找循環中用來監視下標變量j是否越界
實際上一切為簡化邊界條件而引入的附加結點(元素)均可稱為哨兵
直接插入 排序 是穩定的 也就是相同關鍵字的記錄的相對位置在排序後不發生改變
直接插入排序 的時間復雜度在不同輸入實例時是不同的最好情況是文件初態為正序此時算法的時間復雜度為O(n)最壞情況是文件為反序時間復雜度為O(n^)算法的 平均時間復雜度也是O(n^) 該算法的空間復雜度為O()是就地排序
對於一個給定的輸入實例我們應當能夠寫入直接插入排序的排序過程
對於 希爾排序 要記住它的算法是 不穩定 的
三交換排序( 綜合應用 )
交換排序 的基本思想是 兩兩比較 待排序記錄的關鍵字發現兩個記錄次序相 反 時 即 進行交 換 直到沒有反序的記錄為止
冒泡排序 的基本思想是將每個記錄R[i]看作是重量為R[i]key的氣泡根據輕泡不能在重泡之下的原則從 最後 一個記錄(最下方的記錄) 開始往上掃 描 兩兩 進行 比較 凡掃描到違反上述原則的氣泡就進行交換保證 輕 氣 泡 在 上 如此反復進行直到任何兩個氣泡都達到輕者在上重者在下為止
冒泡排序比較簡單其算法也容易理解冒泡排序算法是穩定的 主要的難點還是快速排序
快速排序 其基本思想是將原問題分解為若干個規模更小但結構與原問題相似的子問題;遞歸地解這些子問題然後將這些解組合為原問題的解由於采用了分治的策略因此通常稱為 分治法 (教材中寫為冶我拍拍腦袋想想大概是作者筆誤吧這個冶字好象與Conquer搭不上邊)
分治法有三個步驟分解求解組合
分解 就是在原記錄中任選一個記錄作為基准以此基准把當前無序區劃分為左右兩個較小的子區間並使左邊的記錄關鍵字均小於等於基准記錄的關鍵字右邊子區間中的記錄關鍵字均大於這個基准記錄的關鍵字分解的過程其實是一次粗略排序的過程即它 只做一件事 把整個無序區 排列 成三部分小於等於基准的部分基准和大於等於基准的部分
求解 就是遞歸調用了也就是在左子區間和右子區間裡再進行分解求解直到不用再分就可以求解
組合 什麼也不做求出的解就是組合的結果
所以在分治法中最關鍵的一步就是分解算法的實現即確定當前無序區中的基准記錄所在位置以便遞歸調用時能夠知道當前無序區的區間
那麼在分治法中分解一步選哪個記錄作為基准呢? (選定一個基准後就將以它為界把關鍵字比它大的記錄移到右邊比它小的移到左邊)當然可以隨意選定一個為了算法的簡明可以選無序區的第一個記錄作為基准算法的實現也不復雜如果我們能夠寫出算法每次劃分後的狀態則理解算法的實現也就很容易了
對於快速排序其時間主要耗費在劃分操作上最壞的情況是每次劃分選取的基准都是當前無序區中關鍵字最小(或最大)的記錄這時快速排序必須作n次劃分時間復雜度為O(n^)這種情況就是文件已按遞增序或遞減序排列在最好的情況下每次劃分所選的基准都是當前無序區的中值記錄此時的時間復雜度為O(nlgn)由於出現最壞情況的輸入實例概率極小因此它的 平均性能接近於它的最好時間復雜度 也是O(nlgn)
快速排序 算法是 非穩定 的比如[ ]這個序列排序後的結果為
三選擇排序( 簡單應用 )
選擇排序 的基本思想是每一趟從 待排 序的 記錄 中 選 出關鍵字 最小 的記錄順序存放已排好的子文件的最後(最前)直到全部記錄排序完畢
直接選擇 排序容易理解其 時間復雜度為O(n^) 就地排序算法是 不穩定 的
本來知道直接選擇法就行了可是就是有人吃飽了撐的又弄出了 堆排序有什麼好呢就是因為它更省時間更完美就象上面的分治法
為了弄清堆排序是什麼東西還得先知道堆是什麼東西
堆就是一個關鍵字序列 並且這n個關鍵字的序列KKKn要滿足以下性質( 堆性質 )就是 Ki≤Ki且Ki≤Ki+ 或者 Ki≥Ki且Ki≥Ki+ 當把這個序列存入一個向量並把它看作是一棵完全二叉樹的存儲結構時堆就是這樣一棵二叉樹任一非葉結點的關鍵字均不大於(或不小於)其左右孩子結點的關鍵字(是不很象一堆從小到大(或從大到小)的關鍵字堆起來的塔?)
如這棵二叉樹的根結點(堆頂)是樹上所有結點關鍵字中最小和最大者則稱這兩種堆為 小根堆 和 大根堆 堆中任一子樹亦是堆
知道了這些就可以討論堆排序了其實堆排序就是運用了上述堆的性質這裡以大根堆為例因為堆頂是最大的數所以當把一個關鍵字序列排成一個 大根堆 時就很容易地找到 最大 或最小的數它就 在序列的第一個位置上 然後把這個最大的數與最後一個記錄交換這時最後一個記錄就是關鍵字最大的記錄了這是確定的對於 剩下 的關鍵字序列我們仍然把它排成一個大根堆然後再把第一個記錄(當前堆中的堆頂)與當前堆的最後一個記錄交換這時在整個序列後面就有了兩個有序的關鍵字(從小到大)重復這樣的過程就可以把有序區不斷擴大直到全部關鍵字都進入有序區直到排序完成
這個算法主要是 建立初始堆和重建堆 的過程它的時間復雜度 最壞情況下為O(nlgn)而平均性能接近於最壞性能 堆排序不適宜於記錄數較少的文件 堆排序 是 就地排序 是 不穩定 的
對於給定的序列用堆排序的過程主要是通過畫完全二叉樹來演示
四歸並排序( 領會 )
歸並就是將若干個已排序的文件合成一個有序的文件這個算法容易理解其時間復雜度 無論在最好還是最壞的情況下都是O(nlgn) 它不是就地排序因為用到了一個輔助向量 歸並排序是穩定的
五分配排序( 領會 )
分配排序的思想是不通過關鍵字的比較來進行排序而是根據關鍵字的取值來進行分配
箱排序的平均時間復雜度是線性的O(n)
基數排序是對箱排序的改進和推廣其基本思想是從低位到高位依次對關鍵字進行箱排序要保證基數排序是正確的就必須保證 除第一趟外各趟箱排序是穩定的
我們要能夠對一給定序列寫出其基數排序的過程
六各種排序方法的比較和選擇( 簡單應用 )
這一節還比較重要的主要是簡單應用就是給定一類記錄其數目以及其他條件讓我們選擇一個最合適的排序算法這就要了解各種排序方法的優缺點
選擇排序方法時應 綜合考慮下列因素
待排序的記錄數目n;(n較大的就要用時間復雜變為O(nlgn)的排序方法所以也要記一下算法的時間復雜度)
記錄的大小(規模);(記錄很大的話要用大量時間和空間來移動它們因此最好用鏈表作為存儲結構而快速排序和堆排序在鏈表上難於實現)
關鍵字的結構及其初始狀態;(比如實數就不能使用箱排序和基數排序)
對穩定性的要求(這一點要多多注意記住哪些排序算法是穩定的)
語言工具的條件(有的語言沒有提供指針類或遞歸算法則不易用歸並快速排序和基數排序等算法);
存儲結構; From:http://tw.wingwit.com/Article/program/sjjg/201311/23634.html
