第八章內(nèi)部排序內(nèi)容提要基本概念插入排序快速排序選擇排序歸并排序基數(shù)排序排序的概述（一）排序的功能：將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列。排序的穩(wěn)定性：如果在待排序的記錄序列中有多個數(shù)據(jù)元素的關(guān)鍵字值相同，經(jīng)過排序后，這些數(shù)據(jù)元素的相對次序保持不變，則稱這種排序算法是穩(wěn)定的，否則稱之為不穩(wěn)定的。原地排序：在原來占有的空間中進(jìn)行，只占有少量輔助空間。排序的分類內(nèi)部排序和外部排序：內(nèi)部排序是指在排序的整個過程中，待排序的所有數(shù)據(jù)元素全部被放置在內(nèi)存中；外部排序是指由于待排序的數(shù)據(jù)元素個數(shù)太多，而需要將一部分?jǐn)?shù)據(jù)元素放置在內(nèi)存，另一部分?jǐn)?shù)據(jù)元素放置在外設(shè)上。排序概述（三）排序過程中的基本操作比較兩個關(guān)鍵字將記錄從一個位置移到另一個位置待排序序列的存儲方式地址連續(xù)的存儲單元（類似于順序存儲）靜態(tài)鏈表中（排序時修改指針，不移動位置）有地址向量的連續(xù)存儲單元（修改記錄地址）插入排序（一）直接插入排序（簡單排序）基本操作：從數(shù)組的第二個單元開始，依次從原始數(shù)據(jù)中取出數(shù)據(jù)，并將其插入到數(shù)組中該單元之前的已排好序的序列中合適的位置處。操作步驟：從已排好的序列尾部開始，逐一比較，找到新記錄該插入的位置，完成第一次插入第i趟就是在含有i-1個記錄的有序子序列r[1..i-1]中插入記錄r[i]后變成含有i個記錄的有序序列為防止數(shù)組下標(biāo)出界，在r[0]處設(shè)置監(jiān)視哨整個過程進(jìn)行n-1次插入4938

384965

384965973849659776384965769713133849657697271327384965769749132738494965769765

9797767676131313132727272727494949494949簡單插入排序已知線性表按照順序結(jié)構(gòu)存儲滿足原地排序和穩(wěn)定排序的條件，分類后關(guān)鍵字相等的若干個元素是相鄰的O(n)2voidinsertsort(sqlistr,intn){inti,j;for(i=2;i<=n;i++)/*一共進(jìn)行n-1趟排序*/{r[0]=r[i];/*r[0]用于暫時存放待插入的元素*/

j=i-1;/*j為待比較元素下標(biāo)，初始時指向待插入元素前一個單元*/

while(r[0].key<r[j].key){r[j+1]=r[j];j--;}r[j+1]=r[0];/*在j+1位置插入r[0]*/}}穩(wěn)定算法O（n）2插入排序（二）折半插入排序：簡單插入的不足：當(dāng)n大時，耗時基本操作：在一個有序表中進(jìn)行查找和插入操作步驟：設(shè)立兩個指針：low、high通過比較，查找和刪除折半插入排序已知線性表按照順序結(jié)構(gòu)存儲該算法是不穩(wěn)定的原地排序。O(n*logn)2插入排序（三）希爾排序：優(yōu)點：在時間上做了改進(jìn)（分組插入法）基本思想：將待排記錄分成若干序列（定義一個增量）進(jìn)行直接排序，直到序列基本有序。“基本有序”時對全體記錄進(jìn)行一次直接插入排序增量的選擇：增量應(yīng)該是沒有1之外的公因子，并且最后一個增量值必須是1不穩(wěn)定的算法49386597761327495504(49,13)(38,27)(65,49)(97,55)(76,04)第一趟結(jié)果：13274955044938659776(13,55,38,76)(27,04,65)(49,49,97)第二趟結(jié)果：13044938274955659776第三趟直接插入排序第三趟結(jié)果：04132738494955657697快速排序（一）冒泡排序基本思想：將每個記錄R[i]看作是重量為R[i].key的氣泡，根據(jù)輕氣泡不在重氣泡之下的原則，從下往上掃描數(shù)組R，逐一比較，交換順序適合n較小的情況冒泡排序法原地的穩(wěn)定的排序O(n)2最糟糕的情況是，原序列恰好是一個降序序列，則總的比較次數(shù)為n(n-1)/2，移動次數(shù)為3n(n-1)/24938659776132749第一趟結(jié)果：3849657613274997第二趟結(jié)果：3849651327497697第三趟結(jié)果：3849132749657697第四趟結(jié)果：3813274949657697時間復(fù)雜度O（n）穩(wěn)定算法第五趟結(jié)果：1327384949657697快速排序（二）快速排序：對簡單冒泡的改進(jìn)基本思想：將待排序的n個記錄中任取一個記錄（樞軸）作為標(biāo)準(zhǔn)，將所有記錄分為兩組，再重復(fù)上述方法，直到所有記錄都在適當(dāng)位置為止一趟快速排序的過程及算法不穩(wěn)定算法適用于離有序較遠(yuǎn)的情況，不適合接近有序的情況當(dāng)序列成遞增排列時，每次劃分只能將一個元素分離出去，故此時有最糟糕的效率，為 平均的復(fù)雜度為O(n*log2n)O(n)2一趟快速排序的過程：附設(shè)兩個指針low、high，設(shè)樞軸記錄為pivotkey，從high所指位置起向前搜索找到第一個小于pivotkey的記錄和樞軸交換，然后從low所指位置向后搜索，找到第一個大于pivotkey的記錄和樞軸交換，重復(fù)步驟，直至low=high為止。4938659776132749ij若j指向的元素>=p,j--；若j指向的元素<p,

數(shù)換位，i++；若i指向元素<=p,

i++，若i指向的元素>P,數(shù)換位，j--。直至i=j4938659776132749ij2738659776134949j2738659776134949ij2738499776136549iji2738139776496549ij2738134976976549ji2738134976976549ij選擇排序（一）簡單選擇排序基本思想：每一趟在n-i+1個記錄中選擇關(guān)鍵字最小的記錄作為有序序列中第i個記錄。是穩(wěn)定排序算法簡單，易實現(xiàn)，但n不能大簡單選擇排序求局部的最大元素穩(wěn)定的原地排序比較：移動：n-1T=選擇排序（二）樹型選擇排序（錦標(biāo)賽排序）基本思想：對n個記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在其中n/2個較小者之間再進(jìn)行兩兩比較，直至選出最小關(guān)鍵字記錄。該思想可以以一棵有n個葉結(jié)點的完全二叉樹表示存在多余比較，輔助空間多49386597761327494938659776132749386513273813134938659776∞274938657627382727選擇排序（三）堆排序：（需要輔助空間）堆定義：若以一維數(shù)組存儲一個堆，則堆對應(yīng)一棵完全二叉樹，且所有非葉子結(jié)點的值均不大于（或小于）其子女的值，根結(jié)點的值是最?。ɑ蜃畲蟮模┒雅判虻亩x：若在輸出堆頂?shù)淖钚≈岛螅沟檬Ｏ碌膎-1個元素的序列重又建成一個堆，則得到n個元素中的次小值。反復(fù)執(zhí)行，便能得到一個有序序列建成的堆。這樣一個自堆頂至葉子的調(diào)整過程稱為篩選選擇排序（四）堆排序需要解決的兩個問題：如何由一個無序序列建成一個堆如何在輸出堆頂元素后，調(diào)整剩余元素成為一個新的堆例（無序變成堆）例（輸出后調(diào)整）不是穩(wěn)定排序時間復(fù)雜度低O(n*log2n)空間復(fù)雜度低O(C)適合n較大的情況，適合在較大n中找序列的前幾個數(shù)構(gòu)造過程：（構(gòu)造一個根結(jié)點最小的堆）將序列順序排成一棵二叉樹從第n/2個(取整)元素開始向前篩選將該結(jié)點與孩子結(jié)點比較，將小的數(shù)作為根。若發(fā)生結(jié)點的上下層交換，則應(yīng)考慮新的下層結(jié)點是否需要繼續(xù)下墜至葉子節(jié)點。否則讀取第n/2-1的元素，重復(fù)比較過程直到讀取完第1個數(shù)為止493865977613274949386597761327494938654976132797493813497665279713384949766527971338274976654997考慮4號結(jié)點97考慮3號結(jié)點652號結(jié)點38已經(jīng)滿足堆定義，考慮1號結(jié)點97創(chuàng)建堆完畢n/2取整為4，從4號點開始堆調(diào)整的步驟：用堆中最后一個元素代替根再從上到下進(jìn)行調(diào)整，使二叉樹滿足堆的定義調(diào)整完后，再輸出根（堆頂元素），重復(fù)上述過程，直到所有元素都輸出，排序結(jié)束。13382749766549979738274976654913273897497665492738494976659727973849497665389749497665384949977665389776769765659776976576494965769776654997496549977665494997764949歸納：無論是創(chuàng)建堆還是堆調(diào)整，只要發(fā)生上下層的節(jié)點交換，就需要考慮新的下層結(jié)點是否需要繼續(xù)下墜至葉子位置上。歸并排序（二路歸并）基本思想：將兩個或兩個以上的有序表合并為一個有序表。（兩兩歸并）具體步驟：比較各子序列第一個記錄的關(guān)鍵字，最小的一個就是排序后序列的第一個記錄的關(guān)鍵字。取出該記錄，繼續(xù)比較各子序列現(xiàn)在的第一個記錄的關(guān)鍵字，找到排序后的第二個記錄時間復(fù)雜度O(n*log2n)穩(wěn)定算法，但使用較少?；鶖?shù)排序（一）前面所介紹的排序方法都是通過交換、移動來實現(xiàn)的?；鶖?shù)排序是借助多關(guān)鍵字排序的思想，將單關(guān)鍵字按基數(shù)分為“多關(guān)鍵字”進(jìn)行排序。多關(guān)鍵字的排序（多個關(guān)鍵字分主，次）最高位優(yōu)先法（MSD法）：先按最主關(guān)鍵字排序，一直到按最次關(guān)鍵字排序后，將各組連接起來得到序列最低位優(yōu)先法（LSD法）：基數(shù)排序（二）鏈?zhǔn)交鶖?shù)排序基本思想：分配、收集對單關(guān)鍵字也可按多關(guān)鍵字排序方法進(jìn)行。拆分成多項，項的個數(shù)成為“基”（RADIX）采用LSD法進(jìn)行排序具體操作：從最低位起，按關(guān)鍵字的不同值將序列中的記錄分配到RADIX個隊列中，關(guān)鍵字相同的在同樣一鏈隊列中，最后按關(guān)鍵字大小順序鏈接起來穩(wěn)定算法109063930589184505269008083278把每位十進(jìn)制數(shù)字看成一個關(guān)鍵字：則k由3個關(guān)鍵字組成基為10e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]278109063930589184505269008083f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]930063083184505278008109589269505008109930063269278083184589個位e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]083930505184f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]063278008109589269十位e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]278930063008589184505269083f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]109008063083109184269278505589930百位各種內(nèi)部排序的比較各排序時間、空間復(fù)雜度表結(jié)