7-4選擇排序v第七章排序技術(shù)學(xué)什么？簡(jiǎn)單選擇排序堆排序提出關(guān)鍵問(wèn)題給出解決方法寫出算法描述得到完整算法運(yùn)行實(shí)例7-4-1簡(jiǎn)單選擇排序v第七章排序技術(shù)基本思想有序區(qū)無(wú)序區(qū)min簡(jiǎn)單選擇排序的基本思想：第

i

趟（1≤i≤n-1）排序在待排序序列ri~rn

中選取最小記錄，并和第

i個(gè)記錄交換。r1ri-1…rirn……r1ri-1…ri'ri+1rn…運(yùn)行實(shí)例2420101812待排序序列第一趟排序結(jié)果第二趟排序結(jié)果第三趟排序結(jié)果第四趟排序結(jié)果1012242018122420181018241220102018241210關(guān)鍵問(wèn)題簡(jiǎn)單選擇排序進(jìn)行多少趟？for(i=0;i<length-1;i++){

}算法描述：第i趟簡(jiǎn)單選擇排序；有序區(qū)無(wú)序區(qū)minr1ri-1…rirn……第i

趟簡(jiǎn)單選擇排序完成什么工作？（1）在r[i]~r[n-1]中找最小值（2）將最小記錄與r[i]交換算法描述：

index=i; for(j=i+1;j<length;j++)if(data[j]<data[index])index=j;if(index!=i)data[i]<==>data[index];算法實(shí)現(xiàn)voidSort::SelectSort(){inti,j,index,temp;for(i=0;i<length-1;i++) {

}}

if(index!=i){temp=data[i];data[i]=data[index];data[index]=temp;}

index=i; for(j=i+1;j<length;j++)if(data[j]<data[index])index=j;交換語(yǔ)句之前的判斷一定會(huì)提高效率嗎？比較語(yǔ)句？執(zhí)行次數(shù)？移動(dòng)語(yǔ)句？執(zhí)行次數(shù)？時(shí)間性能與排序數(shù)據(jù)的初始狀態(tài)有關(guān)性能分析最好情況：0次最壞情況：3(n-1)次比較次數(shù)：O(n2)移動(dòng)次數(shù)：12345最好、最壞、平均情況：O(n2)12345

空間性能：O(1)

穩(wěn)定性：不穩(wěn)定155*155*7-4-2堆排序v第七章排序技術(shù)改進(jìn)的著眼點(diǎn)缺點(diǎn)：簡(jiǎn)單選擇排序的時(shí)間主要耗費(fèi)在哪了呢？第i

趟掃描無(wú)序序列（n-i

次比較）只做了一件事——找最小值改進(jìn)的著眼點(diǎn)：利用簡(jiǎn)單選擇排序的思想，同時(shí)減少比較次數(shù)利用每趟比較后的結(jié)果優(yōu)點(diǎn)：移動(dòng)次數(shù)較少，最壞情況O(n)查找最小值的同時(shí)找出并保存較小值減少后面選擇所用的比較次數(shù)提高整個(gè)排序的效率堆的定義小根堆：每個(gè)結(jié)點(diǎn)的值都小于等于其左右孩子結(jié)點(diǎn)的完全二叉樹。大根堆：每個(gè)結(jié)點(diǎn)的值都大于等于其左右孩子結(jié)點(diǎn)的完全二叉樹。小根堆和大根堆統(tǒng)稱為堆。1820323825365040284550384532364020182828堆的特點(diǎn)50384532364020182828（2）較大值的結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對(duì)。大根堆有什么特點(diǎn)呢？（1）根結(jié)點(diǎn)（稱為堆頂）的值是所有結(jié)點(diǎn)的最大值；將堆按層序編號(hào)，有什么特點(diǎn)？12367541098堆與序列的關(guān)系5038453236402018282812367541098堆采用順序存儲(chǔ)，則對(duì)應(yīng)一個(gè)（無(wú)序）序列503845323640282018280123456789順序存儲(chǔ)data[i]左孩子data[2*i+1]右孩子data[2*i+2]雙親與左右孩子之間的關(guān)系？堆調(diào)整堆調(diào)整：在一棵完全二叉樹中，根結(jié)點(diǎn)的左右子樹均是堆，調(diào)整根結(jié)點(diǎn)使整個(gè)完全二叉樹成為一個(gè)堆的過(guò)程。voidSort::Sift(intk,intlast)//根結(jié)點(diǎn)的編號(hào)為k，最后一個(gè)結(jié)點(diǎn)的編號(hào)為last{}如何設(shè)計(jì)函數(shù)接口？由于初始建堆和重建堆均調(diào)用此函數(shù)，因此，設(shè)置形參k和last關(guān)鍵問(wèn)題283632251816362832251816iji和j的關(guān)系是？inti=k,j=2*i+1;j是i的左孩子voidSort::Sift(intk,intlast)//根結(jié)點(diǎn)的編號(hào)為k，最后一個(gè)結(jié)點(diǎn)的編號(hào)為last{}循環(huán)條件是？283632301816362832301816363032281816

while(j<=last){}ijijiinti=k,j=2*i+1;voidSort::Sift(intk,intlast)//根結(jié)點(diǎn)的編號(hào)為k，最后一個(gè)結(jié)點(diǎn)的編號(hào)為last{}關(guān)鍵問(wèn)題28為什么和36交換？

if(j<last&&data[j]<data[j+1])j++;交換后如何調(diào)整i和j？else{

temp=data[i];data[i]=data[j];data[j]=temp;i=j;j=2*i+1;}283632301816362832301816363032281816ijiji

while(j<=last){

}

if(j<last&&data[j]<data[j+1])j++;if(data[i]>data[j])break;什么時(shí)候結(jié)束篩選？關(guān)鍵問(wèn)題堆調(diào)整算法voidSort::Sift(intk,intlast){inti,j,temp;i=k;j=2*i+1;//i是被調(diào)整結(jié)點(diǎn)，j是i的左孩子while(j<=last)//還沒(méi)有進(jìn)行到葉子{if(j<last&&data[j]<data[j+1])j++;//j指向左右孩子的較大者if(data[i]>data[j])break;//已經(jīng)是堆else{temp=data[i];data[i]=data[j];data[j]=temp;i=j;j=2*i+1;//被調(diào)整結(jié)點(diǎn)位于結(jié)點(diǎn)j的位置}}}基本思想堆排序的基本思想：首先將待排序序列構(gòu)造成一個(gè)大根堆，即選出了堆中所有記錄的最大者，將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個(gè)記錄。r1…rirn…rn-i+1無(wú)序區(qū)，調(diào)整為大根堆有序區(qū)第i

趟堆排序?qū)1~ri

調(diào)整成大根堆，再將堆頂與ri

交換運(yùn)行實(shí)例12345待排序序列初始建堆541325413254132541325413254132交換r[1]和r[5]無(wú)序區(qū)重建堆交換r[1]和r[4]無(wú)序區(qū)重建堆交換r[1]和r[3]541324312312最后一趟5413221初始建堆如何將一個(gè)無(wú)序序列建成一個(gè)大根堆——初始建堆？待排序序列{28,25,16,36,18,32}282516361832362832251816初始建堆結(jié)果{36,28,32,25,18,16}解決辦法：從編號(hào)最大的分支結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行調(diào)整算法描述：for(i=ceil(length/2)-1;i>=0;i--)Sift(i,length-1);//調(diào)整結(jié)點(diǎn)i需要調(diào)整葉子結(jié)點(diǎn)嗎？運(yùn)行實(shí)例待排序序列{28,25,16,36,18,32}282516361832282532361816283632251816362832251816初始建堆結(jié)果{36,28,32,25,18,16}for(i=ceil(length/2)-1;i>=0;i--)Sift(i,length-1);//調(diào)整結(jié)點(diǎn)i關(guān)鍵問(wèn)題12345待排序序列初始建堆5413254132如何處理堆頂——無(wú)序區(qū)中的最大值？解決辦法：交換data[0]與

data[length-i];52交換413241352413如何將無(wú)序區(qū)重新調(diào)整成為大根堆？無(wú)序區(qū)最后一個(gè)結(jié)點(diǎn)的編號(hào)？解決辦法：調(diào)整根結(jié)點(diǎn)算法描述：Sift(0,length-i-1);52第一趟堆排序結(jié)果413431252重建堆結(jié)果413關(guān)鍵問(wèn)題堆排序要進(jìn)行多少趟？n-1趟算法描述：for(i=0;i<length;i++){

第i

趟堆排序}52第一趟堆排序結(jié)果41352重建堆結(jié)果413第二趟堆排序結(jié)果52413關(guān)鍵問(wèn)題算法實(shí)現(xiàn)voidSort::HeapSort(){inti,temp;for(i=ceil(length/2)-1;i>=0;i--)Sift(i,length-1);for(i=1;i<length;i++)