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