數(shù)據(jù)結(jié)構(gòu)與算法--第23講選擇排序.ppt

《數(shù)據(jù)結(jié)構(gòu)與算法--第23講選擇排序.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第23講選擇排序本講知識點(diǎn)：(1)了解選擇排序的思想(2)掌握選擇排序、堆排序的算法(3)掌握選擇排序的應(yīng)用難點(diǎn)：堆排序2排序的基本概念各種排序方法各種排序方法的比較排序知識體系結(jié)構(gòu)排序插入排序選擇排序交換排序歸并排序基數(shù)排序直接插入排序折半插入排序鏈表插入排序希爾排序直接選擇排序堆排序冒泡排序快速排序3選擇排序的主要操作是選擇，其主要思想是：每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼最小的記錄，添加到有序序列中。有序序列r0r1ri-1rirn-1rk…………無序序列rn-1ri+1r0r1ri-1……riri……交換最

2、小記錄一、簡單選擇排序SimpleSelectionSort4基本思想：首先通過n-1次關(guān)鍵字比較，從n個記錄中找出關(guān)鍵字最小的記錄，將它與第一個記錄交換再通過n-2次比較，從剩余的n-1個記錄中找出關(guān)鍵字次小的記錄，將它與第二個記錄交換重復(fù)上述操作，共進(jìn)行n-1趟排序后，排序結(jié)束需解決的關(guān)鍵問題?⑴如何在待排序序列中選出關(guān)鍵碼最小的記錄？⑵如何確定待排序序列中關(guān)鍵碼最小的記錄在有序序列中的位置？一、簡單選擇排序SimpleSelectionSort5簡單選擇排序示例0821i=1最小者08交換21,08最小者16交

3、換25,16最小者21交換49,212128i=02516490808i=2210828492128491625161625一、簡單選擇排序SimpleSelectionSort6i=3最小者25交換25,28i=4最小者28不交換492108281625254921081628252849210816282528無序區(qū)只有一個記錄簡單選擇排序示例一、簡單選擇排序SimpleSelectionSort7解決方法：設(shè)置一個整型變量lowIndex，用于記錄在一趟比較的過程中關(guān)鍵碼最小的記錄位置。關(guān)鍵問題⑴：如何在無序區(qū)

4、中選出關(guān)鍵碼最小的記錄？212825164908lowIndexlowIndexlowIndex08一、簡單選擇排序SimpleSelectionSort8算法描述：lowIndex=i;for(j=i+1;j

5、的待排序區(qū)間是elem[i]~elem[n-1]，則elem[i]是無序區(qū)第一個記錄，所以，將lowIndex所記載的關(guān)鍵碼最小的記錄與elem[i]交換。關(guān)鍵問題⑵：如何確定最小記錄的最終位置？算法描述：if(lowIndex!=i)elem[i]←→elme[lwoIndex];一、簡單選擇排序SimpleSelectionSort10voidSimpleSelectionSort(ElemTypeelem[],intn){for(inti=0;i

6、i;for(intj=i+1;j

7、Onninni=-=-?-=）（簡單選擇排序的時間復(fù)雜度為O(n2)。13改進(jìn)的著眼點(diǎn)：如何減少關(guān)鍵碼間的比較次數(shù)。若能利用每趟比較后的結(jié)果，也就是在找出鍵值最小記錄的同時，也找出鍵值較小的記錄，則可減少后面的選擇中所用的比較次數(shù)，從而提高整個排序過程的效率。減少關(guān)鍵碼間的比較次數(shù)查找最小值的同時，找出較小值二、堆排序HeapSort14堆的定義堆是具有下列性質(zhì)的完全二叉樹：每個結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為小根堆），或每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為大根堆）。1820323645253

8、85040281.小根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最小者。2.較小結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。15堆是具有下列性質(zhì)的完全二叉樹：每個結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為小根堆），或每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為大根堆）。503845402836322018281.大根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最大者。2.較大結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕