C 語言課件3 數(shù)組常用操作

用冒泡排序法對數(shù)組進行增序

（從小到大）的排序

排序的規(guī)則有兩種：一種是增序（從小到大）；另一種是降序（從大到?。┟芭菖判蚍ㄊ浅Ｒ姷呐判蛩惴ǎM水中氣泡的排放規(guī)則，使重量“較輕”（值較?。┑臍馀莞〉缴厦?，重量“較重”（值較大）的氣泡沉到下面，對每一趟排序，從第1個元素開始，比較相鄰元素的大小，按照規(guī)則對調兩者的位置，最終確定一個最大（或最?。┑臍馀莸奈恢?。

請看對6個數(shù)進行冒泡排序法的過程：985420895420859420854920854290854209大數(shù)沉淀，小數(shù)起泡a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<=4;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}第1趟排序854209584209548209542809542089a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<=3;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}第2趟排序542089452089425089420589a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<=2;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}第3趟排序420589240589204589a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<=1;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}第4趟排序204589024589a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<=0;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}第5趟排序for(i=0;i<=4;i++)if(a[i]>a[i+1]){……}for(i=0;i<=3;i++)if(a[i]>a[i+1]){……}for(i=0;i<=0;i++)if(a[i]>a[i+1]){……}……for(i=0;i<=6-pass-1;i++)if(a[i]>a[i+1]){……}for(pass=1;pass<=5;j++)

pass:趟數(shù)從1到5

size個元素時pass:趟數(shù)從1到size-1i從0到size-pass-16個元素時pass=1pass=2pass=5voidbubblesort(intvalues[],intsize){intpass,j,temp;for(pass=1;pass<=size-1;pass++){ for(j=0;j<=size-1-pass;j++) if(values[j]>values[j+1]){ temp=values[j]; values[j]=values[j+1]; values[j+1]=temp; }} }將冒泡排序法定義為一函數(shù)將冒泡排序法定義為一函數(shù)bubbleSort(intvalues[],intn)：形參是待排序的一維數(shù)組和一維數(shù)組元素的個數(shù)。等同于bubbleSort(int*values,intn)形參定義為intvalues[]或int*values，是一維數(shù)組指針，對應的實參可為任意的一維數(shù)組名。形參定義為intvalues[len1]，則對應的實參是長度為len1的一維數(shù)組名。將打印一維數(shù)組功能定義為一函數(shù)。

voidprint(intvalues[],intsize){ inti; for(i=0;i<size;i++) printf("%4",values[i]); printf("\n");}voidmain(){ intscore1[]={10,3,56,89,80,60}; intscore2[]={78,100,45,12,78,90,3,5}; bubblesort(score1,6); print(score1,6); bubblesort(score2,8); print(score2,8);}31056608089351245787880100用選擇法排序用選擇法對數(shù)組中10個整數(shù)按由小到大排序。解題思路：所謂選擇法就是先將10個數(shù)中最小的數(shù)與a[0]對換；再將a[1]到a[9]中最小的數(shù)與a[1]對換……每比較一輪，找出一個未經(jīng)排序的數(shù)中最小的一個共比較9輪a[0]a[1]a[2]a[3]a[4]36194

16394

1

3694

1

3

496

1

3

4

69小到大排序#include<stdio.h>intmain(){voidsort(intarray[],intn);inta[10],i;printf("enterarray:\n");for(i=0;i<10;i++)scanf("%d",&a[i]);

sort(a,10);printf("Thesortedarray:\n");for(i=0;i<10;i++)printf("%d",a[i]);printf("\n");return0;}voidsort(intarray[],intn){inti,j,k,t;for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(array[j]<array[k])k=j; t=array[k];

array[k]=array[i];

array[i]=t; }}在sort[i]~sort[9]中，最小數(shù)與sort[i]對換冒泡法排序的基本思想是：將相鄰兩個數(shù)進行比較，若前面數(shù)大，則交換兩數(shù)位置，這樣，最大數(shù)就會逐漸沉到最下面，即在最后一個元素的位置。例如有4個數(shù)放在數(shù)組a中，經(jīng)過第一輪3次兩兩比較、交換，最大數(shù)就會沉到最后，存放在a[3]中。第二輪再將前面的3個數(shù)經(jīng)過2次這樣的兩兩比較、交換后，其中的最大數(shù)就會被存放在a[2]中，第三輪將剩下的2個數(shù)比較1次，大的數(shù)被換到a[1],小的數(shù)存放在a[0]中。這樣，經(jīng)過三輪比較就完成了4個數(shù)的排序。方法一：冒泡法排序其排序過程如圖6-4所示。方法一：冒泡法排序一般地，對n個數(shù)進行排序，共需進行n-1輪比較，在第i輪中要對n-i+1個數(shù)進行n-i次相鄰元素的兩兩比較、交換。假設有n個數(shù)存放在一維數(shù)組a中，則n個數(shù)的冒泡排序算法可用for循環(huán)表示為：for(i=0;i<=n-2;i++)for(j=0;j<=n-2-i;j++)if(a[j]>a[j+1])

將a[j]的值與a[j+1]的值互換；方法一：冒泡法排序#include<stdio.h>voidmain(){inti,j,n,a[100];inttemp;printf("Inputthenumberofdata:");

scanf("%d",&n);/*從鍵盤輸入排序數(shù)據(jù)的個數(shù)*/printf("Input%ddata:",n);for(i=0;i<n;i++) scanf("%d",&a[i]);冒泡法排序源程序：printf("\nOutputtheoriginalarray:");for(i=0;i<n;i++)printf("%3d",a[i]);for(i=0;i<=n-2;i++)for(j=0;j<=n-2-i;j++)if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1];

a[j+1]=temp; }冒泡法排序源程序：冒泡排序算法printf("Outputthesortedarray:");for(i=0;i<n;i++)printf("%3d",a[i]);/*輸出排序后的一維數(shù)組序列*/printf("\n");}冒泡法排序源程序：運行結果為：Inputthenumberofdata:4↙Input4data:23564312↙Outputtheoriginalarray:23564312Outputthesortedarray:12234356選擇排序法的基本思想是：

對存放在數(shù)組中待排序的數(shù)首先找出其中的最小值，與第一個元素進行交換，然后找出從第二個元素開始至最后一個元素中的最小值與第二個元素交換，以此類推，直到整個數(shù)組中的數(shù)有序。方法二：選擇排序法假設有存放在數(shù)組中待排序的6個數(shù)a[0]、a[1]、a[2]、a[3]、a[4]和a[5]先找出其中的最小數(shù)與a[0]交換；然后在a[1]、a[2]、a[3]、a[4]和a[5]中找出最小數(shù)與a[1]進行交換；在a[2]、a[3]、a[4]和a[5]中找出最小數(shù)與a[2]進行交換；在a[3]、a[4]和a[5]中找出最小數(shù)與a[3]進行交換；在a[4]和a[5]中找出最小數(shù)與a[4]進行交換，完成排序。方法二：選擇排序法其排序過程如圖6-5所示。方法二：選擇排序法#include<stdio.h>#defineN10/*設定待排序數(shù)據(jù)的個數(shù)*/main(){inta[N];

inti,j,k,t;printf("Input%dnumbers:",N);for(i=0;i<=N-1;i++)scanf("%d",&a[i]);/*輸入原始的一維數(shù)組

序列*/選擇法排序源程序：for(i=0;i<=N-2;i++)

{k=i;for(j=i+1;j<=N-1;j++)if(a[j]<a[k])k=j;if(i!=k)

{t=a[i];a[i]=a[k];a[k]=t; } }選擇法排序源程序：變量k用于記錄最小值的下標，假定第i次中最小數(shù)的位置是ia[k]是每次比較后當前的最小數(shù)若最小數(shù)不是默認的a[i],則將a[i]與a[k]的值交換選擇排序算法printf("thesortednumbers:");for(i=0;i<=N-1;i++)printf("%d",a[i]);printf("\n");}選擇法排序源程序：輸出排序后的一維數(shù)組序列Input10numbers:65839102471↙thesortednumbers:12345678910運行結果:在有序的數(shù)組中，用折半查找法查找一個特定的值。在有序的數(shù)組中，二分查找法是一種比較快捷的查找方法。折半查找法基本思路：先將整個數(shù)組作為查找區(qū)間，用給定的值與查找區(qū)間的中間元素的值相比較，若相等，則查找成功；若不等，則縮小范圍，判斷該值落在區(qū)間的前一部分還是后一部分，再將其所在的部分作為新的查找區(qū)間，繼續(xù)上述過程，一直到找到該值或區(qū)間長度小于0表明查找不成功為止。例如：用折半查找法查找key=80元素31056608085a[0]a[1]a[2]a[3]a[4]a[5]low=3mid=(low+hight)/2hight=5a[mid]<80low=0hight=5mid=4a[mid]=80僅比較2次即找到關鍵字。折半查找法是快速查找法。inta[size]，查找是否含有關鍵字key的元素，折半查找法的算法描述過程：1.設置查找的最初區(qū)間[low，high]，low=0，high=size-1，mid=(low+high)/2；found是否找到key的標志，初值0。2.判斷a[mid]和key之間的關系:若key=a[mid]，則成功找到，置found=1,查找結束。若key<a[mid]，設定下一查找范圍是左半?yún)^(qū)間[low，mid-1]。若key>a[mid]，設定查找范圍是右半?yún)^(qū)間[mid+1，high]。

重復步驟2條件：(low<=high)且found==03.循環(huán)結束時，若found==1則找