[計算機軟件及應用]數據結構第9章排序中國石油大學華東(已修改)
2025-10-26 04:12 本頁面
【正文】 1 第九章 排序 2 ? 概述 ? 插入排序 （直接、折半、 希爾 ） ? 快速排序 ? 交換排序 （氣泡） ? 選擇排序 （直接） ? 歸并排序 第九章 排序 3 排序算法的穩(wěn)定性 : 如果在元素序列中有兩 個元素 r[i]和 r[j], 它們的排序碼 k[i] == k[j] , 且在排序之前 , 元素 r[i]排在 r[j]前面。如果在排序之后 , 元素 r[i]仍在元素 r[j]的前面 , 則稱這個排序方法是穩(wěn)定的 , 否則稱這個排序方法是不穩(wěn)定的。 內排序與外排序 : 內排序是指在排序期間數據元素全部存放在內存的排序；外排序是指在排序期間全部元素個數太多，不能同時存放在內存，必須根據排序過程的要求，不斷在內、外存之間移動的排序。 4 插入排序 (Insert Sorting) 基本方法是 ：每步將一個待排序的元素，按其排序碼大小，插入到前面已經排好序的一組元素的適當位置上 , 直到元素全部插入為止。 基本思想是 : 當插入第 i (i≥ 1) 個元素時，前面的 V[0], V[1], …, V[ i1]已經排好序。這時，用 V[i]的排序碼與 V[i1], V[i2], … 的排序碼順序進行 比較，后 移 ，找到插入位置即將 V[i]插入。 直接插入排序 (Insert Sort) 5 各趟排序結果 21 25 49 25* 16 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 16 08 25 i = 1 0 1 2 3 4 5 temp 21 25 49 25* 16 08 49 i = 2 6 0 1 2 3 4 5 i = 4 i = 5 i = 3 0 1 2 3 4 5 temp 21 25 49 25* 16 08 16 0 1 2 3 4 5 temp 21 25 49 25* 16 08 25* 0 1 2 3 4 5 temp 21 25 49 25* 16 08 08 7 算法分析 設待排序元素個數為 currentSize = n, 則該算法的主程序執(zhí)行 n1趟 (第一個元素不用插入 )。 排序碼比較次數和元素移動次數與元素排序碼的初始 排列有關。 最好情況下，排序前元素已按排序碼從小到大有序，每趟只需與前面有序元素序列的最后一個元素比較 1次，總的排序碼比較次數為 n1, 元素移動次數為 0。 21 25 49 25* 16 08 0 1 2 3 4 5 8 最壞情況下 , 第 i 趟時第 i 個元素必須與前面 i 個元素都做排序碼比較 , 并且每做 1次比較就要做 1次數據移動 。 21 25 49 28 16 08 0 1 2 3 4 5 9 平均情
教學課件相關推薦
鄂ICP備17016276號-1