內(nèi)部排序4選擇排序5歸并排序6基數(shù)排序

《內(nèi)部排序4選擇排序5歸并排序6基數(shù)排序》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、數(shù)據(jù)結(jié)構(gòu)10.1概述第十章內(nèi)部排序10.2插入排序10.3快速排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種內(nèi)部排序方法的比較基本思想：每一趟在n-i+1(i=1,2,…,n)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個(gè)記錄。10.4選擇排序有序序列r1r2ri-1rirnrk…………無(wú)序序列rnri+1r1r2ri-1……riri……交換最小記錄簡(jiǎn)單選擇排序樹(shù)形選擇排序堆排序思路：一.簡(jiǎn)單選擇排序10.4選擇排序每次經(jīng)n-i次比較，從n-i+1個(gè)記錄中選出第i小的記錄，并與第i位置記錄交換。初始關(guān)鍵字493865977

2、6132749i=11338659776492749例i=21327659776493849i=31327389776496549i=41327384976976549i=51327384949976576i=61327384949659776i=71327384949657697每次經(jīng)n-i次比較，從n-i+1個(gè)記錄中選出第i小的記錄，并與第i位置記錄交換。思路：10.4選擇排序解決方法：設(shè)置一個(gè)整型變量index，用于記錄在一趟比較的過(guò)程中關(guān)鍵碼最小的記錄位置。212825164908indexindexindex08關(guān)鍵問(wèn)題⑴:如何在無(wú)序

3、區(qū)中選出關(guān)鍵碼最小的記錄？10.4選擇排序關(guān)鍵問(wèn)題⑴:如何在無(wú)序區(qū)中選出關(guān)鍵碼最小的記錄？212825164908indexindex08算法描述：index=i;for(j=i+1;j<=L.length;j++)if(L.r[j].key

4、小記錄的最終位置？voidSelectSort(SqList&L){for(i=1;i

5、找出鍵值較小的記錄，則可減少后面的選擇中所用的比較次數(shù)，從而提高整個(gè)排序過(guò)程的效率。減少關(guān)鍵碼間的比較次數(shù)查找最小值的同時(shí)，找出較小值10.4選擇排序ZHAOCHALIUBAODIAOYANGXUEWANGCHABAODIAOWANGBAODIAOBAO錦標(biāo)賽過(guò)程示意圖冠軍1234567ZHAOCHALIUBAODIAOYANGXUEWANGCHALIUDIAOWANGCHADIAOCHA錦標(biāo)賽過(guò)程示意圖亞軍89ZHAOCHALIUBAODIAOYANGXUEWANGZHAOLIUDIAOWANGLIUDIAODIAO錦標(biāo)賽過(guò)程示意圖季軍101

6、1思路：二.樹(shù)型選擇排序10.4選擇排序以初始序列作為完全二叉樹(shù)的葉子結(jié)點(diǎn)，從最后的分支結(jié)點(diǎn)開(kāi)始，選左右孩子中較小的(勝者)為其雙親的值，相等則取左孩子，直至選出樹(shù)根，得到最小元素；然后將此時(shí)根對(duì)應(yīng)的葉子結(jié)點(diǎn)關(guān)鍵字值改為?最大值?，從該葉子起與兄弟比，較小的作為新的雙親，直至根，得到次小值…，依次可選出其余元素。134938383865659776131313272749例：4938659776132749二.樹(shù)型選擇排序10.4選擇排序以初始序列作為完全二叉樹(shù)的葉子結(jié)點(diǎn)，從最后的分支結(jié)點(diǎn)開(kāi)始，選左右孩子中較小的(勝者)為其雙親的值，相等則取左

7、孩子，直至選出樹(shù)根，得到最小元素；…274938383865659776∞2776272749二.樹(shù)型選擇排序10.4選擇排序例：4938659776132749134938383865659776131313272749然后將此時(shí)根對(duì)應(yīng)的葉子結(jié)點(diǎn)關(guān)鍵字值改為?最大值?，從該葉子起與兄弟比，較小的作為新的雙親，直至根，得到次小值…，依次可選出其余元素。缺點(diǎn)：需增加額外空間來(lái)存放中間比較結(jié)果和排序結(jié)果，且算法實(shí)現(xiàn)困難。三.堆排序堆的概念：堆是滿足下列性質(zhì)的數(shù)列{k1,k2,…,kn}:ki≤k2iki≤k2i+1ki≥k2iki≥k2i+1或若上

8、述數(shù)列是堆，則k1必是數(shù)列中的最小值或最大值，則稱分別滿足上式的序列為小頂堆或大頂堆。完全二叉樹(shù)中所有非終端結(jié)點(diǎn)的值均不大于（或不小于）其左右孩子的結(jié)