數(shù)據(jù)結(jié)構(gòu)之排序課件(已修改)
2024-09-16 09:02 本頁面
【正文】 數(shù)據(jù)結(jié)構(gòu) 第 九 章 排序 第九章 排序 ?知 識(shí) 點(diǎn) 排序的基本概念 三種簡單的排序方法：冒泡排序、直接選擇排序、簡單插入排序 堆排序 快速排序 歸并排序 基數(shù)排序 ?難 點(diǎn) 堆排序 快速排序 歸并排序 基數(shù)排序 ?要 求 熟練掌握以下內(nèi)容： 熟悉各種內(nèi)部排序方法的基本思想和特點(diǎn) 各種排序方法的優(yōu)缺點(diǎn)、時(shí)、空性能和適用場合 熟悉并掌握三種簡單排序算法、快速排序算法和堆排序算法 了解以下內(nèi)容： 二路歸并排序算法 基數(shù)排序算法 排序的歷史 ?大約公元前 300年，在愛琴島上發(fā)現(xiàn)了若干個(gè)表 , 給出了宗教中的人名 .這些表按字母排列 ,但只按頭一個(gè)字母排列 .(單個(gè)字母的字符排序 ) ?約公元前 200年 , 巴比倫人艾娜基比特 安奴(InakibitAnu),用陶土做的 ,含有 500個(gè)以上高精度的六十進(jìn)制數(shù)及其倒數(shù)表 ,并把它排列成詞典順序 .(數(shù)字排序 ) ?在許多圣經(jīng)贊美詩中 ,遵循一個(gè)嚴(yán)格的字母序列 ,頭一個(gè)詩句以 a開始 ,第二個(gè)詩句以 b開始 ,…… 有助于記憶 .(單個(gè)字母的字符排序 ) ? 公元 134135年 ,某些希臘文稿包含一些分類賬的片斷 ,他列出了按頭兩個(gè)字母排序的納稅人的名字 . ? …… ? 對(duì)于今天排序技術(shù)起源的探索 ,是 19世紀(jì)末發(fā)明的排序機(jī)器 .1880年 ,美國人口普查 ,數(shù)據(jù)處理成為令人頭痛的問題 — 無法在當(dāng)年完成 . 赫爾曼 .霍勒里斯 (Herman Hollerith),一位人口統(tǒng)計(jì)局的 20歲的職員 ,發(fā)明了一臺(tái)巧妙的制表機(jī) ,用 100臺(tái)這樣的制表機(jī) ,成功的完成了人口普查的統(tǒng)計(jì)問題 . ? …… 計(jì)算機(jī)的誕生和發(fā)展促進(jìn)了排序技術(shù)的發(fā)展 ? 1945年 ,馮 .諾依曼 (Von Neuman)編制了一個(gè)用于內(nèi)部合并排序的程序 這也是存儲(chǔ)程序計(jì)算機(jī)的第一個(gè)程序 . ?…… 如果我能把過去幾年內(nèi)所產(chǎn)生的大量的關(guān)于排序的材料的要旨都加以排序 ,編排出次序來 ,那我就心滿意足了 . ( 1955) 排序的概念 ?將一組雜亂無序的數(shù)據(jù)按一定的規(guī)律順次排列起來叫做 排序 (sort)。 ?關(guān)鍵字 (key)：對(duì)一批記錄的排序，應(yīng)該指定是根據(jù)記錄中哪個(gè)字段進(jìn)行排列。這個(gè)作為排序依據(jù)的字段稱之為關(guān)鍵字。 ?約定：本章討論的排序均為按遞增順序排序，并假定要排序的記錄均已存儲(chǔ)在一個(gè)一維數(shù)組中。 記錄的形式定義為： Typedef struct rectype { KeyType key。 /*關(guān)鍵字 */ itemType otherinfo。 /*其他域 */ }rectype。 ?大多數(shù)的排序方法數(shù)據(jù)是存儲(chǔ)在內(nèi)存中，并在內(nèi)存中加以處理的，這種排序方法叫 內(nèi)部排序。 ?如果在排序過程中，數(shù)據(jù)的主要部分存放在外存儲(chǔ)器中（如軟盤、硬盤、磁帶），借助內(nèi)存進(jìn)行內(nèi)、外存數(shù)據(jù)交換，逐步排列記錄之間的順序，則稱之為 外部排序。 ?一種排序方法，如果排序后具有相同關(guān)鍵字的記錄仍維持排序之前的相對(duì)次序，則稱之為 穩(wěn)定的， 否則稱為 不穩(wěn)定的 。 返回 ? 三種簡單排序算法 1 直接插入排序 ?基本思想：設(shè)有 n個(gè)待排序的記錄，順序存放在數(shù)組 R[1— n]中。設(shè)前 I1個(gè)記錄已經(jīng)有序，從第 I個(gè)記錄開始和前 I1個(gè)記錄的關(guān)鍵字比較，找到合適的位置插入。 ?直接插入算法需要經(jīng)過（ n1）趟插入過程。如果數(shù)據(jù)恰好應(yīng)插入到序列的最后端，則不需移動(dòng)數(shù)據(jù)，可節(jié)省時(shí)間，所以若原始數(shù)據(jù)大體有序，此算法可以有較快的運(yùn)算速度。 圖 直接插入排序 ( 0) 42 20 17 13 28 14 23 15 ( 1) [ 20 42] ( 2) [ 17 20 42 ] ( 3) [ 13 1 7 20 42 ] ( 4) [ 13 17 20 28 42 ] ( 5) [ 13 14 17 20 28 4 2] ( 6) [ 13 14 17 20 23 28 42 ] ( 7) [ 13 14 15 17 20 23 28 20] 直接插入排序算法 void insertsort (rectype r[], int n) { int i,j。 for( i=2。 i=n。 i++) { r[0]=r[i]。 /* r[0]用于暫時(shí)存放待插入的元素 */ j= i1。 /* j為待比較元素下標(biāo) while (r[0].keyr[j].key) { r[j+1]=r[j]。 /*記錄后移 */ j。 } r[j+1]=r[0]。 /* 在 j+1位置插入 r[0]*/ } } 性能分析 ?最好的情況：當(dāng)待排序的記錄已經(jīng)有序時(shí)，比較次數(shù)為 n1；移動(dòng)次數(shù)為 2（ n1） ?最壞的情況：當(dāng)待排序的記錄按遞減排列時(shí)，比較次數(shù)為 2+3+……+n=(n 1)(n+2)/2 移動(dòng)次數(shù)為 ?(I+1)=(n1)(n+4)/2 ?取其平均值： 比較次數(shù) 和 移動(dòng)次數(shù) 均為 n*n/2，時(shí)間復(fù)雜度為 O（ n*n），空間復(fù)雜度為 O（ 1）。 性能分析 R[0]的使用： ?把 R[I]放在 R[0]中， R[I]的位置用來向后移動(dòng)記錄 ?比較過程中，又防止下標(biāo) j 出界，起到了監(jiān)視哨的作用。 ?可以看出 ， 該算法是穩(wěn)定的 。 2. 冒泡排序 基本思想： 首先將 R[1]和 R[2]比較，若逆序，則交換 R[1]和 R[2]，然后比較 R[2]和 R[3],….. 直到第 n1個(gè)記錄和第 n個(gè)記錄比較，經(jīng)過這一趟比較，最大的記錄被放在最后一個(gè)位置上；然后對(duì)前 n1個(gè)記錄進(jìn)行同樣的操作，則具有次大關(guān)鍵字的記錄被放在第 n1個(gè)記錄的位置上；重復(fù)以上過程，直到?jīng)]有記錄交換為止。 圖 冒泡排序過程 49 38 65 97 76 13 27 49 [ 38 49 65 76 13 27 49 ] 97 [ 38 49 65 13 27 49 ] 76 97 [ 38 49 13 27 49 ] 65 76 97 [ 38 13 27 49 ] 49 65 76 97 [ 13 27 38 ] 49 49 65 76 97 [ 13 27 ] 38 49 49 65 76 97 冒泡排序算法 void bubblesort(r[ ], n) { int i, j。 for (i=1。 in。 i++) { f
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1