快速排序算法分析解析

1、123456789101112131415161718return;inti=left;intj=right;intkey=aleft快速排序算法快速排序就是遞歸調用此過程一一在以49為中點分割這個數(shù)據(jù)序列，分別對前面一部分和后面一部分進行類似的快速排序，從而完成全部數(shù)據(jù)序列的快速排序，最后把此數(shù)據(jù)序列變成一個有序的序列，根據(jù)這種思想對于上述數(shù)組A的快速排序的全過程如圖6所示：初始狀態(tài)49386597761327進行一次快速排序之后劃分為27381349769765分別對前后兩部分進行快速排序273813經第三步和第四步交換后變成132738完成排序。769765經第三步和第四步交換后變成65

2、7697完成排序。運行結果：273813497697651327384976976513273849657697第一輪函數(shù)調用的詳細過程：49386597761327i=0j=6Key=49第一輪循環(huán)：i=0j=627386597761327j=627386597761365i=2第二輪循環(huán)：i=2j=627381397761365j=527381397769765i=3第三輪循環(huán)：i=3j=527381397769765j=3循環(huán)結束：i=3j=3ai=key27381349769765C語言版本voidsort(int*a,intleft,intright)if(left>=righ

3、t)/*如果左邊索引大于或者等于右邊的索引就代表已經整理完成一個組了*/while(i<j)/*控制在當組內尋找一遍*/while(i<j&&key<=aj)/*而尋找結束的條件就是：1，找到一個小于或者大于key的數(shù)(大于或小于取決于你想升序還是降序)2,沒有符合條件1的，并且i與j的大小沒有反轉*/1920212223242526272829303132333435363738j-;/*向前尋找*/ai=aj;/*找到一個這樣的數(shù)后就把它賦給前面的被拿走的i的值(如果第一次循環(huán)且key是aleft,那么就是給key)*/while(ij&&

4、key>=ai)/*這是i在當組內向前尋找，同上，不過注意與key的大小關系停止循環(huán)和上面相反，因為排序思想是把數(shù)往兩邊扔，所以左右兩邊的數(shù)大小與key的關系相反*/i+；aj=ai;ai=key;/*當在當組內找完一遍以后就把中間數(shù)key回歸*/sort(a,left,i-1);/*最后用同樣的方式對分出來的左邊的小組進行同上的做法*/sort(a,i+1,right);/*用同樣的方式對分出來的右邊的小組進行同上的做法*/*當然最后可能會出現(xiàn)很多分左右，直到每一組的i=j為止*/C+語言#includeiostreamusingnamespacestd;45 void67891011

5、1213Qsort(inta,intlow,inthigh)if(low=high)return;intfirst二low;intlast二high;intkey=afirst;/*用字表的第一個記錄作為樞軸*/1415while(firstlast)1718192021222324252627282930313233343536373839404196,33,24;1);/*這里原文第三424344454647while(firstlast&&alast=key)last;afirst二alast;/*將比第一個小的移到低端*/while(firstlast&&

6、;afirst二key)+first;alast二afirst;/*將比第一個大的移到高端*/afirst=key;/*樞軸記錄到位*/Qsort(a,low,first-1);Qsort(a,first+1,high);intmain()inta=57,68,59,52,72,28,Qsort(a,0,sizeof(a)/sizeof(a0)-個參數(shù)要減1否則內存越界*/for(inti=0;isizeof(a)/sizeof(a0);i+)coutai<<""48return0;/*參考數(shù)據(jù)結構p274（清華大學出版社，嚴蔚敏）*/123456classQu

7、ickpublicvoidsort(intarr,intlow,inthigh)intl=low;inth=high;intpovit二arrlow;while(lh)while(lh&&arrh>=povit)h-;if(lh)inttemp=arrh;arrh=arrl;arrl=temp;l+；while(l<h&&arrl<=povit)l+；if(l<h)inttemp=arrh;arrh=arrl;arrl=temp;h-;print(arr);System.out.print("l二+(l+)+h二+(h+1)+p

8、ovit二+povit+n);if(llow)sort(arr,low,l-l);if(hhigh)sort(arr,l+1,high);更高效點的代碼：publicTextendsComparable？superTTquickSort(TtargetArr,intstart,intend)inti二start+1,j=end;Tkey二targetArrstart;SortUtilTsUtil二newSortUtilT()；if(start二end)return(targetArr);/*從i+和j-兩個方向搜索不滿足條件的值并交換910111213141516171819202122232

9、4252627282930313233343536373839404142434445464748495051*52535455565758596061626364656667686970717273747576777879808182838485868788899091929394*條件為：i+方向小于key,j方向大于key*/while(true)while(targetApareTo(key)0)j;while(targetApareTo(key)0&&ij)i+;if(i>=j)break;sUtil.swap(targetArr,i

10、,j);if(targetArri=key)j-；elsei+；/*關鍵數(shù)據(jù)放到'中間'*/sUtil.swap(targetArr,start,j);if(starti-l)this.quickSort(targetArr,start,i-l);辻(j+lend)this.quickSort(targetArr,j+l,end);returntargetArr;/*/方式三：減少交換次數(shù)，提高效率/*/privateTextendsComparable？superTvoidquickSort(TtargetArr,intstart,intend)inti二start,j二en

11、d;Tkey二targetArrstart;while(i<j)/*按j方向遍歷目標數(shù)組，直到比key小的值為止*/while(ji&&targetApareTo(key)=0)9596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127j;if(ij)/*targetArri已經保存在key中，可將后面的數(shù)填入*/targetArri=targetArrj;i+;/*按i+方向遍歷目標數(shù)組，直到比key大的值為止*/while(i

12、j&&targetApareTo(key)=0)/*此處一定要小于等于零，假設數(shù)組之內有一億個1，0交替出現(xiàn)的話，而key的值又恰巧是1的話，那么這個小于等于的作用就會使下面的if語句少執(zhí)行一億次。*/i+；if(i<j)/*targetArrj已保存在targetArri中，可將前面的值填入*/targetArrj=targetArri;j-；/*此時i=j*/targetArri二key;/*遞歸調用，把key前面的完成排序*/this.quickSort(targetArr,start,i-l);/*遞歸調用，把key后面的完成排序*/this.qui

13、ckSort(targetArr,j+l,end);C#1234567usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;namespacetestclassQuickSortstaticvoidMain(stringargs)intarray=49,38,65,97,76,13,27;sort(array,0,array.Length-1);Console.ReadLine();/*一次排序單元，完成此方法，key左邊都比key小，key右邊都比key大。*paramarray排序數(shù)組*p

14、aramlow排序起始位置*paramhigh排序結束位置*return單元排序后的數(shù)組*/privatestaticintsortUnit(intarray,intlow,inthigh)intkey=arraylow;while(low<high)/*從后向前搜索比key小的值*/while(arrayhigh>=key&&high>low)high;/*比key小的放左邊*/arraylow=arrayhigh;/*從前向后搜索比key大的值，比key大的放右邊*/while(arraylow<=key&&high>low)+low;/*比key大的放右邊*/arrayhigh=arraylow;89101112131415161718192021222324252627282930/*左邊都比key小，右邊都比key大。/將key放在游標當前位置。/此時low等于high*/3132333435363738394041424344454647484950515arraylow=key;foreach(intiinarray)Console.Write("0t",i);Console.WriteLine();re