快速排序算法實驗報告

在操作系統(tǒng)中，我們總是希望以最短的時間處理完所有的任務(wù)。但事情總是要一件件地做，只需要將n件任務(wù)按用時去從小到大排序，就可以得到任務(wù)依次的處理順序。當(dāng)有n件ni，求讓所有任務(wù)等待的時間和最小的任務(wù)處理順序。二、需求分析n，nn值隨機產(chǎn)生。3.輸入輸出格式：n，接下來一行，有n輸出有n用的時間。按此順序進(jìn)行，則使得所有任務(wù)等待時間最小。4.測試數(shù)據(jù)：輸入53426157312334556kkn-k個位置上。k也是軸值的下標(biāo)。這樣k把數(shù)組分成了兩個子數(shù)組。分別對兩個子數(shù)組，輸入事件件數(shù)n快速排序方法（因圖難畫，舉一個實例）：初始狀態(tài)72657888542lr循環(huán)72657888542lr第一次交換67257888542lr第二趟循環(huán)7257888542rl第二次交換72657888542r反轉(zhuǎn)交換67257888542r這就是依靠軸值，將數(shù)組分成兩部分的實例（42voidqsort(int*array,intl,intr){intpivotIndex=l+rand()%(r-l+1swap1(array,pivotIndex,r);//將選定的軸值放到每段數(shù)組的最后intk=partition(array,l-1,r,array[r]);//依靠軸值，將數(shù)組分//成兩部分swap1(array,k,r)qsort(array,l,k-1);//遞歸調(diào)用，對數(shù)組左右兩部分進(jìn)行排序qsort(array,k+1,r);}/*將大于軸值的放右邊，小于軸值的放左邊算法實現(xiàn)*/intpartition(int*array,intl,intr,constintpivot){while((r!=0)&&(array[--r]>pivot));swap1(array,l,r);returnΘ(n2)，但很少出現(xiàn)這種情況。如果快速排序找到了Θ(nn)。n=原始序列：//提示隨機產(chǎn)生的n四、測試結(jié)果五、實驗心得（可選六、附錄（實驗源碼#include<iostream>#include<ctime>usingnamespace//產(chǎn)生nint*crtArray(int&size){intn;cout<<"n=";cin>>n;srand(time(NULL));int*intArray=newint[n];size=n;cout<<"原始序列："<<endl;for(inti=0;i<n;i++){intArray[i]=rand()%10;if(intArray[i]==0){i--;continue;}cout<<<<"";cout<<endl;returnvoidswap1(int*array,int&a,int&b){inttemp=array[a];array[a]=array[b];array[b]=temp;}intpartition(int*array,intl,intr,constint{do{while(array[++l]<pivot);while((r!=0)&&(array[--r]>=pivot));swap1(array,l,r);}while(l<r);swap1(array,l,r);returnl;}voidqsort(int*array,intl,intr){if(r<=l)return;intpivotIndex=r;intk=partition(array,l-1,r,array[r]);swap1(array,k,r);qsort(array,l,k-1);qsort(array,k+1,r);}/*主函數(shù)*/intmain(){intsize;int*Array;Array=crtArray(size);qsort(Array,0,size-1);cout<<"結(jié)果："<<endl;for(inti=0;i<size;i++)cout<<Array[i]<<"";cout<<endl;return0;}姓名：XXX一、需求分析排序是計算機內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。假設(shè)含nR1,R2,?，Rn}其相應(yīng)的關(guān)鍵字序列為{K1,K2,?，Kn}這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個關(guān)系：按此固有關(guān)系將上式記錄序列重新排列為{Rp1,Rp2,?，Rpn排序算法是計算機科學(xué)中最重要的研究問題之一。對于排序的研究既有理論上的重要意義，領(lǐng)域具有廣泛應(yīng)用。常見的排序算法有起泡排序、直接插入排序、簡單選擇排序、快速1：有時候應(yīng)用程序本身就需要對信息進(jìn)行排序。為了準(zhǔn)備客戶賬目，銀行需要根據(jù)支2：在一個繪制互相重疊的圖形對象的程序中，可能需要根據(jù)一個“在上方”關(guān)系將各3：在一個由ni4：對一個含有nk在操作系統(tǒng)中，我們總是希望以最短的時間處理完所有的任務(wù)。但事情總是要一件件地做，只需要將n件任務(wù)按用時去從小到大排序，就可以得到任務(wù)依次的處理順序。當(dāng)有n件任務(wù)同時來臨時，每件任務(wù)需要用時ni當(dāng)有nni，求出讓所有任務(wù)等待的時間和最小的n，接下來一行，有n輸出有n請輸入任務(wù)件數(shù)：-2.請輸入任務(wù)件數(shù)3.請輸入任務(wù)件數(shù)4.請輸入任務(wù)件數(shù)6157(一)函數(shù)調(diào)用關(guān)系圖intstart,intrandom(intstart,intend);voidchange(inta[],inti,intj);a[],int函數(shù)voidQuickSort(inta[],intend);start,intend);QuickSort(inta[],intstart,int（一）本程序所輸入的任務(wù)件數(shù)和任務(wù)時間均為整數(shù)，可使用整數(shù)intcout<<"請輸入任務(wù)件數(shù):";while(size)//任務(wù)件數(shù)大于0，則執(zhí)行該循環(huán)，否則重新輸入件數(shù){inti;cout<intrandom(intstart,intintsrand(time(NULL));//設(shè)置隨機數(shù)種子，對多組數(shù)據(jù)排序時不會取相同的軸值returnt;voidchange(inta[N],inti,intintt;intPartition(inta[],intstart,intinttemp=random(start,end);//得到隨機軸值inti=start-1;//iintbase=a[end];//以最后一個數(shù)作為劃分的基點for(intj=start;j<end;j++)returni+1;voidQuickSort(inta[N],intstart,int電子科技大學(xué)學(xué)生姓名：學(xué)號：點名序號：指導(dǎo)教師：2014-2015-2學(xué)生姓名實驗地點：基礎(chǔ)實驗大樓實驗時間：520快速排序的基本思想是：通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩A[1]……A[N]，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）I、J以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即J（J：=J-1），XI（I：=I+1），X3、4I=J二分法查找（折半查找）min，low，highamid（R[mid].key）比較，若相等，則查找成功，如果R[mid].key>a，則由表的有序性可知，R[mid].keya，aR[mid].keyhigh=mid-1;如果R[mid].key<a,則等于aR[mid].key如果R[mid].key=a，下一次查找針對新的查找區(qū)間，重復(fù)步驟（1）和在查找過程中，lowhighhigh<low，則查找失敗。實現(xiàn)折半查找算法,并在步驟(2)排序后的序列上,進(jìn)行任意地查找,并輸出查詢結(jié)果。PCC#defineMAX#defineFROMFILE1typedefstructJD{intkey;intbich(JDr[],intn,int{intlow,high,mid,found;low=1;high=n;found=0;{mid=(low+high)/2;if(k>r[mid].key)low=mid+1;elseif(k==r[mid].key)found=1;voidquicksort(JDr[],intlow,inthigh){inti,j,k;JDwhile((i<j)&&(r[j].key>=x.key))j--while((i<j)&&(r[i].key<=x.key))i++;if(i<j){r[j]=r[i];j--int#ifdefFROMFILEprintf("請輸入你所要查找的數(shù)組長度:");intlength;JDinti;printf("輸入第%di);FILE*fp;fp=fopen("test.txt","r");return0;JDinti=1;while(fscanf(fp,"%d",&a[i