選擇排序法 通訊一甲 B09622048 楊穎穆
目錄 1.摘要 2.排序原理 3.程式 4.Big-o說明 5.實驗結果顯示 6.參考資料
摘要 ※使用程式設計對一串若干未排序的數值加以排序(選擇排序法): 1. 輸入一串未排序數值(至少十個數值),分別存到陣列中 2. 印出該未排序前陣列中之位址與數值 3. 使用選擇排序法完成排序工作, 說明它的效率,即說明其Big-O為何？ 4. 排序後印出該排序陣列中之位址與數值
排序原理 ※這次主要使用的是”選擇排序法”,它是個可用來排序小數目元素的有效率演算法,就是將一串未排好的數字,找出它其中最小的數排至最左邊,也就是把最小元素放置A[0]的位置,然後接著在n-1個元素中,找最小的排在A[1],直到排序好為止。
排序原理 5 4 6 2 ※設計一個由小到大的排序 ※我們先設定好一串數字,假如是”5,4,6,2”分別 A[0] A[1] A[2] A[3] ※設定好A[0]為’最小索引值’,然後與A[1]做比較,如果A[1]<A[0]此時A[1]就是我們新的索引值,接著A[1]再和A[2]做比較得到A[2]>A[1]這時索引值還是為A[1],然後A[1]在和A[3]做比較,A[3]<A[1]時,現在索引值就是A[3],就是我們也找的最小索引值。最後程式會將A[3]存於我們設定好的temp裡,進行和A[0]做交換,依此類推,接著找尋最小第二索引值,直到排序好為止,就會得到我們想要的結果”2,4,5,6” 。 5 4 6 2
程式 #include <stdio.h> #include <stdlib.h> #define n 12 //限制我有12筆資料 void Sort( int A[],int t); //宣告有一個副程式 int main(void){ int t,A[n]; //宣告有變數 t 和 A 陣列 for(t=0;t<n;t++){ //for迴圈 printf(" 請輸入任意數字[%d]:",t); //在畫面中提示我們輸入的數且印出來 scanf("%d",& A[t]); //輸入數字且屬於A陣列 } Sort(A,n); //呼叫副程式,並執行副程式做排序動作 for(t=0;t<n;t++){ //for迴圈 printf("\n由小到大排序後的數字[%d]: ",t); //印出排序好的位址和數字 printf("%d \n",A[t]); //印出排序後的數字從A[0]到A[11] system("PAUSE"); return 0;
void Sort( int A[],int t) { //副程式開始 int i,j,temp,sel; //宣告有變數 i,j,temp,sel for(i=0;i<n-1;i++){ //for迴圈 sel=i; //目前最小元素的索引 for(j=i+1;j<n;j++){ //for迴圈 if(A[j]<A[sel]){ sel=j; //更換目前最小元素的索引 } if(i!=sel){ //A[i]和A[sel]互換 temp=A[i]; A[i]=A[sel]; A[sel]=temp;
Big-o說明 ※Big-o主要就是說明整個排序時間的複雜效率,在我們程式中,已經先設定好我們要輸入的數字為n個,然後它會執行的迴圈總共是n-1次,第n-1次是要做一次比對,然後n-2….依此類推,最後我們得到時間複雜度的結果是n的平方。
實驗結果顯示
參考資料 ※主要的參考資料來至”演算法概論”這本書及王志湖老師上課所教授的內容和同學的程式。
END