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