大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第七章：排序-第四節(jié)-選擇排序

第四節(jié)選擇排序選擇排序(SelectionSort)的基本思想是：每一趟從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排好序的子文件的最后，直到全部記錄排序完畢。常用的選擇排序方法有直接選擇排序和堆排序。一、直接選擇排序1、排序思想直接選擇排序(StraightSelectSoft，)是一種簡(jiǎn)單的排序方法。它的基本思想是：每次從待排序的無(wú)序區(qū)中選擇出關(guān)鍵字值最小的記錄，將該記錄與該區(qū)中的第一個(gè)記錄交換位置。初始時(shí)，R[1…n]為無(wú)序區(qū)，有序區(qū)為空。第一趟排序是在無(wú)序區(qū)R[1…n]中選出最小的記錄，將它與R[1]交換，R[1]為有序區(qū)；第二趟排序是在無(wú)序區(qū)R[2…n]中選出最小的記錄與R[2]交換，此時(shí)R[1…2]為有序區(qū)；依此類推，做n-1趟排序后，區(qū)間R[1…n]中記錄遞增有序。2、實(shí)例分析【例】一組關(guān)鍵字(38，33，65，82，76，38，24，11)，直接選擇排序過(guò)程。3、算法描述voidSelectSort(seqListR，intn){//對(duì)R作直接選擇排序inti，j，k；for(i=1；i<n；i++)//做n-1趟排序{k=i；//設(shè)k為第i趟排序中關(guān)鍵字最小的記錄位置for(j=i+1；j<=n；j++)//在[i．．n]選擇關(guān)鍵字最小的記錄if(R[j].key<R[k].key)k=j；//若有比R[k].key小的記錄，記住該位置if(k!=i)//與第i個(gè)記錄交換{R[0]=R[i]；R[i]=R[k]；R[k]=R[0]；｝｝｝4、算法分析（1）時(shí)間復(fù)雜度無(wú)論文件初始狀態(tài)如何，在第i趟排序中選出最小關(guān)鍵字的記錄需要做n-i次比較，總比較次數(shù)為（n-1）+（n-2）+…+1=n（n-1）/2；當(dāng)初始文件為正序時(shí)，移動(dòng)次數(shù)為0；文件初態(tài)為反序時(shí)，每趟排序均要執(zhí)行交換操作，每次交換需要移動(dòng)3次，總的移動(dòng)次數(shù)取最大值3（n-1）。直接選擇排序的平均時(shí)間復(fù)雜度為O(n2)。（3）空間復(fù)雜度直接選擇排序的空間復(fù)雜度是O（1），是一個(gè)就地排序。（4）穩(wěn)定性直接選擇排序是不穩(wěn)定的。【例】假設(shè)采用不帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)，試編寫一個(gè)直接選擇排序(升序)的算法。設(shè)單鏈表結(jié)點(diǎn)類型和鏈表類型的定義如下：typedefstructnode{//結(jié)點(diǎn)類型定義DataTypedata；//結(jié)點(diǎn)數(shù)據(jù)域Structnode*next；//結(jié)點(diǎn)指針域}ListNode；typedefListNode*LinkList；（1）按直接選擇排序算法思想，交換結(jié)點(diǎn)的數(shù)據(jù)域和關(guān)鍵字域值的算法。voidLselectsort1(Linklisthead){//先找最小的和第一個(gè)結(jié)點(diǎn)交換，再找次小的和第二個(gè)結(jié)點(diǎn)交換，…，以此類推ListNode*p，*r，*s；ListNodeq；p=head；while（p!=NULL）//假設(shè)鏈表不帶頭結(jié)點(diǎn)｛s=p；//s為保存當(dāng)前關(guān)鍵字最小結(jié)點(diǎn)地址指針r=p->next；while(r!=NULL)//向后比較，找關(guān)鍵字值最小的結(jié)點(diǎn){if（r->data<s->data）//若r指向結(jié)點(diǎn)的關(guān)鍵字值小，使s指向它s=r；r=r->next；//比較下一個(gè)｝if（s!=p）//說(shuō)明有關(guān)鍵字值比s的關(guān)鍵字值小的結(jié)點(diǎn)，需交換｛q=(*p);//整個(gè)結(jié)點(diǎn)記錄賦值p->data=s->data；s->data=q.data；}p=p->next；//指向下一個(gè)結(jié)點(diǎn)｝｝（2）按直接選擇排序算法思想，每次選擇到最小的結(jié)點(diǎn)后，將其脫鏈并加入到一個(gè)新鏈表中，這樣可避免結(jié)點(diǎn)域值交換，最后將新鏈表的頭指針?lè)祷亍inkListLselectSort2（LinkListhead）｛//找最小的為新表的第一個(gè)結(jié)點(diǎn)，找次小的作為第二個(gè)結(jié)點(diǎn)，…，依次類推ListNode*p，*q，*r，*s，*t，*t1；t=NULL//置空表，采用尾插法建立新鏈表while（head!=NULL）{s=head；//先假設(shè)s指向關(guān)鍵字最小值的結(jié)點(diǎn)p=head；q=NULL；//q指向p的前趨結(jié)點(diǎn)r=NULL；//r指向s的前趨結(jié)點(diǎn)while(p!=NULL){if(p->data<s->data)//使s指向當(dāng)前關(guān)鍵字值小的結(jié)點(diǎn){s=p；r=q；//使r指向s的前一個(gè)結(jié)點(diǎn)｝q=p；p=p->next；//指向后繼結(jié)點(diǎn)}if(s==head)//沒(méi)發(fā)現(xiàn)更小的head=head->next；//刪除第一個(gè)結(jié)點(diǎn)elser->next=s->next；//刪除最小結(jié)點(diǎn)if(t==NULL){t=s；t1=t；)//t1指向新表的當(dāng)前尾結(jié)點(diǎn)else//插入新結(jié)點(diǎn){t1->next=s；t1=s;}}t1->next=NULL；returnt;//返回新表頭指針}二、堆排序1、堆排序定義n個(gè)關(guān)鍵字序列Kl，K2，…，Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足如下關(guān)系：（1）ki≤K2i且ki≤K2i+1

或（2）Ki≥K2i且ki≥K2i+1(1≤i≤

)前者稱為小根堆，后者稱為大根堆?！纠筷P(guān)鍵字序列(76，38，59，27，15，44)就是一個(gè)大根堆，還可以將此調(diào)整為小根堆(15，27，44，76，38，59)，它們對(duì)應(yīng)的完全二又樹如圖：2、堆排序的思想從小到大排序的步驟：第一步：將參加排序的原始序列轉(zhuǎn)換為第一個(gè)大根堆（建初始堆）。第二步：把堆的第一個(gè)元素（最大值元素）與堆的最后那個(gè)元素交換位置。第三步：將在第二步中"去掉"最大值元素后剩下的元素組成的序列重新調(diào)整為一個(gè)新的堆。第四步：重復(fù)第二步與第三步n-1次，直到排序結(jié)束。3、實(shí)例分析【例】已知關(guān)鍵字序列為(47，33，1l，56，72，61，25，47)，采用堆排序方法對(duì)該序列進(jìn)行堆排序，畫出建初始堆的過(guò)程和每一趟排序結(jié)果。第一步：將參加排序的原始序列轉(zhuǎn)換為第一個(gè)大根堆（建初始堆）。第二步：將根結(jié)點(diǎn)（最大值）與最后一個(gè)結(jié)點(diǎn)調(diào)換如下圖（a）所示，完成第一趟排序，第一趟排序的結(jié)果為：47566147331125[72]第三步，將第一趟排序的結(jié)果除最后一個(gè)元素外的其余結(jié)點(diǎn)組成的序列調(diào)整為堆，如圖（b）所示，然后將根結(jié)點(diǎn)與倒數(shù)第2個(gè)結(jié)點(diǎn)調(diào)換如下圖（c）所示，完成第二趟排序，第二趟排序的結(jié)果為：25564747331125[6172]第四步，將第二趟排序的結(jié)果除最后2個(gè)元素外的其余結(jié)點(diǎn)組成的序列調(diào)整為堆，如圖（d）所示，然后將根結(jié)點(diǎn)與倒數(shù)第3個(gè)結(jié)點(diǎn)調(diào)換如下圖（e）所示，完成第三趟排序，第三趟排序的結(jié)果為：1147472533[566172]第五步，將第三趟排序的結(jié)果除最后3個(gè)元素外的其余結(jié)點(diǎn)組成的序列調(diào)整為堆，如圖（f）所示，然后將根結(jié)點(diǎn)與倒數(shù)第4個(gè)結(jié)點(diǎn)調(diào)換如圖（g）所示，完成第四趟排序，第四趟排序的結(jié)果為：11334725[47566172]第六步，將第四趟排序的結(jié)果除最后4個(gè)元素外的其余結(jié)點(diǎn)組成的序列調(diào)整為堆，如圖（h）所示，然后將根結(jié)點(diǎn)與倒數(shù)第5個(gè)結(jié)點(diǎn)調(diào)換如圖（i）所示，完成第五趟排序，第五趟排序的結(jié)果為：253311[4747566172]第七步，將第五趟排序的結(jié)果除最后5個(gè)元素外的其余結(jié)點(diǎn)組成的序列調(diào)整為堆，如圖（j）所示，然后將根結(jié)點(diǎn)與倒數(shù)第6個(gè)結(jié)點(diǎn)調(diào)換如圖（k）所示，完成第六趟排序，第六趟排序的結(jié)果為：1125[334747566172]第八步，將第六趟排序的結(jié)果除最后6個(gè)元素外的其余結(jié)點(diǎn)