[理學(xué)]大學(xué)教程零起點(diǎn)數(shù)據(jù)結(jié)構(gòu)--排序-展示頁
2024-12-17 00:50本頁面
【正文】 第二趟排序 48 35 18 45 12 68 33 步驟： i=3 ri存入 r0位置 將 r0關(guān)鍵字與 rj關(guān)鍵字比較（ j從 i1開始到 1） 若 r0rj則 rj存入 ri+1位置， j減 1 r0存入 rj+1位置 18 483518r0為監(jiān)視哨 10 直接插入排序（基于順序查找） 初始關(guān)鍵字 45 12 68 33 第三趟排序 48 35 18 45 12 68 33 步驟： i=4 ri存入 r0位置 將 r0關(guān)鍵字與 rj關(guān)鍵字比較（ j從 i1開始到 1） 若 r0rj則 rj存入 rj+1位置， j減 1 r0存入 rj+1位置 18 48 35 18 45 48 45r0為監(jiān)視哨 11 直接插入排序（基于順序查找） 初始關(guān)鍵字 12 68 33 第四趟排序 48 35 18 45 12 68 33 步驟： i=5 ri存入 r0位置 將 r0關(guān)鍵字與 rj關(guān)鍵字比較（ j從 i1開始到 1） 若 r0rj則 rj存入 rj+1位置， j減 1 r0存入 rj+1位置 35 18 45 48 45 12 48 453518 12 r0為監(jiān)視哨 12 直接插入排序（基于順序查找） 初始關(guān)鍵字 [48] 35 18 45 12 68 33 [35 48] 18 45 12 68 33 [18 35 48] 45 12 68 33 [18 35 45 48] 12 68 33 [12 18 35 45 48] 68 33 [12 18 35 45 48 68] 33 [12 18 33 35 45 48 68] 13 【 例 】 打撲克牌時(shí)的抓牌就是插入排序一個(gè)很好的例子，每抓一張牌，插入到合適位置，直到抓完牌為止，即可得到一個(gè)有序序列。1 04/01/2022 1 2 第 7章 排序 基本概念 插入排序 交換排序 選擇排序 歸并排序 分配排序 各種內(nèi)部排序比較 3 基本概念 假設(shè)含有 n個(gè)記錄的序列為 {R1， R2， … Rn} 其對(duì)應(yīng)的關(guān)鍵字序列為 {K1， K2， … Kn} 根據(jù) Ki的值對(duì)這組序列重新排列，使對(duì)應(yīng)關(guān)鍵字有序 Ri為一條記錄 Ki為記錄的關(guān)鍵字 可能存在多條記錄具有相同的關(guān)鍵字 4 若具有相同關(guān)鍵字的記錄經(jīng)過排序后記錄的相對(duì)位置 仍保持不變則該排序算法是穩(wěn)定的，否則為不穩(wěn)定的 排序時(shí)只在內(nèi)存中進(jìn)行，為內(nèi)排序， 需要讀取外存設(shè)備中數(shù)據(jù)的為外排序 內(nèi)部排序方法有： 插入排序，交換排序，選擇排序，歸并排序 評(píng)價(jià)排序算法優(yōu)劣的標(biāo)準(zhǔn)： 時(shí)間復(fù)雜度和空間復(fù)雜度 5 待排序記錄存儲(chǔ)結(jié)構(gòu)： typedef struct { int key； antype otheritem； } records； typedef records list[n+1]。 //list 為定義待排序記錄的數(shù)據(jù)類型 //并規(guī)定待排序記錄中 0元素不存數(shù)據(jù) 6 插入排序 直接插入排序（基于順序查找） 表插入排序（基于鏈表存儲(chǔ)） 折半插入排序（基于折半查找） 希爾排序（基于逐趟縮小增量） 7 插入排序 直接插入排序（基于順序查找） 直接插入排序思想： 依次將待排序記錄中的第 i個(gè)記錄插入到有序序列中 . 初始情況：將 r1作為有序序列，將 r2rn逐個(gè)插入 , 通過順序查找方式找到 ri在有序表中的位置 , 找位置的同時(shí)移動(dòng)有序序列中元素的位置 , 找位置時(shí)從后向前找 . 在一個(gè)已排好序的記錄子集的基礎(chǔ)上，每一步將下一個(gè)待排序的記錄有序地插入到已排好序的記錄子集中，直到將所有待排記錄全部插入為止。 14 已知一組鍵值序列 （ 22， 24， 26， 25， 27， 29， 21， 28）， 試給出采用直接插入排序法對(duì)該組序列 作升序排序的每一趟結(jié)果 試寫出直接插入排序算法 設(shè)順序表 va中的數(shù)據(jù)元素遞增有序。 15 插入排序 直接插入排序（基于順序查找） Void StraightSort（ list r, int n） { for（ i=2； i=n。 j = i1。 j。 } } r0為監(jiān)視哨 該算法時(shí)間復(fù)雜度為 O（ n2） 該算法空間復(fù)雜度為 O（ 1） 該算法是穩(wěn)定的排序算法 16 設(shè)順序表 va中的數(shù)據(jù)元素遞增有序。 //記錄數(shù)組，從 1到 n int n。 i。 } r[i].key amp。 i=1 18 實(shí)現(xiàn)排序的基本操作有兩個(gè)： （ 1）“比較”序列中兩個(gè)關(guān)鍵字的大小； （ 2）“移動(dòng)”記錄。 i=n1。 for( j=1。 j++ ) if( r[j+1].key r[j].key ) { flag=0。 r[j]=r[j+1]。 } if( flag==1 ) return。 i=1。 ji。 10. } 11. } 12. } 13. } 49 38 65 97 76 13 27 30 初始 38 49 65 76 13 27 30 97 第一趟 38 49 65 13 27 30 76 第二趟 38 49 13 27 30 65 第三趟 38 13 27 30 49 第四趟 13 27
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1