《選擇排序算法》教學課件2_第1頁
《選擇排序算法》教學課件2_第2頁
《選擇排序算法》教學課件2_第3頁
《選擇排序算法》教學課件2_第4頁
《選擇排序算法》教學課件2_第5頁
已閱讀5頁,還剩12頁未讀 繼續免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

選擇排序

選擇排序是指在排序過程序中,依次從待排序的記錄序列中選擇出關鍵字值最小的記錄、關鍵字值次小的記錄、……,并分別將它們定位到序列左側的第1個位置、第二個位置、……,最后剩下一個關鍵字值最大的記錄位于序列的最后一個位置,從而使待排序的記錄序列成為按關鍵字值由小到大排列的的有序序列。簡單選擇排序1.簡單選擇排序的基本思想

每一趟在n-i+1(i=1,2,3,...,n-1)個記錄中選取關鍵字最小的記錄作為有序序列中的第i個記錄。它的具體實現過程為:(1)將整個記錄序列劃分為有序區域和無序區域,有序區域位于最左端,無序區域位于右端,初始狀態有序區域為空,無序區域含有待排序的所有n個記錄。(2)設置一個整型變量index,用于記錄在一趟的比較過程中,當前關鍵字值最小的記錄位置。開始將它設定為當前無序區域的第一個位置,即假設這個位置的關鍵字最小,然后用它與無序區域中其他記錄進行比較,若發現有比它的關鍵字還小的記錄,就將index改為這個新的最小記錄位置,隨后再用a[index].key與后面的記錄進行比較,并根據比較結果,隨時修改index的值,一趟結束后index中保留的就是本趟選擇的關鍵字最小的記錄位置。(3)將index位置的記錄交換到無序區域的第一個位置,使得有序區域擴展了一個記錄,而無序區域減少了一個記錄。不斷重復(2)、(3),直到無序區域剩下一個記錄為止。此時所有的記錄已經按關鍵字從小到大的順序排列就位。

簡單選擇排序算法簡單選擇排序的整體結構應該為:for(i=1;i<n;i){

第i趟簡單選擇排序;}

下面我們進一步分析一下“第i趟簡單選擇排序”的算法實現。(1)初始化:假設無序區域中的第一個記錄為關鍵字值最小的元素,即將index=i;

下面我們進一步分析一下“第i趟簡單選擇排序”的算法實現。(2)搜索無序區域中關鍵字值最小的記錄位置:

for(j=i+1;j<=n;j++) if(a[j].key<a.[index].ke)index=j;

下面我們進一步分析一下“第i趟簡單選擇排序”的算法實現。(3)將無序區域中關鍵字最小的記錄與無序區域的第一個記錄進行交換,使得有序區域由原來的i-1個記錄擴展到i個記錄。

完整算法voidselecsort(DataTypea,intn){for(i=1;i<n;i++) //對n個記錄進行n-1趟的簡單選擇排序

{index=i; //初始化第i趟簡單選擇排序的最小記錄指針

for(j=i+1;j<=n;j++) //搜索關鍵字最小的記錄位置

if(a[j].key<a[i].key)index=j;if(index!=i){temp=a[i];a[i]=a[index];a[index]=temp; }}}簡單選擇排序算法簡單,但是速度較慢,并且是一種不穩定的排序方法.,但在排序過程中只需要一個用來交換記錄的暫存單元。堆排序1.堆排序的基本思想:堆排序是另一種基于選擇的排序方法。下面我們先介紹一下什么是堆?然后再介紹如何利用堆進行排序。

2.堆定義:

由n個元素組成的序列{k1,k2,……,kn-1,kn},當且僅當滿足如下關系時,稱之為堆。例如序列(47,35,27,26,18,7,13,19)滿足:

若將堆看成是一棵以k1為根的完全二叉樹,則這棵完全二叉樹中的每個非終端結點的值均不大于(或不小于)其左、右孩子結點的值。由此可以看出,若一棵完全二叉樹是堆,則根結點一定是這n個結點中的最小者或最大者。下面給出兩個堆的示例。下面我們討論一下如何利用堆進行排序?從堆的定義可以看出,若將堆用一棵完全二叉樹表示,則根結點是當前堆中所有結點的最小者(或最大者)。堆排序的基本思想是:首先將待排序的記錄序列構造一個堆,此時,選出了堆中所有記錄的最小者或最大者,然后將它從堆中移走,并將剩余的記錄再調整成堆,這樣又找出了次小(或次大)的記錄,以此類推,直到堆中只有一個記錄為止,每個記錄出堆的順序就是一個有序序列。堆排序的篩選算法:voidsift(DataTypea,intk,intm){i=k;;j=2*i;temp=a[i];

while(j<=m)//{if(j<m&&a[j].key<a[j+1].key)j++;if(a[i].key>a[j].key)break;

else{a[i]=a[j];i=j;j=2*i;}}a[i]=temp;}堆排序完整的算法:voidheapsort(DataTypea,intn){h=n/2;//最后一個非終端結點的編號

for(i=h;i>=1;i--)//初建堆。從最后一個非終端結點至根結點

sift(a,i,n);for(i=n;i>1;i--)//重復執行移走堆頂結點及重建堆的操作

{temp=a[1];a[1]=a[i];a[i]=temp;sift(a,1,i-1);}}

在堆排序中,除建初堆以外,其余調整堆的過程最多需要比較樹深次,因此,與

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論