快速排序算法

1、快速排序算法快速排序就是递归调用此过程在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：初始状态 49 38 65 97 76 13 27 进行一次快速排序之后划分为 27 38 13 49 76 97 65 分别对前后两部分进行快速排序27 38 13 经第三步和第四步交换后变成 13 27 38 完成排序。76 97 65 经第三步和第四步交换后变成 65 76 97 完成排序。运行结果：27 38 13 49 76 97 6513 27

2、 38 49 76 97 65 13 27 38 49 65 76 97第一轮函数调用的详细过程： 49 38 65 97 76 13 27i =0 j=6 Key=49 第一轮循环：i=0 j=6 27 38 65 97 76 13 27 j=6 27 38 65 97 76 13 65 i=2 第二轮循环：i=2 j=6 27 38 13 97 76 13 65 j=5 27 38 13 97 76 97 65 i=3第三轮循环：i=3 j=5 27 38 13 97 76 97 65 j=3 循环结束： i=3 j=3 ai=key 27 38 13 49 76 97 65C语言版本12

3、34567891011121314151617181920212223242526272829303132333435363738voidsort(int*a,intleft,intright)if(left=right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/return;inti=left;intj=right;intkey=aleft;while(ij)/*控制在当组内寻找一遍*/while(ij&key=aj)/*而寻找结束的条件就是：1，找到一个小于或者大于key的数（大于或小于取决于你想升序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/j-

4、;/*向前寻找*/ ai=aj;/*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是aleft，那么就是给key）*/while(i=ai)/*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/i+;aj=ai;ai=key;/*当在当组内找完一遍以后就把中间数key回归*/sort(a,left,i-1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/sort(a,i+1,right);/*用同样的方式对分出来的右边的小组进行同上的做法*/*当然最后可能会出现

5、很多分左右，直到每一组的i=j为止*/C+语言123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#includeusingnamespacestd;voidQsort(inta,intlow,inthigh)if(low=high)return;intfirst=low;intlast=high;intkey=afirst;/*用字表的第一个记录作为枢轴*/while(firstlast)while(first=key)-last;afirst=alast;/*将比第一个

6、小的移到低端*/while(firstlast&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,96,33,24;Qsort(a,0,sizeof(a)/sizeof(a0)-1);/*这里原文第三个参数要减1否则内存越界*/for(inti=0;isizeof(a)/sizeof(a0);i+)coutai;return0;/*参考数据结构p274(清华大学出

7、版社，严蔚敏)*/Java123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127classQuickpubl

8、icvoidsort(intarr,intlow,inthigh)intl=low;inth=high;intpovit=arrlow;while(lh)while(l=povit)h-;if(lh)inttemp=arrh;arrh=arrl;arrl=temp;l+;while(lh&arrl=povit)l+;if(llow)sort(arr,low,l-1);if(hhigh)sort(arr,l+1,high);/*/方式二/*/更高效点的代码：publicTextendsComparableTquickSort(TtargetArr,intstart,intend)inti=sta

9、rt+1,j=end;Tkey=targetArrstart;SortUtilsUtil=newSortUtil();if(start=end)return(targetArr);/*从i+和j-两个方向搜索不满足条件的值并交换*条件为：i+方向小于key，j-方向大于key*/while(true)while(targetApareTo(key)0)j-;while(targetApareTo(key)0&i=j)break;sUtil.swap(targetArr,i,j);if(targetArri=key)j-;elsei+;/*关键数据放到中间*/sUti

10、l.swap(targetArr,start,j);if(starti-1)this.quickSort(targetArr,start,i-1);if(j+1end)this.quickSort(targetArr,j+1,end);returntargetArr;/*/方式三：减少交换次数，提高效率/*/privateTextendsComparablevoidquickSort(TtargetArr,intstart,intend)inti=start,j=end;Tkey=targetArrstart;while(ii&targetApareTo(key)=0)j-;if

11、(ij)/*targetArri已经保存在key中，可将后面的数填入*/targetArri=targetArrj;i+;/*按i+方向遍历目标数组，直到比key大的值为止*/while(ij&targetApareTo(key)=0)/*此处一定要小于等于零，假设数组之内有一亿个1，0交替出现的话，而key的值又恰巧是1的话，那么这个小于等于的作用就会使下面的if语句少执行一亿次。*/i+;if(ij)/*targetArrj已保存在targetArri中，可将前面的值填入*/targetArrj=targetArri;j-;/*此时i=j*/targetArri=key;/*

12、递归调用，把key前面的完成排序*/this.quickSort(targetArr,start,i-1);/*递归调用，把key后面的完成排序*/this.quickSort(targetArr,j+1,end);C#1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;us

13、ingSystem.Text;namespacetestclassQuickSortstaticvoidMain(stringargs)intarray=49,38,65,97,76,13,27;sort(array,0,array.Length-1);Console.ReadLine();/*一次排序单元，完成此方法，key左边都比key小，key右边都比key大。*paramarray排序数组*paramlow排序起始位置*paramhigh排序结束位置*return单元排序后的数组*/privatestaticintsortUnit(intarray,intlow,inthigh)intkey=arraylow;while(low=key&highlow)-high;/*比key小的放左边*/arraylow=arrayhigh;/*从前向后搜索比key大的值，比key大的放右边*/while(arraylowlow)+low;/*比key大的放右边*/arrayhigh=arraylow;/*左边都比key小，右边都比key大。/将key放在游标当前位置。/此时low等于high*/arraylow=key;foreach(intiinarray)Console.Write(0t,i);Console.WriteLine();re