用冒泡排序法對數組進行增序

（從小到大）的排序

排序的規則有兩種：一種是增序（從小到大）；另一種是降序（從大到小）冒泡排序法是常見的排序算法，它模擬水中氣泡的排放規則，使重量“較輕”（值較小）的氣泡浮到上面，重量“較重”（值較大）的氣泡沉到下面，對每一趟排序，從第1個元素開始，比較相鄰元素的大小，按照規則對調兩者的位置，最終確定一個最大（或最小）的氣泡的位置。

請看對6個數進行冒泡排序法的過程：985420895420859420854920854290854209大數沉淀，小數起泡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:趟數從1到5

size個元素時pass:趟數從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; }} }將冒泡排序法定義為一函數將冒泡排序法定義為一函數bubbleSort(intvalues[],intn)：形參是待排序的一維數組和一維數組元素的個數。等同于bubbleSort(int*values,intn)形參定義為intvalues[]或int*values，是一維數組指針，對應的實參可為任意的一維數組名。形參定義為intvalues[len1]，則對應的實參是長度為len1的一維數組名。將打印一維數組功能定義為一函數。

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用選擇法排序用選擇法對數組中10個整數按由小到大排序。解題思路：所謂選擇法就是先將10個數中最小的數與a[0]對換；再將a[1]到a[9]中最小的數與a[1]對換……每比較一輪，找出一個未經排序的數中最小的一個共比較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]中，最小數與sort[i]對換冒泡法排序的基本思想是：將相鄰兩個數進行比較，若前面數大，則交換兩數位置，這樣，最大數就會逐漸沉到最下面，即在最后一個元素的位置。例如有4個數放在數組a中，經過第一輪3次兩兩比較、交換，最大數就會沉到最后，存放在a[3]中。第二輪再將前面的3個數經過2次這樣的兩兩比較、交換后，其中的最大數就會被存放在a[2]中，第三輪將剩下的2個數比較1次，大的數被換到a[1],小的數存放在a[0]中。這樣，經過三輪比較就完成了4個數的排序。方法一：冒泡法排序其排序過程如圖6-4所示。方法一：冒泡法排序一般地，對n個數進行排序，共需進行n-1輪比較，在第i輪中要對n-i+1個數進行n-i次相鄰元素的兩兩比較、交換。假設有n個數存放在一維數組a中，則n個數的冒泡排序算法可用for循環表示為：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);/*從鍵盤輸入排序數據的個數*/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]);/*輸出排序后的一維數組序列*/printf("\n");}冒泡法排序源程序：運行結果為：Inputthenumberofdata:4↙Input4data:23564312↙Outputtheoriginalarray:23564312Outputthesortedarray:12234356選擇排序法的基本思想是：

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

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

序列*/選擇法排序源程序：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次中最小數的位置是ia[k]是每次比較后當前的最小數若最小數不是默認的a[i],則將a[i]與a[k]的值交換選擇排序算法printf("thesortednumbers:");for(i=0;i<=N-1;i++)printf("%d",a[i]);printf("\n");}選擇法排序源程序：輸出排序后的一維數組序列Input10numbers:65839102471↙thesortednumbers:12345678910運行結果:在有序的數組中，用折半查找法查找一個特定的值。在有序的數組中，二分查找法是一種比較快捷的查找方法。折半查找法基本思路：先將整個數組作為查找區間，用給定的值與查找區間的中間元素的值相比較，若相等，則查找成功；若不等，則縮小范圍，判斷該值落在區間的前一部分還是后一部分，再將其所在的部分作為新的查找區間，繼續上述過程，一直到找到該值或區間長度小于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.設置查找的最初區間[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]，設定下一查找范圍是左半區間[low，mid-1]。若key>a[mid]，設定查找范圍是右半區間[mid+1，high]。

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