【正文】 lude void main() { double x[10],max,min,ave,med,var,std。 int i。 for(i=0。i10。i++) scanf(%lf,amp。x[i])。 max=ismax(x,10)。 min=ismin(x,10)。 ave=isave(x,10)。 med=median(x,10)。 var=variance(x,10)。 std=std_dev(x,10)。 printf(最大值： %lf 最小值： %lf 平均值： %lf\n中值： %lf 方差： %lf 標準偏差： %lf\n, max,min,ave,med,var,std)。 } C語言程序設(shè)計 第 5章 數(shù)組和矩陣 排序算法 1．選擇排序（ Selection Sort）算法 2．冒泡排序（ Bubble Sort）算法 C語言程序設(shè)計 第 5章 數(shù)組和矩陣 選擇排序思想： 在所有元素中查找最小的元素，將此元素與最前面的元素交換，再在余下元素中查找最小的元素，將此元素與余下元素的最前面元素交換，因為每一次都是選擇一個最小數(shù)進行，所以稱為選擇排序。 1．選擇排序（ Selection Sort）算法 （ 必記算法 ） C語言程序設(shè)計 第 5章 數(shù)組和矩陣 10個數(shù)據(jù)的選擇排序過程 C語言程序設(shè)計 第 5章 數(shù)組和矩陣 選擇排序通用算法描述： void SelectSort(int x[ ], int n) { int i, j, k, t。 for(i=0。 in1。 i++) /*n個數(shù)進行 n1趟選擇，外循環(huán)控制趟數(shù) */ { k=i。 /*k記憶最小值位置，假設(shè)法 */ /*內(nèi)循環(huán)負責在當前無序區(qū) x[i+1]…x[n1]中選最小值 */ for(j=i+1。jn。j++) if(x[j]x[k]) k=j。 /*k記下目前找到的最小值所在的位置 */ if(k!=i) /*將最小數(shù)交換到無序區(qū)最前面 */ { t=x[i]。 x[i]=x[k]。 x[k]=t。} } } C語言程序設(shè)計 第 5章 數(shù)組和矩陣 【 例 510】 已知某班學生的某門課成績，對其按升序排列。 include define NUM 100 void SelectSort(int x[ ],int n) { int i,j,k,t。 for(i=0。in1。i++) { k=i。 for(j=i+1。jn。j++) if(x[j]x[k]) k=j。 if(k!=i) { t=x[i]。x[i]=x[k]。x[k]=t。 } } } C語言程序設(shè)計 第 5章 數(shù)組和矩陣 void main() { int i,n,a[NUM]。 printf (請輸入學生實際人數(shù) :\n )。 scanf(%d,amp。n)。 for(i=0。 in。 i++) /*數(shù)據(jù)輸入 */ { printf (請輸入第 %d個學生成績 :\n ,i+1)。 scanf(%d,a+i)。 if(a[i]0 ||a[i]100) {i。continue。} /*數(shù)據(jù)有效性驗證 */ } SelectSort(a,n)。 /*函數(shù)調(diào)用，數(shù)組名做實參 */ printf ( the sorted numbers: \n )。 for(i=0。 in。 i++) /*輸出 */ printf( %d ,a[i])。 } C語言程序設(shè)計 第 5章 數(shù)組和矩陣 2．冒泡排序（ Bubble Sort）算法 （ 必記算法 ） ?冒泡排序是對所有相鄰的元素進行比較，在比較排序過程中總是大數(shù)往后（下）放，小數(shù)往前（上）放，相當于氣泡往上升，所以稱作冒泡排序。 ?從下往上排序，則最輕氣泡先產(chǎn)生； ?從上往下排排序，則最重氣泡先產(chǎn)生。 設(shè) n個數(shù)按由小到大排列，冒泡排序的 基本思想 是： （ 1） 初始狀態(tài)： x[0]、 x[1]、 ? x[n1]為 無序區(qū) 。 （ 2） 第一趟掃描 對無序區(qū)從上往下，依次比較相鄰兩個數(shù)據(jù)的大小，若發(fā)現(xiàn)小者在下、大者在上，則交換二者位置。 每次對于每對氣泡 (x[j]， x[j+1])，若x[j]x[j+1]，則交換 x[j]和 x[j+1]的值。 第一趟掃描完畢時， “ 最重 ” 的氣泡（數(shù)據(jù)）就移到該區(qū)間的最后，即最大數(shù)據(jù)被推到了最后。有序區(qū)在最后。 C語言程序設(shè)計 第 5章 數(shù)組和矩陣 經(jīng)過 i1趟冒泡排序后 ： x[0]、 x[1]、 ? x[ni]為 無序區(qū) ， x[ni+1]? x[n1]為 有序區(qū)。 （ 3） 第 i趟排序： 繼續(xù)掃描無序區(qū) x[0]、 x[1]、 ? x[ni]。形成新的有序區(qū)和無序區(qū)： x[0] ? x[ni1]為無序區(qū)， x[ni]? x[n1]為有序區(qū)。 依次類推，一共需進行 n1趟冒泡排序，完成n1個數(shù)據(jù)的升序排列，最后一個數(shù)據(jù)不需再排。x[0]、 x[1]、 ? x[n1]形成新的有序區(qū)。 C語言程序設(shè)計 第 5章 數(shù)組和矩陣 10個數(shù)據(jù)的冒泡排序過程 C語言程序設(shè)計 第 5章 數(shù)組和矩陣 冒泡排序通用算法 void BubbleSort(int x[],int n) { /*采用自上向下掃描，對 x[ ]做冒泡排序 */ int i, j, t； for(i=1。in。i++) /*外循環(huán)控制趟，做 n1趟排序 */ for(j=0。 jni。 j++) /*對當前無序區(qū)自前向后掃描 */ if(x[j]x[j+1]) /*交換數(shù)據(jù) */ {t=x[j]。x[j]=x[j+1]。x[j+1]=t。} } C語言程序設(shè)計 第 5章 數(shù)組和矩陣 優(yōu)化冒泡排序通用算法 void BubSort(int x[ ],int n) { /*采用自上（左）向下（右）掃描，對 x做冒泡排序 */ int i, j, t； int exchange； /*交換標志 */ for(i=1。in。i++) /*最多做 n1趟排序 */ { exchange=0； /*本趟排序開始前交換標志為假 */ for(j=0。 jni。 j++) /*對當前無序區(qū)自前向后掃描 */ if(x[j]x[j+1]) /*交換數(shù)據(jù) */ { t=x[j]； x[j]=x[j+1]； x[j+1]=t； exchange=1； /*發(fā)生了交換，故將交換標志置為 1*/ } if(!exchange) return； /*本趟排序未發(fā)生交換，提前終止算法 */ } } C語言程序設(shè)計 第 5章 數(shù)組和矩陣 【 例 511】 用冒泡排序法實現(xiàn)例 510。 include define NUM 100 void BubSort(int x[],int n) { int i, j, t。 int exchange。 for(i=1。in。i++) { exchange=0。 for(j=0。 jni。 j++) if(x[j]x[j+1]) { t=x[j]。 x[j]=x[j+1]。 x[j+1]=t。 exchange=1。 } if(!exchange) return。 } } C語言程序設(shè)計 第 5章 數(shù)組和矩陣 void main() { int i,n,a[NUM]。 printf (請輸入學生實際人數(shù) :\n )。 scanf(%d,amp。n)。 for(i=0。 in。 i++) { printf (請輸入 %d個學生成績 :\n ,i+1)。 scanf(%d,a+i)。 if(a[i]0 ||a[i]100) { i。 continue。 } } BubSort(a,n)。 printf ( the sorted numbers: \n )。 for(i=0。 in。 i++) printf(%d ,a[i])。 } C語言程序設(shè)計 第 5章 數(shù)組和矩陣 數(shù)據(jù)查找算法 1．順序查找（ Sequential Search） 2．有序表中的查找：折半查找（二分查找法） C語言程序設(shè)計 第 5章 數(shù)組和矩陣 用一維數(shù)組存放多個原始數(shù)據(jù)，構(gòu)造一個單層循環(huán)，將待查找的數(shù)據(jù)與一維數(shù)組中的每個元素逐一進行比較，存在如下幾種可能： （ 1）如果相等，表明找到，結(jié)束循環(huán)，查找成功。 （ 2）如果不等，則有兩種可能： ? 數(shù)組中還存在沒有比較的元素，繼續(xù)取下一個元素進行比較。 ? 數(shù)組全部比較完畢，沒有要找的數(shù)據(jù)，結(jié)束比較，查找失敗。 （ 3）算法： 設(shè)置標志變量 flag=0，表示沒有找到；若找到該元素，則 flag=該元素的位置 。 根據(jù)整型變量 flag值即可確定查找的結(jié)果。 1．順序查找（ Sequential Search） C語言程序設(shè)計 第 5章 數(shù)組和矩陣 順序查找的通用算法： int SeqFind(double x[ ], int n, double a) { int i=0,flag=0。 while(inamp。amp。!flag) { if(fabs(ax[i])) /*比較兩個實數(shù)相等 */ flag=i+1。 /*找到的位置 */ else i++。 } return flag。 } C語言程序設(shè)計 第 5章 數(shù)組和矩陣 【 例 512】 已知 10個學生的數(shù)學成績，從鍵盤任意輸入一個成績，查找是否有此成績。 /*program */ include include define N 10 int SeqFind(double x[],int n,double a) { int i=0, flag=0。 while(inamp。amp。!flag) { if(fabs(ax[i])) flag=i+1。 else i++。 } return flag。 } C語言程序設(shè)計 第 5章 數(shù)組和矩陣 void main( ) { int i, flag。 double x[N],a。 printf(請輸入 10個學生的數(shù)學成績： )。 for(i=0。 iN。 i++) scanf(%lf,x+i)。 printf(請輸入待查找的成績： )。 scanf(%lf,amp。a)。 flag=SeqFind(x,N,a)。 if(flag==0) printf(not find)。 else printf(%lf in %d,a,flag)。 } C語言程序設(shè)計 第 5章 數(shù)組和矩陣 2．有序表中的查找：折半查找（二分查找法） 首先，要查找的表是有序表。 在有序表中取中間位置元素作為比較對象，若給定值與中間元素相等，則查找成功