[計算機軟件及應(yīng)用]第八章排序-在線瀏覽
2024-12-03 23:21本頁面
【正文】 76 13 27 49’ i=5 (76) (38 49 65 76 97) 13 27 49’ i=6 (13) (13 38 49 65 76 97) 27 49’ i=7 (27) (13 27 38 49 65 76 97) 49’ i=8 (49) (13 27 38 49 49’ 65 76 97) 監(jiān)視哨 [0] 直接插入排序是穩(wěn)定的。 插入排序 ? 直接插入排序算法簡單、易實現(xiàn)，其算法的時間復(fù)雜度是 O（ n2）。 ? 當(dāng)待排序記錄較少時，排序速度較快，反之，當(dāng)待排序的記錄數(shù)量較大時，大量的比較和移動操作將使直接插入排序算法的效率降低 。 ? 直接插入排序是一種 穩(wěn)定 的排序方法。 適用于待排序的記錄數(shù)量較大的情況。 給指定查找區(qū)間上下界指針賦值 :low←1 ， high ←i 1。 （ 3）將插入位置后面的記錄依次后移一個位置 。 插入排序 14 36 49 52 80 58 61 23 97 75 i low high m m low low m high 14 36 49 52 58 61 80 23 97 75 i low high m high m high m low 例如 : 再如 : 插入 位置 插入 位置 ? 折半插入排序只減少關(guān)鍵字間的比較次數(shù)，而記錄的移動次數(shù)不變。 ? 從空間復(fù)雜度來看，折半插入排序只需要一個記錄大小的輔助空間用于暫存待插入的記錄，這與直接插入排序相同。 插入排序 2路插入排序 2路插入排序是對折半插入排序的改進算法，它是利用增加輔助空間來減少排序過程中移動記錄的次數(shù)，即“ 以空間換時間 ”。 先將 r［ 0］的值賦給 d［ 0］，將 d［ 0］看成是處于最后有序序列中處于中間位置的記錄， 再從 r［ 1］開始依次將記錄插入到 d［ 0］之前或之后的有序序列中。 當(dāng)所有的記錄都插入完成后，從指針 first所指向的記錄開始一直讀取到指針 final所指向的記錄，所得到的序列就是排序后的有序序列。 基本思想： 將整個待排序的記錄序列劃分成若干個子序列，然后分別對每個子序列進行直接插入排序，這樣可以減少參與直接插入排序的數(shù)據(jù)量，如此反復(fù)，當(dāng)經(jīng)過幾次分組排序后，記錄的排列已經(jīng)基本有序，這個時候再對所有的記錄進行一次直接插入排序。 在待排序的記錄數(shù)目較大的情況下，希爾排序方法一般要比直接插入排序方法快。增量序列有多種取法，但應(yīng)使增量序列中的值沒有除 1之外的公因子，并且增量序列中的最后一個值必須為 1。 插入排序 選擇排序 選擇排序（ Selection Sort）的基本思想是 :每一趟從待排序的序列中選出關(guān)鍵字最小的記錄，順序放在已排好序的子序列的最后，直到全部記錄排序完畢。 第 1趟排序，從無序區(qū)的 n個記錄中選取最小的記錄與序列中的第一條記錄交換位置，它做為有序區(qū)的第一條記錄，此時無序區(qū)剩下 n1條記錄 。 如此反復(fù)， n個記錄的可經(jīng)過 n1 趟簡單選擇排序得到有序結(jié)果。 選擇排序 堆排序 堆排序（ Heap Sort）是利用堆的特性進行排序。 Ki≤K2i ， Ki≤K2i+1或 Ki≥K2i ， Ki≥K2i+1（ i=1， 2， … ， n/2） 若將與此序列對應(yīng)的一維數(shù)組看成是一棵完全二叉樹按層次編號的順序存儲，則堆的含義表明，完全二叉樹中所有非終端結(jié)點的值均不小于（或不大于）其左、右孩子結(jié)點的值。 選擇排序 選擇排序 堆排序的基本思想是 :對一組待排序的記錄，首先把它們按堆的定義排成一個堆，將堆頂元素取出 。依次下去，直到取出全部元素，從而將全部記錄排成一個有序序列。為此，我們先把待排序數(shù)據(jù)初始次序置入完全二叉樹的各個結(jié)點中，然后由下而上逐層進行父子結(jié)點的關(guān)鍵字比較并交換，直到使其最后滿足堆的條件。 例如，假定待排序的一組數(shù)據(jù)序列為 : 42 36 56 78 67 11 27 36 選擇排序 40 55 49 73 81 64 36 12 27 98 例如 : 排序之前的關(guān)鍵字序列為 1236817349988155 現(xiàn)在，左 /右子樹都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點，使整個二叉樹是個“堆”即可。 選擇排序 堆排序?qū)?n較大的文件很有效，對記錄數(shù)較少的文件不值得提倡。對于存在相同關(guān)鍵字的記錄的情況，堆排序是 不穩(wěn)定 的。 ? 冒泡排序 ? 快速排序 交換排序 冒泡排序 冒泡排序是一種簡單的排序方法。 假設(shè)在排序過程中 ,記錄序列 R[1..n]的狀態(tài)為 : 第 i 趟起泡排序 無序序列 R[1..ni+1] 有序序列 R[ni+2..n] ni+1 無序序列 R[1..ni] 有序序列 R[ni+1..n] 比較相鄰記錄，將 關(guān)鍵字最大的記錄 交換到 ni+1 的位置上 交換排序 處理過程為 : 第一趟 :從第一條記錄 r［ 1］開始，直到最后一條記錄 r［ n］，對兩兩相鄰的記錄依此比較，若發(fā)現(xiàn)為逆序，則立即交換其位置，最后使這 n條記錄中關(guān)鍵字最大的記錄“下沉”到最底部，既被交換到第 n個位置上，它不參與下一趟排序 。 如此反復(fù)，最多經(jīng)過（ n1）趟冒泡排序，就可以使整個序列成為有序序列。 42 36 56 78 67 11 27 36 交換排序 初始狀態(tài) 42 36 56 78 67 11 27 36 78 i=1 36 42 56 67 11 27 36 67 i=2 36 42 56 11 27 36 56 78 i=3 36 42 11 27 36 42 67 78 i=4
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1