（1）冒泡、直插、選擇、快速、希爾、歸並排序算法進行比較； （2）待排序的元素的關鍵字為整數。其中的數

1.冒泡排序已知壹組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與a[2]的值，若a[1]大於a[2]則交換兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大於a[3]則交換兩者的值，否則不變。再比較a[3]與a[4]，以此類推，最後比較a[n-1]與a[n]的值。這樣處理壹輪後，a[n]的值壹定是這組數據中最大的。再對a[1]~a[n-1]以相同方法處理壹輪，則a[n-1]的值壹定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理壹輪，以此類推。***處理n-1輪後a[1]、a[2]、……a[n]就以升序排列了。?優點：穩定，比較次數已知；缺點：慢，每次只能移動相鄰兩個數據，移動數據的次數多。?初始關鍵字 [49 3865 97 76 13 27 49]第壹趟排序後 [38 4965 76 13 27 49] 97第二趟排序後 [38 4965 13 27 49] 76 97第三趟排序後 [38 4913 27 49] 65 76 97第四趟排序後 [38 1327 49] 49 65 76 97第五趟排序後 [38 1327] 49 49 65 76 97第六趟排序後 [13 27]38 49 49 65 76 97第七趟排序後 [13] 2738 49 49 65 76 97最後排序結果 13 2738 49 49 76 76 97?#include <iostream>using namespace std;void main()? {? int i,j,k;? int a[8]={49,38,65,97,76,13,27,49};? for(i=7;i>=0;i--)? {? for(j=0;j<i;j++) { if(a[j]>a[j+1])? { k=a[j]; a[j]=a[j+1]; a[j+1]=k;? } } }? for(i=0;i<8;i++)? cout<<a<<endl;? } 2.選擇排序?①初始狀態：無序區為R[1..n]，有序區為空。?②第1趟排序 在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。……?③第i趟排序第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R[i..n](1≤i≤n-1)。該趟排序從當前無序區中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R[i+1..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區.這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。?優點：穩定，比較次數與冒泡排序壹樣；缺點：相對之下還是慢。?初始關鍵字 [49 3865 97 76 13 27 49]第壹趟排序後 13 〔38 65 97 76 49 27 49]第二趟排序後 13 27 〔65 97 76 49 38 49]第三趟排序後 13 2738 [97 76 49 65 49]第四趟排序後 13 2738 49 [49 97 65 76]第五趟排序後 13 2738 49 49 [97 97 76]第六趟排序後 13 2738 49 49 76 [76 97]第七趟排序後 13 2738 49 49 76 76 [ 97]最後排序結果 13 2738 49 49 76 76 97?#include <iostream>using namespace std;void main(){? int i,j,k,t;? int R[8]={49,38,65,97,76,13,27,49};? for(i=0;i<7;i++) { k=i; for(j=i+1;j<8;j++) if(R[j]<R[k]) k=j;? if(k!=i) { t=R[j];R[j]=R[k];R[k]=t; } }for(i=0;i<8;i++)? cout<<R<<endl;? }

3.插入排序已知壹組，壹組無序數據b[1]、b[2]、……b[m]，需將其變成壹個升序數列。先創建壹個變量a。首先將不b[1]與b[2],如果b[1]大於b[2]則交換位置，否則不變；再比較b[2]與b[3]，如果b[3]小於b[2]，則將b[3]賦值給a，再將a與b[1]比較，如果a小於b[1]；則將b[2]，b[1]依次後移；在將a放在b[1]處以此類推，直到排序結束。初始關鍵字 [49 3865 97 76 13 27 59] a? b[1] b[2]? b[3]? b[4] b[5]? b[6]? b[7] b[8]1-----49? 49 >? 38? 65? 97 76? 13 27? 5938? 49? 49? ……….38? 38? 49? ……….2-----38? 38 49 < 65? 97 76? 13? 27? 593-----38? 38 49? 65 <97 76? 13? 27? 594----38? 38 49? 65? 97>? 76? 13? 27? 5976? 38? 49? 65? 97? 97……..76? 38? 49? 65? 76? 97……..以此類推void insertSort(Type* arr,long len){? long i=0,j=0;? for(i=1;i<len;i++)? {? j=i;? tmpData=arr[j];//tmpData用來儲存數據 while(tmpData<arr[j-1]&&j>0)? { arr[j]=arr[j-1]; j--;? }? arr[j]=tmpData;? }}4.縮小增量排序(希爾排序)由希爾在1959年提出，又稱希爾排序。已知壹組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。發現當n不大時，插入排序的效果很好。首先取壹增量d(d<n)，將a[1]、a[1+d]、a[1+2d]……列為第壹組，a[2]、a[2+d]、a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……列為最後壹組以次類推，在各組內用插入排序，然後取d'<d，重復上述操作，直到d=1。增量d(1, 3, 7,15, 31, …, 2^k-1)是使用最廣泛的增量序列之壹.優點：快，數據移動少；缺點：不穩定，d的取值是多少，應取多少個不同的值，都無法確切知道，只能憑經驗來取。初始：d＝5? 49? 38? 65? 97? 76? 13? 27? 49? 55? 44 ? 壹趟結果? 13? 27? 49 55? 44? 49? 38? 65? 97 76 ?d=3 |----------------------|----------------------|---------------------| ? 二趟結果? 13? 44? 49 38? 27? 49? 55? 65? 97? 76? d=1 ? 三趟結果? 13? 27? 38 44? 49? 49? 55? 65? 76? 97? #include <iostream>using namespace std;#define MAX 16? void shell_sort(int *x, int n){? inth, j, k, t;? for(h=n/2;h>0; h=h/2) /*控制增量*/? {? for(j=h; j<n; j++) /*這個實際上就是上面的直接插入排序*/? { t= *(x+j); for(k=j-h; (k>=0 && t<*(x+k)); k-=h) { *(x+k+h)= *(x+k); } *(x+k+h)= t;? }? }}void main(){? int*p, i, a[MAX];? p= a;? cout<<"InputMAX number for sorting :"<<endl;? for(i=0; i<MAX; i++)? cin>>*p++;? p=a;? shell_sort(p,MAX);? for(p=a, i=0; i<MAX; i++)? {? cout<<*p++<<endl;? }? cout<<endl;}

5.快速排序快速排序是冒泡排序的改進版，是目前已知的最快的排序方法。已知壹組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先任取數據a[x]作為基準。比較a[x]與其它數據並排序，使a[x]排在數據的第k位，並且使a[1]~a[k-1]中的每壹個數據<a[x]，a[k+1]~a[n]中的每壹個數據>a[x]，然後采用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n]兩組數據進行快速排序。優點：極快，數據移動少；缺點：不穩定。分段插入排序void QuickSort(int *pData, int left, intright){int i, j;int middle,iTemp;i = left;j = right;middle =pData[(left + right) / 2]; //求中間值do{while((pData < middle) && (i < right)) //從左掃描大於中值的數i++;while((pData[j] > middle) && (j > left)) //從右掃描小於中值的數j--;if (i <=j) //找到了壹對值{//交換iTemp =pData;pData =pData[j];pData[j] =iTemp;i++;j--;}} while (i<= j) ; //如果兩邊掃描的下標交錯，就停止（完成壹次）//當左邊部分有值(left<j)，遞歸左半邊if(left<j)QuickSort(pData,left,j);//當右邊部分有值(right>i)，遞歸右半邊if(right>i)QuickSort(pData,i,right);}?6.歸並排序算法合並排序（MERGESORT）是又壹類不同的排序方法，合並的含義就是將兩個或兩個以上的有序數據序列合並成壹個新的有序數據序列，因此它又叫歸並算法。它的基本思想就是假設數組A有N個元素，那麽可以看成數組A是又N個有序的子序列組成，每個子序列的長度為1，然後再兩兩合並，得到了壹個 N/2? 個長度為2或1的有序子序列，再兩兩合並，如此重復，值得得到壹個長度為N的有序數據序列為止，這種排序方法稱為2—路合並排序。例如數組A有7個數據，分別是： 49? 38? 65 97? 76? 13? 27，那麽采用歸並排序算法的操作過程如圖7所示：初始值 [49]? [38]? [65]? [97]? [76]? [13]? [27]第壹次合並之後 [38 49] [65 97]? [13 76]? [27]第二次合並之後 [38 49? 65 97]? [13 27 76]第三次合並之後 [13 27? 38 49 65? 76 97]合並算法的核心操作就是將壹維數組中前後相鄰的兩個兩個有序序列合並成壹個有序序列。合並算法也可以采用遞歸算法來實現，形式上較為簡單,但實用性很差。合並算法的合並次數是壹個非常重要的量,根據計算當數組中有3到4個元素時,合並次數是2次,當有5到8個元素時,合並次數是3次,當有9到16個元素時,合並次數是4次，按照這壹規律,當有N個子序列時可以推斷出合並的次數是X(2? >=N,符合此條件的最小那個X)。其時間復雜度為：O(nlogn).所需輔助存儲空間為：O(n)歸並排序：#include <stdio.h>void merge(int a[],int p,int q,int r){int n1=q-p+1,n2=r-q,i,j,k;int l[1002],R[1002];for (i=1;i<=n1;i++)l=a[p+i-1];for (j=1;j<=n2;j++)R[j]=a[q+j];R[n2+1]=l[n1+1]=999999;i=j=1;for (k=p;k<=r;k++){if (l<=R[j]){a[k]=l;i++;}else{a[k]=R[j];j++;}}}void mergesort(int a[],int p,int r){int q;if (p<r){q=(p+r)/2;mergesort(a,p,q);mergesort(a,q+1,r);merge(a,p,q,r);}}int main(){int a[1001],t,n,i;scanf("%d",&t);while (t--){scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a);mergesort(a,1,n);for (i=1;i<=n;i++){printf("%d",a);if (i!=n)printf(" ");}printf("\n");}return 0;}

上一篇:文科生和理科生談戀愛是壹種什麽感覺？

下一篇:合肥哪裏有烘焙的學校？