概述 插入排序 交換排序 選擇排序 歸并排序 分配排序 外排序.ppt

《概述 插入排序 交換排序 選擇排序 歸并排序 分配排序 外排序.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫。

1、第九章排序概述插入排序交換排序選擇排序歸并排序分配排序外排序一、概述什么是排序(Sorting)？簡單地說，排序就是將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律排列起來（遞增或遞減）。排序是計算機中經(jīng)常遇到的操作。排序的幾個基本概念數(shù)據(jù)表(DataList)待排序的數(shù)據(jù)對象的有限集合。關(guān)鍵字(Key)作為排序依據(jù)的數(shù)據(jù)對象中的屬性域。主關(guān)鍵字不同的數(shù)據(jù)對象若關(guān)鍵字互不相同，則這種關(guān)鍵字稱為主關(guān)鍵字。排序的確切定義使一組任意排列的對象變成一組按關(guān)鍵字線性有序的對象。排序的幾個基本概念（續(xù)）排序算法的穩(wěn)定性判斷標(biāo)準(zhǔn)：關(guān)鍵字相同的數(shù)據(jù)對象在排序過程

2、中是否保持前后次序不變。如2,2*,1，排序后若為1,2*,2則該排序方法是不穩(wěn)定的。內(nèi)排序與外排序區(qū)分標(biāo)準(zhǔn)：排序過程是否全部在內(nèi)存進(jìn)行。排序的時間開銷它是衡量算法好壞的最重要的標(biāo)志。通常用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)和數(shù)據(jù)移動次數(shù)來衡量。排序的方法有很多，但簡單地判斷那一種算法最好，以便能夠普遍選用則是困難的。評價排序算法好壞的標(biāo)準(zhǔn)主要有兩條：算法執(zhí)行所需要的時間和所需要的附加空間。另外，算法本身的復(fù)雜程度也是需要考慮的一個因素。排序算法所需要的附加空間一般都不大，矛盾并不突出。而排序是一種經(jīng)常執(zhí)行的一種運算，往往屬于系統(tǒng)的核心部分

3、，因此排序的時間開銷是算法好壞的最重要的標(biāo)志。為簡單起見，數(shù)據(jù)的存儲結(jié)構(gòu)采用記錄數(shù)組形式，同時假定關(guān)鍵字是整數(shù)。記錄數(shù)組的類型說明如下：typedefstruct{intkey;datatypeother;}rectype;rectypeR[n];其中n為記錄總數(shù)加1二、插入排序基本原理，每步將一個待排序的對象，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組對象適當(dāng)位置上，直到對象全部插入為止。直接插入排序(InsertSort)希爾排序(ShellSort)直接插入排序(InsertSort)基本思想：當(dāng)插入第i個對象時，前面的V[

4、0],V[1],…,V[i-1]已經(jīng)排好序，此時，用v[i]的關(guān)鍵字與V[i-1],V[i-2],…的關(guān)鍵字順序進(jìn)行比較，找到插入位置即將V[i]插入，原來位置上對象向后順移。直接插入排序舉例i(0)(1)(2)(3)(4)(5)temp[21]254925*1608251[2125]4925*1608492[212549]25*160825*3[212525*49]1608164[16212525*49]08085[0816212525*49]直接插入排序算法INSERTSORT(rectypeR[]){inti,j;for(i

5、=2;i=1）。因此，我們把R[0]稱為“監(jiān)視哨”。算法分析直接插

6、入排序算法由兩重循環(huán)組成，對于有n個記錄的排序，內(nèi)循環(huán)表明完成一趟排序所需進(jìn)行的記錄關(guān)鍵字間的比較和記錄的后移。若初始時關(guān)鍵字遞增有序，這是最好情況。每一趟排序中僅需進(jìn)行一次關(guān)鍵字的比較，所以總的比較次數(shù)為n-1。在while循環(huán)之前和之中，至少要移動記錄兩次，所以總的比較次數(shù)為2(n-1)。若初始時關(guān)鍵字遞減有序，這是最壞情況。這時的記錄比較和移動次數(shù)分別為：直接插入排序的穩(wěn)定性直接插入排序是一種穩(wěn)定的排序方法。原理：關(guān)鍵字相同的兩個對象，在整個排序過程中，不會通過比較而相互交換。希爾排序1959年由D.L.Shell提出，又稱

7、縮小增量排序(Diminishing-incrementsort)?；舅枷耄涸诓迦肱判蛑?，只比較相鄰的結(jié)點，一次比較最多把結(jié)點移動一個位置。如果對位置間隔較大距離的結(jié)點進(jìn)行比較，使得結(jié)點在比較以后能夠一次跨過較大的距離，這樣就可以提高排序的速度。希爾排序的基本過程設(shè)待排序的對象序列有n個對象，首先取一個整數(shù)gap

8、止。希爾排序示例i(0)(1)(2)(3)(4)(5)gap21254925*1608121--25*325--1649--0821160825*2549221-08-25216-25*-4908162125*2549308162125*25491